Lists (2016)

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

1. Array-based (static) list — contiguous memory, O(1) random access, O(n) insertion/deletion (shifting required)
2. Singly Linked List — each node points to the next; O(1) insertion/deletion at head, O(n) access
3. Doubly Linked List — nodes have both next and previous pointers; allows backward traversal, easier deletion
4. Circular Linked List — last node points back to first, useful for round-robin scheduling, buffering

Array vs Linked List (classic comparison table)

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.

---

2024, Paper I, Q6(c) (6 marks) — Write an algorithm that deletes a specified cell from a doubly linked list. Draw a picture that shows the process graphically.

struct Node {
    int data;
    Node* prev;
    Node* next;
};

void deleteNode(Node*& head, Node* delNode) {
    if (head == nullptr || delNode == nullptr) return;

    if (head == delNode)
        head = delNode->next;                 // update head if deleting the first node

    if (delNode->next != nullptr)
        delNode->next->prev = delNode->prev;  // bypass delNode from the right

    if (delNode->prev != nullptr)
        delNode->prev->next = delNode->next;  // bypass delNode from the left

    delete delNode;                           // free the memory
}

Graphical trace — deleting node B from A ↔ B ↔ C:

Before:            [A] <-> [B] <-> [C]

Step 1 (relink):   A.next -> C,  C.prev -> A
                   [A] -------------> [C]
                   [A] <------------- [C]
                   (B still exists but is now bypassed)

Step 2 (free B):   B's own prev/next links are discarded; its memory is released.

After:             [A] <-> [C]

Key reasoning points:

• Deletion is O(1) given a pointer directly to the node — only a constant number of pointers need updating. This is the doubly-linked-list advantage over an array, where the same deletion costs O(n) due to shifting.

---

2018, Paper I, Q5(b) (5 marks) — What data structure would you employ to build a text editor and why?

A Doubly Linked List (or, in production editors, a Gap Buffer / Piece Table) — each character or line is a node with prev/next pointers, plus a cursor pointer marking the current edit position.

Exam angle: Text editing is dominated by insertions/deletions at the cursor, not random access by index. A doubly linked list does cursor-position insert/delete in O(1) (given the cursor pointer), vs an array/string's O(n) shift-based insert/delete. The "doubly" part additionally allows O(1) cursor movement in both directions. This is the same "prefer linked list when insertions/deletions dominate" reasoning already noted in this page's Exam Angle box — just applied to a concrete real-world system.

---n## Array vs Matrix OperationsnAn array is a linear, homogeneous collection of elements accessed via a single index (a[i]); a matrix is essentially a 2-dimensional array, accessed via two indices (a[i][j], row and column) — the natural structure for tabular/mathematical data.nArray operations (traversal, insertion/deletion with shifting, linear/binary search, sorting) all work along a single dimension in O(n) or O(log n) depending on the operation — see this page's sections above and the Searching & Sorting page.nMatrix operations are richer because of the second dimension:nnOperationRequirementComplexitynAddition / SubtractionSame dimensions (m×n)O(m·n) — element-wisenMultiplicationColumns of first = rows of secondO(m·n·p) for an (m×n)·(n×p) product — each result element is a dot product of a row and a columnnTransposeNoneO(m·n) — swap rows and columnsnTraversalNoneO(m·n) — usually nested loops (row-major or column-major order) instead of a single loopnnIn memory, a matrix is normally stored internally as a single 1-D array (row-major or column-major layout), with the address of a[i][j] computed via a formula (e.g., row-major: base + (i·n_cols + j) × element_size) — so despite being conceptually 2-D, matrix operations ultimately reduce to array-style linear memory access with index arithmetic, same as the rest of this page.n### Exam AnglenA "short note" question — the examiner wants the array/matrix relationship stated explicitly (matrix = 2-D array), plus the multiplication dimension-compatibility rule and its O(m·n·p) cost, which is the detail most often forgotten.n## 📌 More Sample & Repeated FPSC Questionsn2016, Paper II, Q7(a) (6 marks) — Write down a short note on Array versus Matrix Operations.nModel answer: see the definition and operations table above. Key points to include: a matrix is fundamentally a 2-D array; addition/subtraction require matching dimensions; multiplication requires the inner dimensions to match (columns of A = rows of B) and costs O(m·n·p); and despite the 2-D conceptual model, matrices are stored and addressed as flat 1-D memory underneath, via row-major or column-major index arithmetic.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2018 · Paper-I · Q5(b) · 5 marks

Q. What data structure would you employ to build a text editor and why?

Ans.

• A doubly linked list of lines (each line holds its text) is a good choice. Inserting or deleting a line is O(1) once the position is known, and the editor can move up and down using prev and next pointers.
• Within a line, use a gap buffer (or a rope) so typing at the cursor is fast without shifting the entire text.
• Undo and redo use two stacks of past operations.
• Why not an array: inserting in the middle of an array needs shifting all later elements (O(n)).

2024 · Paper-I · Q6(c) · 6 marks

Q. Write an algorithm that deletes a specified cell from a doubly linked list. Draw a picture showing the process.

Ans.

deleteNode(head, X):
    if X == null: return
    if X.prev != null:  X.prev.next = X.next     // skip X going forward
    else:               head = X.next            // X was the first node
    if X.next != null:  X.next.prev = X.prev     // skip X going backward
    free(X)

Before:  A <-> X <-> B
After :  A <-> B          (X is bypassed and freed)

• Time O(1) when the node pointer is known (O(n) if it must first be found).

MCQs

2024 P-I · Q19. What is the name of a linear collection of data components where the linear order is provided by pointers?

• (A) Linked list ✅
• (B) Primitive List
• (C) Node list
• (D) None of these
• Answer: (A) Linked list.
• Why: in a linked list each node stores data and a pointer to the next node, and the pointers give the order. An array gets its order from consecutive memory positions. "Primitive list" and "node list" are not standard data-structure names.

2024 P-I · Q20. How much time would it take to add an element to a linked list asymptotically?

• (A) O(1) ✅
• (B) O(n)
• (C) O(n²)
• (D) None of these
• Answer: (A) O(1).
• Why: inserting at the head only needs a new node and a pointer change, which does not depend on the length of the list. (Inserting at the end without a tail pointer, or searching for a position, would be O(n).)

2025 P-I · Q17. How is the head node deleted in a doubly circular linked list?

• (A) By adjusting the prev pointer of the new head node to null
• (B) By setting the next pointer of the prev node to point to the new head ✅
• (C) By pointing the next pointer of the last node to null
• (D) None of these
• Answer: (B).
• Why: in a circular list nothing points to null. The last node must now point to the new head (its next), and the new head's prev must point back to the last node. Options (A) and (C) describe a non-circular list.