Data Structures Flashcards
array
An array allows you to store multiple items of the same data type under a shared common name.
Arrays can store data of the same data type contiguously in memory. This means…
… random access to all element is available via its direct index.
Limitations of arrays:
- They can only store one data type
- They’re a static data structure (their scope is pre-determined)
record
an un-ordered data structure which is accessed through an attribute. It can store many different data types.
What are pythons versions of arrays?
Lists and tuples
Tuples
Tuples are lists that cannot be edited and is said to be immutable.
immutable
structure and data cannot be changed at run time.
mutable
structure and data can be changed at run time.
Static data structure
size of the structure cannot change at run time
Dynamic data structure
size of the structure can change at run time.
Stack data structure
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.
LIFO
last in first out - the last item you push to the top of the list is the first item you pop off the stack.
Queue data structure
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.
FIFO
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.
Algorithm for insertion into a stack:
- 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
Algorithm for deletion/fetching from a stack:
- 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
Algorithm for insertion into a queue:
- Check to see is the queue is full
- If the queue is full report an error ad stop
- Insert new data item into location pointed to by the head pointer
- Increment the head pointer and stop
Algorithm for deletion/fetching from a queue:
- 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 tail pointer/ delete the data item
- Increment tail pointer and stop
linked lists
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.
uses of linked lists
- Implementing undo functionality
- Dealing with browser cache
- Helping with operating system job queues
Adding data from linked lists:
- 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)
Removing data from linked lists:
- 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
Traversing data from linked lists:
- 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
Searching for an item in a linked list:
- 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
Benefits of Hash tables
Speed of lookup, deletion and insertion of items is fast
hash table
an array which is coupled together with a hash function. The value from the hash function (hash value) maps the initial key to a fixed index in the hash table.
collision
the same hash value is given by two different keys.
collision solution
- Storing the key in the next available space
- adding a linked list to the location where the hash value is repeated
clustering
when there is a collision and the key is stored in the next available space increasing the likelihood of collisions.
solution clustering
combine hashtable with linked lists as overflow spaces
Searching an item in a hash table:
- Feed the key to the hash function
- Go directly to array index (HashValue)
- If the value is equal to the value that you’re searching for then output the value
- Else follow the linked list in sequence until you find the value and output the value
Inserting an item in a hash table:
- Feed in key to the hash function
- Go directly to the array index (HashValue)
- If the location is empty then insert the value
- Else follow the linked list in sequence until a free space in found and insert the value
Deleting an item in a hash table:
- Feed in key to hash function
- Go directly to array index (HashValue)
- If the value is equal to the value you’re searching for then mark as empty
- Else follow the linked list in sequence until you find the value then mark as empty and update the free pointer in the linked list.
uses of tuples
useful for accessing data that must not be changed
list
an ordered data structure accessed through an index. the have no predefined scope and can be edited during run time.
differences between one-dimensional arrays and list
arrays have a defined scope
hash function
A hash function is code which takes in data called a key and outputs a value (hash value).
multi-dimensional
an array containing one or more arrays.
What does a node in a linked link contain?
the data and a reference to the next node
graph
a set of edges/arcs connecting vertices/nodes
Possible uses of graphs:
- Navigation Systems
- Data Transmission
- Web page links
- Social media trends
dense graph
A graph which has more edges in relation to vertices
sparse graph
A graph which has few edges in relation to vertices
digraphs
has one or more edges that have an arrow indicating you can only go in one direction
tree
hierarchical data structure with data related to the data above it in the tree.
a simple connected graph with no cycles
arcs on a tree
branches
node at the top of the tree
root node
nodes lower than the root node
children
nodes with no sub-nodes
leaf-nodes or terminal nodes
binary tree
Tree structure where each node can only have two branches left or right
What do the nodes on a binary tree contain
left pointer, data, right pointer
depth first traversing uses a
stack
breadth first traversing uses a
queue
depth first traversing
follows one path down to a child node, it the visits this then backtracks to the next level then moves down to the next child node. Once all the child nodes from one branch have been visited it visits all the nodes on the next layer up.
breadth first traversing
It starts at the root node, and visits all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Inserting items into a binary search tree:
look at each node starting at the root. If the new value is less than the value at the node, move left otherwise move right. Repeat this for each node arrived at until there is no node. Insert a new node at this point and enter the data.
Algorithm for insertion into a binary tree:
- If tree is empty enter data item at root and stop; Current node = root
- Else repeat:
a. If new data item is less than value at current node go left, else go right.
b. Current node = node reach (null if no node)
c. Until current node is null - Create new node and enter data
different traversal methods
preorder
inorder
postorder
Depth first algorithm
- PUSH the first node onto the stack
- Repeat:
a. push each node onto the stack until a child node is reached
b. visit the node which is the lowest you can reach
c. if no node to visit pop off the stack - Until stack is empty
Breadth first algorithm
- PUSH the first node into the queue
- mark as visited
- REPEAT:
a. visit all unvisited nodes connected to the first node
b. push nodes onto the queue - until all nodes visited
- REPEAT:
a. POP next node from queue
b. REPEAT:
i. visit unvisited nodes connected to current node
ii. PUSH nodes onto quue
c. until all nodes visited - until queue empty
Preorder
- starts at root
- traverses the left sub tree
- traverses the right sub tree
In order
- Traverses the left sub tree
- visits the root
- traverses the right sub tree
Postorder
- Traverses the left sub tree
- traverses the right sub tree
- return to the root node
preorder dot
dot left
inorder dot
dot below
post order dot
dot right
beneficial characteristics of hashing algorithms
- quick to calculate
- minimizes the collisions
- provides a smaller output than input
similarities / differences between array and linked list
- linked list is dynamic but array is static
- an array can have an element accessed directly whereas a linked list needs to be traversed until the desired element is found
- contents of array stored contiguously in memory whereas for linked lists its just in the order inputted
use of visualisation in data structures
a graph is an abstract data structure which is actually an array. However, it easier to visualise and understand a graph making the coding easier to tackle.
Uses of stacks in computer systems
- Temporarily storing the contents of registers while handling an interrupt
- Storing return addresses (during subroutine calls)
- Traversing a Graph data structure
- Passing parameters
- Reversing the order of a set of data
error when you try and add a data item to an already full structure
overflow
typical uses of graphs
- mapping data trasnmission
- Webpage links
- social media trends
