1.4.2 Data Structures Flashcards
1D Arrays
- Finite
- Ordered
- Homogenous - Only takes the same data type
- Static - Size remains the same
- Mutable - Can change/override the contents
- Store contiguously in memory
Lists
- Non-homogenous - Multiple data types
- Dynamic - Can change size
- Mutable - Can change/override the contents
- Ordered - Has a definitive first and last object
Static Vs Dynamic Data Structures
Static:
- (+) Useful if we know the amount of items stored in advance
- (+) We know at definition how much space it will hold
- (-) Limited on how we can interact with it - can populate, replace items (if mutable) and read items
Dynamic:
- (+) Useful if we don’t know the amount of items stored in advance
- (+) Can insert/remove items as well as perform functions on lists
- (-) Not know how much space it’ll take in the storage it’ll need, and if it gets too large it’ll lead to overflow errors
Tuples
- Static
- Ordered
- Non-homogenous
- Immutable (contents can’t be changed)
May be used for data that will remain unchanged
2D & 3D Arrays
- 2D - A matrix (e.g. [[1,2,3,4], [5,6,7,8], [9,10,11,12]]
- 3D - Like a cube (e.g. [[[1,2], [3,4]], [[5,6], [7,8]]]
Records
Saves data so that it can be accessed for subsequent usage
Linked Lists
- Each item represented by a node
- Each node contains 2 pieces of info: the data stored at that node and the details of the next node in the list
Types of Linked Lists
- Circular Linked Lists
- Doubly Linked Lists
- Circular Doubly Linked List
Stacks
- Last in first out data structure (LIFO)
- Items can only be added to or removed from the top of the stack
- May have a “head” which can point to either the top item of the stack or the free space above this top item
- Can be static or dynamic, depending on whether or not they were implemented using a list or an array
Methods For A Stack
- Pop() - Removes top item
- Push(item) - Adds an item to the top of the stack
- Peek() - Returns the top item of the stack
- isFull() - Returns True if the stack is full
- isEmpty() - Returns True if the stack is empty
- Size() - Returns the size of the stack
Uses of Stacks
- ‘Undo’ buttons in applications
- Storing web browser history
Queues
- A first in first out (FIFO) data structure (Remove from the front of the queue (head) and add to the back of the queue (tail))
- Will have a “head” and a “tail” to point to the front and back of the queue respectively
- The tail may point to either the last item in the queue or the free space after the last item
- Can be static or dynamic
Queue Methods
- enQueue(item) - Adds an item to the end of the queue
- deQueue() - Removes the item at the front of the queue
- isEmpty() - Returns True if the queue is empty
- isFull() - Returns True if the queue is full
Queue Uses
- Printers
- Keyboards
- Simulators
Circular Queues
In these types of queues, the tail loops back around to the start (if there’s a free space)
Graphs
- Contain vertices/nodes and edges/arcs
- Either undirected (bidirectional) or directed (have a specific direction for each edge/arc)
- Weighted (values assigned to edges) or unweighted (no values assigned)
- Dense (when most vertices are directly connected to every other vertex) or sparse (most vertices not directly connected)
How do computers process them?
Using an:
- Adjacency Matrix
- Adjacency List
How do adjacency matrices differ between weighted and unweighted graphs?
For unweighted graphs, you put 1’s and 0’s in each box depending on whether there is or isn’t an edge between the 2 vertices
For weighted graphs, you put the weight of the edge into the box between the edge’s corresponding vertices
How can you tell if a graph is undirected using an adjacency matrix?
It’ll be symmetrical across a diagonal line from the top left to the bottom right.
How do adjacency lists differ between a weighted and unweighted graph?
(Implement these lists using dictionaries in python)
Weighted (Undirected) Example:
A: {B:4, C:18}
B: {A:4, C:5}
C: {A:18, B:5}
Unweighted (Undirected) Example:
A: [B, C]
B: [A, C]
C: [A, B]
Adjacency Matrices Vs Adjacency Lists
Matrix Advantages:
- Convenient to work with due to quicker access times
- Easy to add nodes
List Advantages:
- More space efficient for large, sparse networks
What Are The Types of Graph Traversal?
- Breadth First Search (BFS) - Searches within a radius of sorts
- Depth First Search (DFS) - Searches in a certain direction until an end point is found, jumps back to origin if there’s a dead end
Breadth First Search (BFS)
- From the starting vertex, visit all vertices 1 edge away
- Then visit all vertices 2 edges away
- Then visit all vertices 3 edges away etc.
- Implemented using a queue
How is a BFS implemented with a queue?
- Create a queue with just the first vertex in it
- Add the vertices that are 1 edge away from the current vertex to the list
- DeQueue the current vertex and move onto the next one
- Repeat steps 2 & 3 until complete
Pros & Cons of BFS
Pros:
- No issues with loops in graphs
- Can help find the shortest route between 2 vertices
Con:
- Can be slower then a DFS
Depth First Search (DFS)
- Keep going until there’s an end point
- When there’s a choice of edges, you can pick one as long as you’re consistent
- Implemented using a stack
Pros & Cons of DFS
Pro:
- Has the potential to be faster than a BFS
Con:
- Prone to error if there is a loop in the graph and the DFS isn’t implemented properly
Trees
A connected form of a graph consisting of:
- Nodes - an item in the tree
- Edges - Connects two nodes together, also known as a branch or an arc
- Root - A single node which does not have any parent node or incoming edges
- Child - A node with incoming edges
- Parent - A node with outgoing edges
- Subtree - A subsection of a tree consisting of a parent and all the children of a parent
- Leaf - A node with no children
Types of DFS
- Inorder - Left, root, right
- Preorder - Root, left, right
- Postorder - Left, right, root
Preorder DFS
Similar to a regular DFS for graphs
- Start at the root node
- Follow the leftmost path until you reach a leaf
- Backtrack and make a different decision
*Useful for copying trees
Inorder DFS
Returns the tree as it reads left to right
- Start from the leftmost leaf (leftmost node on binary trees)
- Go to parent node
- Does it have an unexplored child node?
- If so, select the leftmost child node and find the child’s leftmost leaf
- Repeat until the whole tree is traversed
*Useful for returning order of a Binary Search Tree
Postorder DFS
Start at the leaves and work inward
- Start at the leftmost leaf
- Find the leaves from the sibling node
- Work up the tree, starting from the leaves
- Children should always be returned before parents
*Useful for deleting the tree
Breadth First Search (Trees)
- Start with the root node
- Visit its children
- Then grandchildren
- Then great grandchildren
- Continue until all the leaves are reached
*Useful for returning items from a tree in order of seniority
Binary Trees
- Type of tree/graph
- At most 2 child nodes
(Binary Search Tree - Data added in such a way that it allows for fast searching)
How Do You Arrange A Binary Tree?
- First value is the root
- Check if the next value is higher or lower than available parent node
- If value is lower, put it to the left of the previous value
- If value is higher, put it to the right of the previous value
- Repeat until list is fully gone through
How do you remove a node with no children in a binary tree?
Locate and delete it
How do you remove a node with 1 child in a binary tree?
Locate and delete it, then its child takes its place
How do you remove a node with 2 children in a binary tree?
Locate and delete node, then its rightmost child takes its place. Its leftmost child then becomes the child of its rightmost.
How do you remove the root from a binary search tree?
Delete the root, and then the next item in the order would take its place (e.g. if 2 was the root, then 2 would be deleted and 3 would take its place, even if it wasn’t a direct child of the root)
