COMP9123 — Data Structures & Algorithms
Week 2: Lists & Sequences
This is the week where the course stops talking about collections in the abstract and starts asking what storage choice actually buys you. The useful lecture starts at slide 6: first the List ADT, then arrays, then linked lists, then the pointer edits that make linked structures work.
Big picture: Week 2 teaches that the same List ADT can behave very differently depending on whether you store items contiguously or as linked nodes.
List ADT: the Promise Before the Storage
The lecture begins with a discipline that matters all semester: separate what a data structure is supposed to do from how it happens to be implemented.
ADT idea: an abstract data type is defined by its data items and supported operations, not by the concrete memory layout. The user of the structure cares about behaviour; the implementer cares about representation.
| List operation | What it promises | What Week 2 wants you to notice |
|---|---|---|
size(), isEmpty() |
Report the current logical state of the list. | The ADT says nothing yet about where that information is stored. |
get(i), set(i, e) |
Read or replace the element at index i. |
The cost depends entirely on the chosen representation. |
add(i, e), remove(i) |
Change the sequence while preserving order. | Storage choice determines whether edits are global shifts or local pointer changes. |
Professor mindset: do not say “a list is an array” or “a list is a linked list.” The lecture is teaching that a list is the abstraction, and arrays / linked structures are competing ways to realise it.
Array-Backed Lists: Fast Indexing, Costly Shifting
Once the List ADT is clear, the lecture uses arrays as the first concrete implementation because arrays make indexing beautifully simple.
Array model: if A[i] stores the element at logical index i, then get(i) and set(i, e) are just direct access into contiguous storage, provided the index is valid.
| Operation | Typical cost | Why |
|---|---|---|
get(i), set(i, e) |
\(O(1)\) | Index arithmetic takes you straight to the target cell. |
add(i, e) |
\(O(n-i)\) | Everything from position i onward must shift forward. |
remove(i) |
\(O(n-i)\) | You must close the hole by shifting elements back. |
| Capacity limit | Structural limitation | A static array only works while \(n \leq N\). |
What arrays do brilliantly
Indexed access, replacement, and compact contiguous storage. This is why arrays stay central throughout algorithms courses.
What arrays do badly
Middle edits and unknown future growth. The lecture's point is that the cost comes from moving many elements, not from the idea of the List ADT itself.
Key limitation from the slides: static array-backed lists use \(O(N)\) space even when the logical list only has \(n\) elements, and they force you to choose capacity before you know the future.
add(i, e) expensive in an array-backed list when i is near the front?Why the Lecture Leaves Arrays and Moves to Linked Structures
Slides 22 to 26 are the bridge. The lecture is not abandoning arrays because they are bad. It is showing what kind of problem pressure makes a different representation worth it.
Dynamic size
Linked lists do not require a fixed capacity ahead of time. They grow and shrink one node at a time.
Scattered memory
Nodes can live in different places in memory. The structure is held together by references instead of contiguity.
Head reference
The whole list is represented by access to the first node. Everything else is reached by following links.
Trade-off: linked lists remove global shifting, but they also remove direct random access. You gain local edits and flexible growth, and you lose instant indexing.
The question to ask: if my workload is dominated by editing nearby links rather than jumping to arbitrary indices, am I still paying for the right representation?
Singly Linked Lists: Nodes, Head Pointers, and Traversal
The singly linked part of the lecture teaches a completely different way to think about structure: not as slots in a block, but as nodes connected one step at a time.
Node model: each node stores its data and a reference to the next node. The final node points to None, and the whole list is captured by the head reference.
What you can do naturally
Walk forward one node at a time, insert at the head cheaply, and splice nodes into the structure by updating a small number of links.
What you must give up
You cannot jump to position i without traversing through earlier nodes first. Indexing becomes a walk, not an address calculation.
Traversal pattern from the slides
Traversal is the first core pattern because everything else builds on it.
current = head
while current != None:
print(current.data)
current = current.next
Lecture advice worth keeping forever: draw the diagram before editing pointers. Most linked-list mistakes happen because students manipulate names in code without first fixing the picture in their head.
Pointer Rewiring: the Reusable Insertion and Deletion Moves
Most of Week 2 is really a set of repeatable pointer-edit templates. Once you see the pattern, the many slides stop feeling like many different algorithms.
| Edit | Core move | What the lecture is trying to train |
|---|---|---|
| Insert at beginning | Point the new node at the old head, then move head. |
How to update a distinguished reference safely. |
| Insert at end | Traverse to the last node, then set current.next = newNode. |
Why missing metadata such as a tail pointer changes cost. |
| Insert at position | Traverse to the predecessor, then splice the new node into the gap. | Why the predecessor matters in singly linked lists. |
| Delete at beginning | Move head to head.next, then sever the old node. |
How to preserve access before disconnecting nodes. |
| Delete at end / position | Find the node before the cut, bypass the removed node, then disconnect stale links. | Why pointer order is part of correctness. |
If you overwrite the only reference to a still-needed node too early, you lose the part of the structure you were meant to preserve.
That is why the slides repeatedly store temporary references such as current and temp before changing links.
A correct edit preserves reachability of everything that should remain and disconnects exactly what should leave.
Doubly Linked Lists: Paying Extra Space for More Local Power
The doubly linked part of the lecture is not just “the same thing with one more arrow.” It is about what changes once each node knows both its predecessor and successor.
Doubly linked node: each node stores data, next, and prev. That extra reference costs space, but it makes reverse traversal and many deletions much more local.
| Question | Singly linked answer | Doubly linked answer |
|---|---|---|
| Can you move backwards directly? | No | Yes, via prev |
| Delete a known interior node locally? | Not without its predecessor | Yes, if you already have the node handle |
| Memory per node | Lower | Higher |
Insert at beginning
You now update both directions: new node points forward, and the old head points back.
Delete interior node
The predecessor and successor can be linked directly around the removed node, which is why doubly linked structures are so popular for local edits.
Circular extra
The closing slides treat circular linked lists as an extension: useful when processes repeat around a ring rather than terminate at None.
Design lesson: extra fields are not free, but they can dramatically simplify the operations you care about most.
Tutorial 2: Build Nodes, Then Think Like a Data-Structure Designer
The tutorial is not just practice on syntax. It is a staged transition from writing basic Python to implementing the exact linked-list patterns the lecture has been diagramming.
| Tutorial cluster | What students are asked to do | Why it matters |
|---|---|---|
| Setup warm-up | Check Python, write hello.py, run it from the terminal. |
Removes tooling friction before the actual data-structure work begins. |
| Core node tasks | Implement Node, DoublyNode, traversal, and insertion / deletion helpers. |
Turns the lecture diagrams into executable structure. |
| Reasoning problems | Explain singly linked deletion, reverse traversal under space limits, recursive permutation generation. | Pushes you from code writing into algorithm design and analysis. |
| Challenge question | Design one singly linked-list-based structure supporting append, delete, findMiddle, and reverse. | Forces you to think about what metadata the structure should maintain, not just what methods it exposes. |
What strong Week 2 understanding sounds like: “I can explain when arrays win, when linked lists win, and which extra references or stored fields would change the runtime of an operation.”
Chapter Quizzes
Use the embedded checks above as you go, then finish with mixed repetition in the Quiz Hub and flashcards.
Best rhythm: read one section, answer its local quick check immediately, then move on. After the whole page feels stable, switch to the Quiz Hub for broader recall.