data structures

data can be added or removed from one location - the TOP of the stack LIFO (last in first out) structure

push() - add an item to the top of the stack pop() - take an item from the top\

cant push if stack full cant pop if stack empty

push - add an item at the top pointer and then move the top pointer up by one

pop - return the value at the top pointer then move the top pointer down by one

traverse or insert is not possible big-O value of all stack operations is one no wasted space

• undo button • recursive function

data can be added at the end/ tail of the queue can be removed at the front/ head of the queue FIFO ( first in first out) structure

Enqueue - add item to end of queue Dequeue - take an item from front of queue

add an item at the end marker move it forward by one

return value at front marker and move it forward by one

• queue moves along in available space as changes are made • to avoid running out of space it can be made circular. if the end of the queue catches up w the front, no more items can be added

traverse insert not possible big- O value of all queue operations is 1 no wasted space

print queue

made of nodes each node contains an item of data and a pointer to the next node

start at header follow pointers until reach node with no pointers

add the item in an empty space change pointers to include item in the list

change pointers so that the list skips over the deleted item

computer remembers the location of an empty storage space this is where new nodes can be added after adding a new node the free space pointer is updated

• wide range of operations possible. traverse, search , insert, sort, delete etc. • most operations have O(n) - linear complexity, making the linked list slower than a stack or queue

list data type in python

made of nodes each node holds one data value and more than one pointer

root - start value branches - nodes to left and right of root leaf node- a node with no branches

made of nodes with two pointers