1.4.2 DATA STRUCTURES

data can not be changed

data can be changed

An ordered data structure in which values have an index and is non-contiguous; mutable and can store various data types

Like a list(mutable) but its contiguous, ,static and only store one data type

Lists that are immutable, static but store various data types

its size cannot be changed afterwards

its size can be changed afterwards

A LIFO structure which has a stack pointer pointing at top node
Items can only be added / removed from the top

A FIFO structure in which has two pointers FRONT and REAR that track the items. Items are added at the rear and removed from the front

a type of queue in which front and rear pointers can wrap around to reuse spaces

Items are given priority and those with the highest go to the front

Dynamic data structure in which each item is called a node, and contains an index, data and pointers which give location of next node

A data structure which consists of nodes and pointers.

root node , leaf nodes , edges/pointers and child nodes

A set of nodes and pointers from any single node down to its leaf nodes

Type of tree which nodes can have up to two child nodes

1) If node is a leaf node - Just delete it
2) If node has one child node- Set previous pointer to child
3)If node has two child nodes. Set previous pointer to child which is next in a inorder traversal.

1)Check if free space
2)Create the node and insert data in it
3)Have previous node point to it
4)Set new nodes pointer to point next node
5)Update free pointer

1)Check if empty
2)Find Ben
3)Remove bens pointer
4)Update previous pointer to point to next node
5)Update free pointer

Data structure made of nodes and pointers.
Each node can have > 2 pointers and point to ANY nodes

Can point in two/one directions or not specify
Can be weighted

Mapping road networks for navigation
Social media network
Representing molecular structures

1)Visit first node A. Place in CN and R
2)Visits all its 1st connections. B C D. Place them in Q and R
3)Find next CN which is B remove it from Q
4)Visits its 1st connections
- repeat until all found

A B C D E F G

1)Visit first node A. Place in S and R
2) Visit alphabetical next so B and visit the whole path. Putting them in S and R
3)When path end or same node pop stack until new connection
Repeat until all found
A B E G C D F

1)Check for overflow
2)Increment stack/ back pointer
3)Insert data

1)Check for underflow
Stack:
2)Remove last item
3)Decrement pointer
Queue is opposite

Pre order- Root L R
Inorder - L Root R
Postorder - L R Root

Immediately find an item in un/sorted list without comparing items

1)Initial data passed into hash function
2)It converts it into hash address
3)Hash address tells where to store

Two keys trying to take same address

Open addressing - check next available spaces and store it there
Chaining - 2D array to store it. Overflow Linked list can be used

Linear probing - function sends start position of where linear search can be done until its found

Be calculated quickly
Result in as few collisions as possible
Use as little memory as possible