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
