Data Structures Flashcards
(136 cards)
1
Q
Data Type
A
Defines potential set of values a variable can hold and the operations that can be performed on it
2
Q
Aspects of Data types
A
- Range of values
- Size of memory required
- How binary data is interpreted
- Operations that can be performed on it
3
Q
Abstract Data Type (ADT)
A
Conceptual model of how data is to be stored and the operations that can be carried out on it
4
Q
Data Structure
A
- (Partial) implementation of user-defined types (ADTs)
- Each item known as member and can be of different data types
5
Q
Purpose of data structures
A
To combine multiple data items under a single identifier
6
Q
Key ADTs
A
- Stacks
- Queues
- Graphs
- Trees
- Hash tables
7
Q
Static data structures
A
- Max size fixed at compilation
- Data stored in contiguous memory locations
8
Q
Advantages of static data structures
A
- Fast to access
- (Sometimes) require less memory
9
Q
Disadvantages of static data structures
A
- Inflexible
- (Sometimes) wastes space
- Operations like insertion and deletion are very slow
10
Q
Dynamic data structures
A
- Can change size at run-time
- Data not (usually) stored contiguously
- Each item points to the next item in the structure
11
Q
Advantages of dynamic data structures
A
- More flexible
- No wasted space or limits
- (Sometimes) require less memory
12
Q
Disadvantages of dynamic data structures
A
- (Sometimes) require more memory (have to store pointers)
- Slower to access
13
Q
Queue
A
Data structure comprised of sequence of items and front and rear pointers
14
Q
Order of item insertion in Queue
A
Items added at rear and retrieved from front in First-in-First-Out (FIFO)
15
Q
Key operations of Queue
A
- Enqueue
- Dequeue
- isEmpty
- isFull
16
Q
Enqueue
A
If not isFull() then add new item to rear
17
Q
Dequeue
A
If not isEmpty() then remove front item
18
Q
isFull
A
Test whether queue is full
19
Q
isEmpty
A
Test whether queue is empty
20
Q
Uses of queues
A
- Queues of print jobs
- Managing input buffers
- Handling multiple file downloads
- Priority-based resource allocation
- …
21
Q
Queue implementations
A
- Linear queues
- Circular queues
- Priority queues
22
Q
Linear queues
A
- Stores items in ‘line’
- Front and rear pointers move down memory
23
Q
Advantages of linear queues
A
- Simple to program
- Limited capacity useful when representing finite resources
24
Q
Disadvantages of linear queues
A
Wasted capacity (whole queue shifts down)
25
Solving waste problem in linear queue
- Shuffling every item one index forward when first item deleted
- However, it's inefficient (O(n))
26
Circular queues
- 'Wraps' front and rear pointers using MOD function
- Static, array-based
27
Advantages of circular queues
- Avoids wasting space
- No need for shuffling
28
Disadvantage of circular queue
More complex to program
29
Priority queue
Items enqueued (or dequeued) based on priority
30
Priority queue implementations
- Can be implemented statically using a 2D array
- More efficient to implement dynamically, with each node storing value and priority
31
Disadvantages of static priority queue
- Inherent drawbacks of static (e.g. space limitation)
- However, dequeue and enqueue time is still O(n) since linear search required to find highest priority
32
Stack
- Comprised of **sequence of item**s and **stack pointer** that **points to top** of stack
- **Last-in-First-Out (LIFO)** - items added to top and removed from top
33
Stack structure
int maxSize;
int items[maxSize];
int stackPointer = -1;
34
Stack operations
- Push
- Pop
- Peek
- isFull
- isEmpty
35
Push
If not isFull, push value to top of stack
36
Pop
If not isEmtpy, returns value at top of stack and removes it
37
Peek
Returns item at top of stack (doesn't remove it)
38
Uses of stack
- Reversing sequence of items
- Storing stack frames
- Storing processor state when handling interrupt
- Evaluating mathematical expressions written in Reverse Polish (postfix) notation
39
Stack overflow
Attempt to push item when stack is full
40
Stack underflow
Attempt to pop item when stack is empty
41
Call stack
Area of memory used to store data used by running processes and subroutines
42
Stack frame
- **Return addresses** (keeps reference to parent subroutine)
- **Parameter values** (keeps parameter values of different subroutines separate)
- **Local variables** (isolates these from rest of system)
43
Call stack pushing and popping
- Stack frame is pushed with each new subroutine call
- Stack frame popped when process completes
44
Linked list
Dynamic data structure comprised of **nodes** that **point to its consecutive node** in the list
45
Aims of linked lists
- Convenience of storing multiple values per element
- Flexibility to grow
- Quick at inserting and deleting items (no shuffling)
46
Disadvantages of linked lists
- Slower to access items (traversal)
- Takes up more memory (each node store value + 64 bit pointer)
47
Graphs
Set of nodes connected by edges
48
Directed vs undirected graph
- In directed, edges can be unidirectional
- In undirected, all edges are bidirectional
49
Weighted graph
Edges have a cost of traversing (e.g. time)
50
Purpose of graphs
Modelling complex relationships between interralated entities
51
Uses of graphs
- Human (social) networks
- Transport networks
- Computer networks
- Planning telecommunication networks
- Project management
52
Typical graph operations
- Adding / removing node
- Adding / removing edge
- Test edge existence
- Get edges / adjacent nodes
- Get weight of edge
53
Implementations of graphs
- Adjacency matrix (static)
- Adjacency list (dynamic)
54
Adjacency matrix
Edges between nodes represented by '1' at intersection in matrix
E.g. if edges[0][1] == 1, then there is an edge between node 0 and node 1
55
Representing direction in adjacency matrix
- From and to index must be predefined and consistent throughout
- **Unidirection** = edges[0][1] == 1, but edges[1][0] == 0
56
Representing weights in adjacency matrix
Store weight at intersection or NULL for no edge
57
Size of adjacency matrix
N^2 (where n = no. nodes)
58
Advantages of adjacency matrix
- Edges can be quickly identified in O(1) time
- Optimised for dense graphs (many edges that need updating) due to O(1) look-up
- Simple implementation using 2D array
59
Disadvantages of adjacency matrix
- More memory required ( Mathjax )
- Less efficient insertion and deletion (limited space or shuffling -> O(n))
- If sparse graph, matrix is sparsely populated -> Wasted space
60
Adjacency list
Array of nodes (representing every node) pointing to list of adjacent nodes
61
Size of adjacency list
N + E (where N = no. nodes & E = no. edges)
62
Implementing adjacency list
- **Python** - dictionary
- **C** - linked list and pointers
63
Representing direction in adjacency list
edges[A] → B but edges[B] doesn't → A
64
Representing weight in adjacency list
Each node in linked list stores weight
65
Advantages of adjacency list
- Requires less memory (data only stored where edges exist)
- Easier and quicker to insert/delete nodes (no shuffling)
- Optimised for sparse graphs (fewer edges and frequent adding and deletion of nodes)
66
Disadvantages of adjacency list
- Slower to test presence of edge (traversal = O(n))
- Harder to implement
- Less optimised for dense graph (more edges → more nodes in lists → slower traversal and more memory)
67
Graph traversal methods
- Depth-first
- Breadth-first
68
Depth-first
- Traverse one whole route before exploring breadth
- Recursively visits adjacent nodes from a given starting point until there are no adjacent nodes left, at which point the function returns
- Uses a stack (automatically implemented via call stack) to maintain FIFO order
69
Uses of depth-first traversal
- Solution to maze (when modelled as graph)
- Find valid path between nodes (not shortest path)
- Determining order of dependent processes (e.g. module compilation)
70
Breadth-first
- Visits all adjacent node before exploring depth
- Uses queue to maintain LIFO order of visiting
71
Uses of breadth-first traversal
- Identifiying friends in social networks
- Finding immediately connected devices and networks
- Crawling web pages to build index of linked pages
72
Tree
A connected, undirected graph with no cycles
73
Purposes of trees
- Manipulating and storing hierachical data (e.g. folder structures)
- Making information easy to search
- Manipulating sorted lists of data
74
Uses of trees
- Processing syntax
- Huffman trees
- Implementing probability and decision trees
75
Root
Node that has no incoming edges
76
Child
Node that has an incoming edge
77
Parent
Node that connects to its children nodes via outgoing edges
78
Subtree
Set of nodes and edges comprised of a parent and all its descendants
79
Leaf node
Node that has no children
80
Rooted tree
Has one node dedicated as the root
81
Binary tree
Rooted tree in which each node has a maximum of two children
82
Binary search tree
Holds items in a way that the tree can be searched quickly in O(log n) time complexity
83
Tree operations
- Determing whether node is root
- Getting list of children nodes
- Adding a child node
- ...
84
Static implementations of binary tree
- Associative arrays
- Dictionary
- Adjacency matrix
85
Associative array implementation of binary tree
- Uses 3 1D arrays
- Nodes[] - stores data values in each node
- Left[] - stores index of node to left of node represented by index number
- Right[] - stores index of node to right of node represented by index number
86
Adjacency matrix
Same as graph
87
Dictionary implementation of binary tree
- **Key** = Value stored in node (e.g. name)
- Each index stores tuples holding keys of left and right nodes
88
Dynamic implementation of Binary tree
- Double linked list of nodes
- Each node store payload value, left node pointer and right node pointer
89
Advantages of dynamic binary tree
- Quicker insertion and deletion
- Maintains O(log n) search time (even with traversal requirement)
90
Tree traversal algorithms
- Pre-order
- In-order
- Post-order
91
Pre-order traversal
1. Visit current node
2. Traverse left subtree (recurse call function on left)
3. Traverse right subtree (recurse call function on right)
92
In-order traversal
1. Traverse left subtree
2. Visit current node
3. Traverse right subtree
93
Post-order traversal
1. Traverse left subtree
2. Traverse right subtree
3. Visit current node
94
Hand-tracing tree traversal algorithms
- Draw outline around tree, starting from left of root and ending at right of root
- **Pre-order** - place dot to left of each node
- **In-order** - place dot beneath each node
- **Post-order** - place dot to right of each node
- When outline passes node, write/output its value
95
Uses of pre-order traversal
- Copying a tree
- Evaluating mathematical expression tree using prefix notation
96
Uses of in-order traversal
Outputting contents of binary tree in ascending order
97
Uses of post-order traversal
- Converting mathematical expressions from infix to postfix
- Producing postfix notation from expression tree
- Emptying a tree
- Completing dependent processes in order (e.g. recursive functions with multiple recursive calls)
98
Key-value pair
Association of a key with a value
99
Static implementations of key-value structure
- Multidimensional array
- 2 (or more) associative arrays to store key-value pairs
100
Limitations of static key-value implementations
* Searching for key requires linear search (O(n) time complexity)
* If improved via binary search, requires costly insertion/deletion to maintain order (worse for associated arrays)
* Fixed size (wasted/limited space)
101
Hash table
ADT whose purpose is to provide an efficient means of accessing items from a large, unordered data set
102
Inserting data into hash table
* Value processed by hashing algorithm which returns hash value
* Data then placed in index specified by hash value
103
Hashing algorithm
Always outputs same when given the same input such that the output is practically unique
104
Accessing data in hash table
Get data's index by running hashing algorithm over input data again
105
AQA definition of hash table
Data structure that stores key-value pairs based on an index calculated from a hashing algorithm
106
AQA component's of hash table
* An array or multidimensional array to hold data
* Data comprised of keys paired with values
* Hashing algorithm to determine index of data
107
Advantages of hash tables
* O(1) time complexity
* Determines item’s existence without linear search
108
Collision
When a hashing algorithm generates same hash value for two or more keys
109
Collision handling methods
* Rehashing (bad)
* Linear probing (worse)
* Chaining (good)
110
Rehashing
Apply additional algorithm to original key or conflicting hash value to generate new hash value
111
Limitations of rehashing
* Increases sparsity of array → wasted space
* Knock-on effect - further collisions may occur, meaning more rehashing is needed
* Additional process → Slower insertion and searching
112
Linear probing
Looks for next available index
113
Limitations of linear probing
* No known association between key and index
* Increases potential for further collisions (knock-on)
* Promotes clustering (indices not evenly distributed)
* Items whose hash value point to shunted index have to be moved elsewhere
* Worst-case, linear search across whole table required
114
Chaining
* Store linked list at each location in hash table
* If collision, simply link item to end of list
115
Limitations of chaining
Requires some linear searching (however not too much depending on spread of items across buckets)
116
Benefits of chaining
* Can keep adding items without clustering or increasing chance of collisions
* Retains most efficiency benefits of hash tables
117
Writing good hashing algorithms
* Can handle text input
* Same hash value for a given key
* Evenly distributed hash values
* Use most of input data
* Use computationally fast operations (e.g. integer calculations)
* Handle collisions efficiently
118
Uses of hash tables
* Dictionary data structures (store key-value pairs)
* Databases (for quick storage and retrieval)
* Cache memory (determine memory address quickly)
* Operating systems (store location of apps and file for quicker access)
119
Dictionaries
Data structrues that store **collections of key-value pairs** where the value is **accessed via its associated key**
120
Dictionary operations
* Retrieving value from given key
* Inserting values with a new key
* Updating values of a given key
* Removing a key-value pair
* Testing if a key exists in a dictionary
121
Uses of dictionaries
Wherever data can be stored in a key-value relationship
122
Implementations of dictionaries
* Associative arrays
* Multi-dimensional array
* Hash table
* Binary search tree
123
Associative array implementation of dictionary
Pair of 1D arrays storing key and value
124
Multi-dimensional array implementation of dictionary
Key and paired value stored in same master index
125
Limitations of array implementations of dictionary
* Fixed size (wasted or limited space)
* Linear search required for access (O(n) complexity)
126
Hash table implementation of dictionary
Most directly echoes mapping concept
127
Limitations of hash table dictionary implementation
Application of hash algorithm "heavy" (I.e. too relatively computationally expensive) for a few key-value pairs
128
Binary search tree implementation of dictionary
Each node contains both key and paired value (sorted based on key's value)
129
Benefits of binary search tree implementation of dictionary
* O(log n) time complexity for searching
* Easy insertion and deletion
* Can grow or shrink as needed
* No need for heavy hashing algorithm
130
Vector
* Quantity with magnitude and direction
* Quantity consisting of multiple values
131
Representations of vectors
* List (1D array)
* Arrows on coordinate plain
* As functions (e.g. f(x) : S → R; f(x) = {V_0 if x = 0, V_1 if x = 1}
* As dictionaries (useful if viewed as function due to explicit mapping)
132
Vector addition
**a** + **b** = [a_x + b_x, a_y + b_y]
133
Scalar-vector multiplication
k**a** = [ka_x, ka_y]
134
Dot (scalar) product
**a** ⋅ **b** = a_x × b_x + a_y × b_y
135
Angle between vectors
**a** ⋅ **b** = |**a**||**b**|cosθ
136
Convex combination
* When sum of two vectors is a vector that sits within the convex hull
* D = ⍺**v** β**u** where ⍺, β ≥ 0, ⍺ + β = 1
