| Structure | Access | Insert | Delete | Space | Key Feature |
|---|---|---|---|---|---|
| Array (static) | O(1) | O(n) | O(n) | O(n) | Fixed size; random access by index |
| Linked List | O(n) | O(1)* | O(1)* | O(n) | Dynamic; no random access; pointers |
| Stack | O(1) | O(1) | O(1) | O(n) | LIFO; push/pop from one end only |
| Queue | O(1) | O(1) | O(1) | O(n) | FIFO; enqueue rear, dequeue front |
| BST | O(log n)* | O(log n)* | O(log n)* | O(n) | Sorted; in-order traversal gives sorted output |
| Hash Table | O(1)* | O(1)* | O(1)* | O(n) | Fastest average; needs collision handling |
| Graph (adj. matrix) | O(1) | O(1) | O(1) | O(V²) | Fast edge lookup; wastes space for sparse graphs |
| Graph (adj. list) | O(deg) | O(1) | O(deg) | O(V+E) | Space efficient for sparse graphs |
* Average case — worst case may differ (e.g. unbalanced BST degrades to O(n))
Stack (top → bottom)
Insert values one at a time. Left subtree < node < right subtree. Click "In-order Traversal" for sorted output.
Each node contains a data value and a pointer to the next node. Dynamic — grows/shrinks at runtime. No random access.
42
→ next
17
→ next
93
→ None
Advantages
Disadvantages
1. Compare an adjacency matrix and an adjacency list as representations of a graph. Refer to storage space and time to check if an edge exists. [4 marks]
Mark scheme:
2. Describe the process of inserting the values 15, 8, 20, 5, 12 into a binary search tree, starting from an empty tree. State the position of each value as it is inserted. [4 marks]
Mark scheme:
3. Explain why a hash table can achieve O(1) average time for data retrieval. [3 marks]
Mark scheme:
4. Describe one disadvantage of using a static array to implement a stack compared to using a linked list. [2 marks]
Mark scheme: