ADTs + linked-list evaluation
Understand what an ADT specifies, then evaluate when linked lists are a better or worse choice than array-based structures.
What an ADT tells you — and what it hides
- explain the purpose of an ADT as a high-level description of stored data and operations;
- recognize singly, doubly and circular linked-list structures;
- evaluate linked lists against arrays/lists in terms of memory utilization, access and update performance;
- use the context of a problem to reach a justified data-structure choice.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
Separate an ADT's required behaviour from its representation
Interface, not implementation
A structure is described only by these operations: add_front(value), remove_front(), search(value) and traverse().
Explain why this is an ADT-level description rather than a complete implementation.
The description states what operations the structure must support and therefore its observable behaviour/purpose. It does not specify how nodes, memory, references or Python classes are implemented internally, so different implementations could satisfy the same ADT description.
Choose the likely structure
A music queue frequently inserts and removes items near known positions but almost never needs direct access to “item 800”. Explain why a linked list could be reasonable.
A linked list can update links without shifting a large block of elements once the position is known. Its lack of fast indexed access is less important because the application rarely jumps directly to a distant numbered position.
Singly, doubly and circular are all examinable
Singly: head → [A | next] → [B | next] → [C | None]
Doubly: None ← [A] ⇄ [B] ⇄ [C] → None
Circular: head → [A] → [B] → [C]
↑ ↓
└─────────────┘Read the three required structures
For each sketch, state what references a node needs and how the end of the structure is represented.
- Singly: each node stores a next reference; the last node points to
None. - Doubly: each node stores next and previous references; the ends have no neighbour in one direction.
- Circular: the final node links back to the head, so traversal must stop by detecting a return to the start rather than waiting for
None.
Trade-offs must be tied to the scenario
Evaluate linked list vs array/list
A leaderboard contains 50,000 players. It is searched sequentially by player name, and new players are often inserted into a known score position. Compare the linked-list choice with an array/list implementation.
A linked list needs extra memory for references and does not provide fast direct indexed access; sequential name search is still linear. However, once a score position has been located, insertion can be completed by changing links rather than shifting many later elements. If frequent insertion at known positions matters more than indexed access and the reference overhead is acceptable, the linked list is reasonable; otherwise an array/list may be simpler and more memory-efficient for indexed access.
Reason about links before writing code
Operation sketch
Start with head → A → C → None. Sketch the links after inserting B between A and C.
head → A → B → C → None
Conceptually, B points to C and A is redirected to B.
Search reasoning
Why can searching a linked list require visiting many nodes even if the desired item is conceptually “near the end”?
Nodes are reached by following references from a known starting point such as the head. Without a direct index or separate lookup structure, the search must inspect successive nodes until the target is found or the list ends.
Build the evaluation habit before coding
Teacher-created Paper 2 mini-set
1. Explain what information an ADT provides to a programmer.
2. State one structural difference between singly and doubly linked lists.
3. Evaluate a linked list for an application that performs many insertions but also needs frequent direct access to item i.
- An ADT gives a high-level description of the data and allowed operations/purpose without fixing one implementation.
- A doubly linked node has links in both directions; a singly linked node normally has only a next link.
- A good evaluation recognizes efficient rewiring for insertions but poor direct indexed access and additional reference memory, then judges based on which requirement dominates.
Can you choose a structure from actual requirements?
Exit decision
A route contains only 20 stops, is rarely modified, and the program repeatedly asks for stop 0, stop 5 and stop 19 by index. Which is likely more appropriate: an array/list or a linked list? Justify.
An array/list is likely more appropriate because direct indexed access is frequent while insertions/deletions are rare. The linked list’s update advantages would provide little benefit and would add reference overhead.
Finish the learning cycle
IA — main task
Continue Criterion D implementation/testing and record one data-structure decision you can justify in terms of the operations your solution actually performs.
Paper 2 — short practice
Without revealing, redraw singly, doubly and circular structures and write a four-factor linked-list evaluation: memory, access/search, insertion/deletion and judgement.