1.1

A data structure is a group / set / collection of related data items / elements

Convenient / best way of organising data relating to a real problem An efficient way to deal with various elements as one item

More Complex to program

• An array is a data structure which is a set of data elements of the same data type • Elements are accessed using an index • Has a pre determined number of elements

A 2D array is a grid-like structure which can hold both rows and columns of the same data type.

• A record is a set of data items related to a single individual / entity • It can contain data of different data types • Can be processed as one item by a computer

• Nodes in a list contain the data itself and address of the next node (pointer) • First element is head node, list has to be traveresed from start. • Dynamic structure (can grow/shrink) • Last node points to null

UNORDERED Can’t be terminated until all items have been inspected ORDERED Can be terminated when a value greater than search is found

• New items can be inserted without rearranging the other elements • Uses memory more efficiently as is dynamic and can shrink/grow

• More complex to program • Can only be accessed in a linear manner • Use more memory as store pointer aswell as data

• Data Structure where items can only be added and removed from the top • Last in first out (LIFO) • Push (add), Pop (remove) • Limited access, can only be accessed from the top • Can be used as a recursive data structure

UNDERFLOW Attempt to POP an empty stack OVERFLOW Attempt to PUSH a full stack

• Each node has a max of 2 children • Everything on the left is less than or equal to the root • Everything on the right is greater than the root

• Data • Left Node • Right Node • Leaf nodes (no children) point to null

DELETE ROOT Replace root with highest value from left side of tree 1 CHILD Replace node with child 2 CHILDREN Replace node with child at left pointer

Clone a tree e.g. make a copy of files in a hierarchical file structure ROOT -> LEFT -> RIGHT

Outputting node content in order LEFT -> ROOT -> RIGHT

Deleting all of the node contents LEFT -> RIGHT -> ROOT

ARRAY ADVANTAGE Faster to search/ add (in order) a value ARRAY DISADVANTAGE More complex to program tree LINKED LIST ADVANTAGE Faster to access data in tree LINKED LIST DISADVANTAGE Binary tree has 2 pointers, list has 1

• Provides direct access to an item via its index and performance is not affected by the number of items stored • Index is a numeric value calculated from the value • Data can be retrieved using the key/index and hashing algorithm to return the value • Stores data in an associative array

• Original table has dynamic data strucutre for each location • After collision new node on linked list is created • Slow down finding data • Doesnt require prior knowledge of how many elements

• If location is occupied, use the next available location • wrap to start if end is reached • easy to maintain • not very efficient (could search through whole file) • Records are likely to be stored close to the calculated location • If blank is reached, not in file • Less total storage space • Fixed max capacity of the main file

• Seperate pre-allocated file • Flag original block • Move data into overflow area • Overflow area uses linear seach • Re organisation/ bigger file will eventually be needed

• Processing order is first in first out (FIFO) • 2 pointers, front and rear (rear points to next empty position) • Enqueue: insert a value • Dequeue: remove a value from front