Definition
- A List is a linear data structure holding an ordered sequence of elements, where each element has a position (index) — fundamental abstract data type (ADT) underlying many other structures
Types of Lists
- Array-based (static) list — contiguous memory, O(1) random access, O(n) insertion/deletion (shifting required)
- Singly Linked List — each node points to the next; O(1) insertion/deletion at head, O(n) access
- Doubly Linked List — nodes have both next and previous pointers; allows backward traversal, easier deletion
- Circular Linked List — last node points back to first, useful for round-robin scheduling, buffering
Array vs Linked List (classic comparison table)
| Feature |
Array |
Linked List |
| Memory |
Contiguous |
Scattered (dynamic) |
| Access time |
O(1) |
O(n) |
| Insertion/Deletion |
O(n) (shift needed) |
O(1) (if position known) |
| Memory overhead |
None extra |
Pointer storage per node |
| Size |
Fixed (static array) |
Dynamic |
Core List Operations
- Insert (at head/tail/position), Delete, Traverse, Search, Update
Exam Angle
A very common question: "When would you prefer a linked list over an array?" — answer: frequent insertions/deletions, unknown/variable size at compile time. Reverse: prefer array for frequent random access.
📌 Sample & Repeated FPSC Questions (2016–2026)
2026, Paper I, Q3(b) (6 marks) — What are arrays? Describe one advantage and one limitation.
An array is a linear data structure storing a fixed-size, ordered collection of same-type elements in contiguous memory, accessed directly by index.
- Advantage: constant-time O(1) random access — the address of any element is computed directly as
base_address + index × element_size, so access time is independent of array size.
- Limitation: fixed size — growing an array at runtime means allocating a new, larger array and copying everything over (O(n)). Mid-array insertion/deletion is also O(n) because later elements must shift — this is exactly where a linked list wins.
Key reasoning points:
- Arrays trade flexibility for speed; linked lists trade speed (of access) for flexibility (of size/insertion) — this is the core contrast this page's comparison table captures.