1.4.2 Data Structures

An array allows you to store multiple items of the same data type under a shared common name.

… random access to all element is available via its direct index.

• They can only store one data type - They’re a static data structure (their scope is pre-determined)

an un-ordered data structure which is accessed through an attribute. It can store many different data types.

Lists and tuples

Tuples are lists that cannot be edited and is said to be immutable.

structure and data cannot be changed at run time.

structure and data can be changed at run time.

size of the structure cannot change at run time

size of the structure can change at run time.

A stack is known as a LIFO, a single pointer is used to point to the top item of the stack, when a new item is pushed onto the stack the pointer is incremented. When an item is popped off the stack the pointer decrements to point to the new top of the stack.

last in first out - the last item you push to the top of the list is the first item you pop off the stack.

A queue is known as a FIFO structure. A pair of pointers is used to point to the front and back of the queue. If an item is popped from the queue the front pointer points to the item being popped. If an item is pushed onto a queue the tail pointer increments by one and points to the new end of queue.

first in first out - because the new items get pushed to the back of the queue and new items get popped from the front of the queue.

• Check to see if the stack is full • If the stack is full report error and stop • Increment the stack pointer • Insert new data item into location pointed to by the stack pointer and stop

• Check to see if the stack is empty • If the stack is empty report an error and stop • Copy the data item in location pointed to by the stack pointer/ delete the data item • Decrement the stack pointer

• Check to see is the queue is full • If the queue is full report an error and stop • Insert new data item into location pointed to by the tail pointer • Increment the tail pointer and stop This is where the tail pointer is pointing to the next free space not the last item. You can have the tail pointer point to the last item in which case increment then insert then stop

• Check to see if the queue is empty • If the queue is empty report an error and stop • Copy data item in location pointed to by the head pointer/ delete the data item • Increment head pointer and stop

A list of data together with a set of links to sort the data. Data is stored in the order its input and pointers are used to link the data into the desired order.

• Implementing undo functionality • Dealing with browser cache • Helping with operating system job queues

• Store the data at the location indicated by the free storage pointer • Alter the free storage pointer to the next free storage space • Set the pointer for the item that will precede it to the new data item • Update the pointer for the new data item to that previously stored in the item the preceded it (i.e. the next data item)

• If the item to remove is in the first position a. Then update starting pointer value of item you want to delete and update all the pointers • Else if the item is in any other position a. Update the pointer value in the preceding node from the one you want to delete to the value of the pointer in the item to be removed and all the succeeding data items pointers • Update the free storage

• Set the pointer to the start value • Repeat: a. Go to the node b. Output the data at the node c. Set the pointer to the value of the next item pointer at the pointer d. until pointer = 0/null

• Set the pointer to the start value • Repeat: a. Go to node (pointer value) b. If the data at the node is the search item i. Then Output the data and stop c. Else i. Set the pointer to the value of the next item pointer at the node d. Until pointer = 0 • Output data not found