19 Python Chapter 8.1–8.3 — collections and linked lists

Python Chapter 8.1–8.3 — collections and linked lists

← Index · Solutions

Priority key · Priorities guide emphasis; they do not remove taught scope.

Exam recall

Draw head, current, previous and next. Preserve the successor before changing a link. Handle empty, head, last node and missing target explicitly.

ADT versus implementation priority/medium

The links determine order. Nodes do not need to occupy neighbouring array cells or memory positions. Head tells you where to start; each next link tells you which node follows. If a link is overwritten before its old destination is saved, the rest of the sequence can become unreachable.

An abstract data type specifies the data’s behaviour and allowed operations, independently of its storage implementation. A list ADT might allow insertion, removal and traversal; a linked list implements a sequence using nodes and links. “Linked” does not itself mean FIFO, LIFO or sorted: the operations impose those rules.

A singly linked node contains data and a link to the next node. The head references the first node; None marks an empty head or the end of the chain. Unlike array indexing, reaching the kth node requires following earlier links. Insertion/removal can avoid shifting many array items once the relevant node or predecessor is known, but locating that position can still require traversal. Links consume memory.

class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node  # Reference to the successor, not an item count.

Homogeneous collections contain items of the same type; heterogeneous ones can contain different types. Linear collections organise items in a sequence; non-linear ones organise relationships differently (later tree/graph implementations are outside your promo cutoff). A conceptual array uses contiguous indexed storage; linked nodes can be located separately and connected through references.

For length, traverse from head and increment a counter per node. For search/update, traverse until the data matches or current is null, then read/change that node’s data. For positional insertion, validate the position, handle position 0 as a head change, and traverse to the preceding node; reject a position beyond the permitted range rather than dereferencing null.

The pointer rule: preserve the remaining chain priority/high

To insert new after current, first set new.next = current.next, then current.next = new. Reversing those assignments can lose the original successor or create an unintended self-link. To insert at the head, connect new to the old head before changing head.

Before: head → A → C → None
1. B.next = A.next       B → C
2. A.next = B
After:  head → A → B → C → None

To remove a node after previous, use previous.next = current.next. Deleting the head instead changes head itself. If a tail pointer is maintained, deleting the final node must update tail too. The removed node’s data can be returned before discarding the reference.

Preserve the successor before redirecting the predecessor. Draw the desired final chain first, then decide which assignments produce it without losing a needed reference.

Worked example — original priority/high

Remove the first matching value and return the possibly changed head plus a success flag. This function does not maintain a separate tail.

def delete_first(head, target):
    previous = None  # No predecessor exists before the head.
    current = head
    while current is not None:
        if current.data == target:
            if previous is None:  # The matching node is the head.
                head = current.next
            else:
                previous.next = current.next  # Bypass the matching node.
            return head, True
        previous = current       # Preserve predecessor before moving forward.
        current = current.next
    return head, False

For A→B→C deleting B: previous reaches A, current reaches B, and A.next becomes C. For deleting A, head becomes B. For empty or missing target, return unchanged head and False. The caller must retain the returned head: head, removed = delete_first(head, target).

Sorted insertion and scope boundary priority/medium

Sorted insertion traverses until the correct comparison boundary, retaining the predecessor. Specify whether a duplicate goes before or after equals.

Scope

Use singly linked lists. Syllabus §2.1.2 and the HCI handout exclude doubly linked and circular linked lists. Circular array queues remain included.

Optional extension: array links and free lists priority/low

The current source trail does not establish a required free-list implementation. Use this reference if a taught exercise supplies that representation.

A static linked list can store node data and “next” indices in arrays, with a free-list head marking available nodes. Allocating removes a node from the free list; freeing returns it. Follow the supplied null-index convention rather than assuming None or −1.

Static free-list trace

Suppose null is −1, active head=0 with next[0]=2, next[2]=-1; free=1 with next[1]=3, next[3]=-1. Allocating one node saves index 1, then sets free=next[1]=3. Only after saving that free-list successor should you overwrite next[1] to insert node 1 into the active chain. To release an already-unlinked node 2, set next[2]=free, then free=2. A full array means free == -1, even though some nodes may not hold currently meaningful data values; the free chain controls allocation.

Practice

Exam focus: HCI 2023 Q7 tests sorted linked-list insertion/deletion/length; HCI 2025 Q6 applies linked nodes to a queue. The original 2023 Q7, PDF p.6 uses string data rather than this chapter’s numeric adaptation, so inspect its order/duplicate assumptions before reusing code.

Handwritten method: draw before/after → name current/predecessor → handle empty/head separately → redirect links in a safe order → preserve or return the changed head. Test a missing target and a singleton; normal middle-node examples alone do not cover these transitions.

19A — original. Write to_list(head) that returns node data in order without changing links. Explain why testing current.next is not None as the loop condition would omit the last node and fail for an empty head.

19B — adapted from HCI 2023 Q7. Write sorted_insert(head, value) for ascending numeric nodes, inserting a duplicate before existing equal values and returning the new head. Handle empty input and insertion at either end.

19C — original, extra practice. Starting with head→10→20→30→None, explain the two link changes needed to insert 15 after 10. Then delete 30. State which predecessor link changes and why traversal needs to keep that predecessor.

Hints

19B: traverse while existing values are strictly less than the new value. Update the head separately when no predecessor exists.

19D — original, positional insertion. Write insert_at(head, position, value) with zero-based positions, using Node. Allow positions 0 through length inclusive, raise IndexError otherwise, and return the possibly changed head. Test empty, head, middle, end and beyond-end cases. Assume position is an integer.

19E — original, length and lookup. Write linked_length(head) and find_first(head, target). The latter returns the zero-based index of the first match, or −1 if absent. Test an empty list and repeated target values.

Revision checklist

• 19.1 Distinguish an ADT’s interface from its implementation.
• 19.2 Compare homogeneous/heterogeneous and linear/non-linear collections at the taught level.
• 19.3 Explain contiguous array storage versus linked-node storage.
• 19.4 Draw and trace a singly linked list with head/start and null references.
• 19.5 Implement traversal, length, search and data update.
• 19.6 Implement insertion at the front, a position and in sorted order as specified.
• 19.7 Implement deletion at the front, middle and end, including target-not-found handling.
• 19.8 Explain why pointer updates must occur in a safe order.
• 19.9 Test empty, singleton, head/tail operations and invalid positions.

Optional extension only: represent links with array indices and trace a supplied free-space list.

Visual revision mindmap

Open this mindmap and its text version · All 21 mindmaps

Your mindmap framework

Centre: Python Chapter 8.1–8.3 — collections and linked lists. Build the six branches below. For each subbranch, add a short definition, a labelled sample and one exam trap from memory; then check the chapter.

flowchart LR
    C["19 • Revision map"]
    C --> B0["ADT and representation"]
    C --> B1["Traverse and locate"]
    C --> B2["Insert"]
    C --> B3["Delete"]
    C --> B4["Costs and scope"]
    C --> B5["Visual checks and mistakes"]

• ADT and representation

  • Behaviour/interface versus storage.
  • Homogeneous/heterogeneous and linear/non-linear.
  • Singly linked node: data plus next reference.
  • Head gives first node; null marks empty/end.

• Traverse and locate

  • current begins at head.
  • Process existing node, then advance.
  • Length, search, read and update.
  • Index access requires traversal; keep predecessor when needed.

• Insert

  • Head: new points to old head.
  • Middle/end: preserve successor then redirect previous.
  • Positional: validate 0 through length.
  • Sorted: comparison boundary and duplicate policy.

• Delete

  • Head change versus predecessor bypass.
  • Return changed head where required.
  • Maintain tail if implementation has one.
  • Missing target and singleton-to-empty cases.

• Costs and scope

  • Links use memory; no contiguous placement required.
  • Locating position may take traversal.
  • No shifting once relevant link is known.
  • Doubly/circular linked lists excluded; array free-list is optional reference.

• Visual checks and mistakes

  • Draw before, successor preserved, predecessor redirected.
  • Label head/current/previous; show null explicitly.
  • Test empty, head, middle, tail, duplicate and invalid position.
  • Avoid: test current.next and omit last node; lose successor; discard returned head.

Close the notes and test the map: explain one branch aloud, sketch its sample, then answer a linked practice question. Mark any missing link to revisit.

Source trail

9569 §2.1.2; school Data Structures pp.1–13, Tutorial 8A. Included because these sections precede queues.

HCI 2023 Q7; 2022 Q7(e–f); school Tutorial 8A.

Source guide records provenance and original-paper locations.