1.4.2 Data Structures

• a static data structure in which data is stored in continuous, Adjacent memory locations [1] • can only store one data type [1] • provides direct access to elements • are usually zero indexed

• is a row in a file and is made up of fields • is widely used in databases • can be implemented using OOP in python

• a static data structure • An ordered collection of elements that can contain multiple data types • is immutable - so elements can’t be added or removed once it has been created [1] • are initialised using regular brackets instead of square ones

Size can’t change during processing [1]

• size can change during processing [1] • disadvantage : storage requirements are unknown initially [1]

• a dynamic data structure used to hold an ordered sequence [1] • each item/node consist of a data field and a pointer field [1] • data field contains the actual data • pointer field gives the location of the next node/item in the list [1] • linked list needs to be traversed until desired element is found [1] • takes longer to search (as more nodes are added) [1]

• array provides direct access to all elements [1] whereas a linked list needs to be traversed until desired element is found [1] • contents of an array are stored continuously in memory [1] • whereas contents of linked list do not have to be in continuous data locations [1]

• adding node • deleting node • traversing linked list

• is used to access each element of the linked list • first position is indicated by the start pointer [1] • linked list can be traversed by following each items next pointer until the end of the list is located (null) • pointer = null means end of list has been reached

• advantage: nodes can be added or removed easily by editing the pointers 1. Allocate memory and create new node containing the data [1] 2. Change the new node to point to the previous nodes next node [1] 3. Change the previous nodes next node to point to the new node [1] • if the new node is added to the start change its pointer to point to the head node • if added at the end let it point to null

• involves updating nodes to bypass the deleted node • node is not truly removed but ignored instead which wastes memory • so to delete a node, change the next pointer of the previous node to bypass the node being deleted and instead point to the next node • linked list requires more memory than arrays due to storing pointers

• is a LIFO data structure [1] • items can only be added or removed from the top of the stack • stacks are used to reverse actions eg back buttons and undo buttons use stacks • stacks use a pointer which points to the top of the stack • when initialising stack we set TOP pointer = -1 • thus is stack is empty TOP = -1

• push(value) • pop() • isEmpty() • isfull() • Size()

• adds an element to the top of the stack (checks if stack is full first) • once value is pushed, the top pointer is incremented by 1 • attempting to push an item onto a full stack is called stack overflow

• removes and returns value at the top of the stack (checks if stack is empty first) • once popped, the pointer is decremented by 1 • attempting to pop an item from an empty stack is called stack underflow

• checks if stack is empty • eg if Top == -1 return true • or return len(stack) == 0

• Checks jf stack is full • compares stack size to the top pointer • if len(stack) == Top return true

Returns size of the stack

• a FIFO data structure • in which items are added at the end of the queue • and items are removed from the front of the queue • Consist of a head and tail pointer • similar to stacks there is also queue overflow and queue underflow

• linear queue • circular queue • priority queue

• Enqueue(value) • dequeue() • peek() • isfull() • isempty()

• adds element to the back of the queue 1. Check if queue is full 2. Increment tail pointer and add the new element in the position pointed by the tail 3. Head pointer stays the same

• returns an elements from the front of a queue 1. Check that queue is not empty 2. Return item at the front of the queue and then increment the head pointer by 1

Returns the value of the item at the front of the queue without removing it from the queue