Data Structure
A data structure is a group / set / collection of related data items / elements
Data Structure Advantages
Convenient / best way of organising data relating to a real problem
An efficient way to deal with various elements as one item
Data Structure Disadvantage
More Complex to program
Array
- 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
2D Array
A 2D array is a grid-like structure which can hold both rows and columns of the same data type.
Record
- 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
Linked List
- 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
Searching Linked List
UNORDERED
Can’t be terminated until all items have been inspected
ORDERED
Can be terminated when a value greater than search is found
Linked List Advantages
- New items can be inserted without rearranging the other elements
- Uses memory more efficiently as is dynamic and can shrink/grow
Linked List Disadvantages
- More complex to program
- Can only be accessed in a linear manner
- Use more memory as store pointer aswell as data
Stack
- 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
Stack Underflow and Overflow
UNDERFLOW
Attempt to POP an empty stack
OVERFLOW
Attempt to PUSH a full stack
Binary Tree
- 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
Binary Tree nodes contain…
- Data
- Left Node
- Right Node
- Leaf nodes (no children) point to null
Delete a Binary Tree node
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
Pre Order Traversal Use
Clone a tree e.g. make a copy of files in a hierarchical file structure
ROOT -> LEFT -> RIGHT
In Order Traversal Use
Outputting node content in order
LEFT -> ROOT -> RIGHT
Post Order Traversal Use
Deleting all of the node contents
LEFT -> RIGHT -> ROOT
Binary Tree Comparisons with Array and Linked List
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
Hash Table
- 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
Hashing Table: Chaining
- 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
Hashing Table: Progressive Overflow
- 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
Hashing Algorithm: Overflow
- 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
Queue
- 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
