Data Structures
Arrays, records, lists, tuples, stacks, queues, linked lists, graphs, trees and hash tables, with the operations and when to choose each.
Linear structures
Arrays, records, lists and tuples
| Structure | Properties |
|---|---|
| Array | Fixed size, same data type, contiguous memory, direct access by index in constant time |
| Record | Fixed set of named fields of possibly different types, a row in a file |
| List | Ordered, may hold mixed types, dynamic size, may not be contiguous |
| Tuple | Ordered and immutable once created |
An array's index calculation is base address + index x element size, which is why access is constant time and why elements must all be the same size.
Stacks
Last in, first out. Operations: push, pop, peek, isEmpty, isFull.
procedure push(item)
if top == maxSize - 1 then
return "Stack overflow"
endif
top = top + 1
stack[top] = item
endprocedure
function pop()
if top == -1 then
return "Stack underflow"
endif
item = stack[top]
top = top - 1
return item
endfunctionUses: the call stack holding return addresses and local variables, undo functionality, evaluating reverse Polish notation, backtracking, and depth first search.
Queues
First in, first out. Operations: enqueue, dequeue, isEmpty, isFull.
A linear queue wastes space as the front pointer advances. A circular queue solves this by wrapping the pointers using modulo arithmetic:
rear = (rear + 1) MOD maxSize
A priority queue dequeues the highest priority item rather than the oldest.
Uses: print spoolers, keyboard buffers, process scheduling, breadth first search.
Linked lists
Each node holds data and a pointer to the next node. A separate pointer marks the start, and a null pointer marks the end.
| Array | Linked list | |
|---|---|---|
| Memory | Contiguous | Anywhere, connected by pointers |
| Size | Fixed at creation | Grows and shrinks dynamically |
| Access | Direct by index, constant time | Must traverse from the start, linear time |
| Insertion in the middle | Requires shifting every later element | Change two pointers |
| Overhead | None | A pointer stored per node |
Insertion is the key difference. Inserting into the middle of an array of a million elements means moving up to a million items. In a linked list it means changing two pointers.
- A stack is a pile. New items go on the top.
- Push another one and it goes on top again.
- Pop takes the top one off, so the last in is the first out.
- A queue is a line. New items join the back.
- Dequeue takes from the front, so the first in is the first out.
- Infix has the operator between the numbers and needs brackets. Postfix puts the operator after them.
- Numbers are pushed on the stack. An operator pops two values, applies itself and pushes the result.
- When the tokens run out, the single value left on the stack is the answer.
Trees, graphs and hash tables
Graphs
A set of vertices connected by edges. Edges may be directed or undirected, and weighted or unweighted.
Adjacency matrix. A two dimensional array where entry (i, j) records an edge from i to j.
- Constant time to check whether an edge exists
- Uses n2 space regardless of how few edges there are, so it wastes memory on sparse graphs
- Better for dense graphs
Adjacency list. Each vertex stores a list of its neighbours.
- Space proportional to the number of edges, so far more efficient for sparse graphs
- Checking a specific edge requires searching a list
- Better for sparse graphs
Uses: road and rail networks, social networks, the web, dependency graphs, state machines.
Trees
A connected acyclic graph with a root, parent and child nodes, and leaves with no children.
A binary search tree keeps values ordered: everything in the left subtree is smaller than the node, everything in the right subtree is larger.
- Search, insert and delete average O(log n)
- Degenerates to O(n) if items are inserted in sorted order, producing a linked list
- Self balancing trees avoid this
Traversals
procedure preOrder(node) // node, left, right - copying a tree
procedure inOrder(node) // left, node, right - visits in sorted order
procedure postOrder(node) // left, right, node - deleting, or postfix expressionsIn order traversal of a binary search tree outputs the values in ascending order. This is examined frequently.
Hash tables
A hash function maps a key to an index in an array, giving average constant time insertion and lookup.
A collision occurs when two keys hash to the same index.
- Separate chaining. Each slot holds a list of all items hashing there. Simple, and degrades gracefully.
- Open addressing or linear probing. On collision, try the next free slot. No extra structures, but causes clustering which degrades performance.
The load factor is the number of items divided by the number of slots. As it rises, collisions become frequent and performance falls, so the table is rehashed into a larger array when it passes a threshold, typically around 0.7.
Frequent lookup by key means a hash table. Ordered data needing range queries means a binary search tree. Frequent insertion in the middle means a linked list. Fixed size with index access means an array.
- A binary tree: every node has at most two children.
- In a binary search tree, smaller goes left and larger goes right.
- Searching for 37: start at the root and compare.
- 37 is less than 50, so go left. More than 30, so go right. Found.
- Three comparisons for seven items. That is why trees are fast.
- Four keys to store: Ada, Bob, Zed and Eve.
- The hash function turns each key into a bucket number, for Ada 65 + 100 + 97 = 262, and 262 mod 8 = 6.
- Each key is stored in its bucket. Bob and Zed both give 3, which is a collision, so they are chained in the same bucket.
Key terms you must be able to define
- Array
- A fixed size collection of items of the same type in contiguous memory, accessed by index.
- Record
- A structure holding a fixed set of named fields, which may be of different types.
- Tuple
- An ordered collection that cannot be changed after creation.
- Stack
- A last in first out structure supporting push and pop.
- Queue
- A first in first out structure supporting enqueue and dequeue.
- Circular queue
- A queue whose pointers wrap around using modulo arithmetic to avoid wasting space.
- Linked list
- A structure of nodes each holding data and a pointer to the next node.
- Graph
- A set of vertices connected by edges, which may be directed or weighted.
- Adjacency matrix
- A two dimensional array recording which vertices are connected.
- Adjacency list
- A representation where each vertex stores a list of its neighbours.
- Binary search tree
- A tree where the left subtree holds smaller values and the right subtree larger ones.
- In order traversal
- Visiting left subtree, node, then right subtree, which outputs a BST in ascending order.
- Hash table
- A structure using a hash function to map keys to array indexes for constant time access.
- Collision
- Two keys hashing to the same index in a hash table.
- Load factor
- The ratio of stored items to available slots in a hash table.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
- Justify a data structure choice by the operations the scenario performs most
- Compare arrays and linked lists on access time and insertion cost, with the reason for each
- Explain adjacency matrix against adjacency list in terms of sparse and dense graphs
- Know that in order traversal of a BST yields sorted output, and that a sorted insertion order degenerates it
- Explain collision resolution and why the load factor triggers rehashing
Mistakes that cost marks here
- Saying a linked list is faster than an array. Access is slower, insertion in the middle is faster.
- Forgetting that a binary search tree degenerates to a linked list if data is inserted in sorted order.
- Confusing the traversal orders. In order gives sorted output from a BST.
- Using an adjacency matrix for a sparse graph, which wastes enormous amounts of memory.
- Saying hash tables are always constant time. That is the average case, and it depends on the load factor and the hash function.
A hash table gives average constant time lookup regardless of size, which is why a dictionary with ten items and one with ten million behave almost identically. Everything depends on the hash function distributing keys evenly.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LA stack is last in first out
- LA queue is first in first out
- LGives a valid stack use such as the call stack or undo
- LGives a valid queue use such as a print spooler or scheduling
A stack operates on a last in first out basis, so the most recently pushed item is the first one removed by a pop, and only the top of the stack is directly accessible. A queue operates on a first in first out basis, so items are dequeued in the order they were added and access is at both ends, adding at the rear and removing from the front. A stack is used for the call stack in a running program, where each function call pushes a return address and local variables that must be restored in exactly the reverse order as calls return, and it is equally the natural structure for undo functionality. A queue is used for a print spooler, where jobs must be printed in the order they were submitted so that no user is unfairly delayed by someone who submitted later.
- LAn array occupies contiguous memory, a linked list does not
- LAn array has a fixed size, a linked list can grow and shrink dynamically
- LArray elements are accessed directly by index in constant time
- LA linked list must be traversed from the start, so access is slower
- LInserting into the middle of an array requires shifting subsequent elements
- LInserting into a linked list only requires changing pointers
An array stores its elements in a contiguous block of memory, all of the same type and size, which allows the address of any element to be calculated directly from the base address and the index, giving constant time access to any position. Its size is fixed when it is created, so it cannot grow, and inserting an element into the middle requires every subsequent element to be shifted one position along, which on a large array is extremely expensive. A linked list stores each element in a node that may be located anywhere in memory, together with a pointer to the next node, so the list can grow and shrink at run time as nodes are created and destroyed. The cost of that flexibility is access time: there is no way to calculate the address of the nth item, so the list must be traversed from the head following pointers, which takes time proportional to the position. In exchange, inserting or deleting in the middle requires only that two pointers be reassigned, with no data movement at all. Each node also carries the memory overhead of its pointer, which an array does not. The choice therefore depends on the workload: arrays suit data that is read by index and rarely restructured, while linked lists suit data that is frequently inserted into and removed from.
- LA hash function converts the key into an array index
- LThe item is stored at and retrieved from that index directly
- LNo search of the structure is required, so lookup time does not depend on the number of items
- LA collision occurs when two keys hash to the same index
- LDescribes chaining or linear probing as a resolution method
A hash table achieves fast lookup by applying a hash function to the key, which deterministically converts it into an index within the underlying array. The item is stored at that index when inserted, and on retrieval the same hash function is applied to the search key to produce the same index, so the item is found by a single direct array access without searching any part of the structure. Because the position is calculated rather than searched for, the time taken does not grow as the number of stored items increases, giving average constant time performance. A collision occurs when two different keys produce the same index. One resolution method is separate chaining, in which each slot in the array holds a linked list rather than a single item, and any keys hashing to that slot are appended to its list. Lookup then hashes to the slot and searches only that short list, and performance degrades gracefully as the table fills. The alternative, linear probing, stores the colliding item in the next free slot instead, which avoids extra structures but tends to produce clusters of occupied slots that lengthen future searches.
- LRecommends a hash table
- LThe customer ID is a unique key suited to hashing
- LThe hash function calculates the position so no search is needed
- LLookup is average constant time regardless of the number of records
- LCompares favourably with alternatives such as a linear search or a tree
A hash table is the right structure here. Each customer has a unique ID, which is precisely the kind of key a hash table is designed around, and the required operation is repeated lookup by that key rather than ordered traversal or range queries. The hash function converts the customer ID directly into an array index, so the record is retrieved by a single array access with no searching whatsoever, and crucially the time taken does not grow as the number of records increases, so retrieval from ten million records is essentially as fast as from ten. The alternatives are markedly worse for this workload. A linear search through an unsorted array would examine on average half of the several million records for every lookup, which is completely impractical at any volume of queries. A binary search tree would give logarithmic performance, requiring around twenty three comparisons for eight million records, which is far better than linear but still substantially slower than a single calculated access, and it would degrade badly if the IDs happened to be inserted in sorted order. The hash table's costs are that it does not maintain any useful ordering and that performance depends on a good hash function and on rehashing when the load factor rises, but since the requirement is purely lookup by unique key, neither of those is a meaningful drawback.
- LAn adjacency matrix is a two dimensional array recording whether each pair of vertices is connected
- LAn adjacency list stores for each vertex a list of the vertices it connects to
- LA matrix uses space proportional to the square of the number of vertices regardless of edges
- LA list is preferable for sparse graphs and a matrix for dense graphs or frequent edge checks
An adjacency matrix represents a graph as a two dimensional array in which the entry at row i and column j records whether an edge exists from vertex i to vertex j, and in a weighted graph holds the weight of that edge. An adjacency list instead stores, for each vertex, a list of the vertices it is directly connected to. The essential difference is space. A matrix requires storage proportional to the square of the number of vertices whether or not the edges exist, so a graph of ten thousand vertices needs a hundred million entries even if only a few thousand edges are present. An adjacency list uses space proportional to the number of edges actually present. A matrix is therefore preferable for dense graphs, where most possible edges exist so little space is wasted, and where the ability to check whether a specific edge exists in constant time matters. An adjacency list is preferable for sparse graphs, which is the far more common case in practice, since real road networks, social networks and dependency graphs all have far fewer edges than the theoretical maximum.