Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 5
Linked lists (Lecture 05)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
A node of a singly linked list holds:
The order is in the links themselves; there are no indices (b) and no separate order (d).
-
Reading
ll[i]on a linked list of n nodes costs:Follow
nexti times fromhead: O(i), O(n) in the worst case. -
push_frontcosts:Two reference assignments, independent of n. "Amortised" (c) describes the dynamic array's append, not this.
-
appendon a singly linked list without a tail reference costs:It must walk to the last node first. A tail reference makes it O(1).
-
Which operation is O(1) on a linked list but O(n) on a dynamic array?
Front insertion: two references here; every element shifts in an array.
-
Which operation is O(1) on a dynamic array but O(n) on a linked list?
Indexing: address arithmetic in an array, a walk in a list.
len(d) is O(1) in both — because the list keeps_size. -
In
push_front, why mustnew.next = self.headcome beforeself.head = new?After
self.head = new,new.next = self.headmakes the node point at itself, and the old first node is no longer referenced by anything. Python evaluates each assignment's right-hand side first (a), but that is not the reason for the order of two separate statements. -
To remove a node from a singly linked list, you need a reference to:
Only the predecessor holds the reference that must be redirected around the removed node.
-
Which node is the special case in
remove(value)without a sentinel?The head has no predecessor, so it is removed by moving
headinstead. -
What is the running time of this loop over a linked list of n nodes?
for i in range(len(ll)): total += ll[i]Each
ll[i]walks i steps from the head: 0 + 1 + … + (n-1). Usefor value in ll:for one O(n) walk. -
Why is
len(ll)O(1) indsa/linked_list.py?A stored count, updated by
push_front,append,insert_at,pop_frontandremove. Forget one, andlenlies. -
Reversing a linked list in place needs how much extra space?
Three references —
prev,nodeand the saved next — whatever n is. -
On 64-bit CPython, a
Nodewith__slots__takes about 48 bytes. One slot of an array of references takes:One 8-byte reference per slot; the node is six times larger.
-
A doubly linked list can do in O(1) what a singly linked one cannot:
With
previn each node, the node itself gives you its predecessor. Indexing (a) and search (c) are still O(n). -
What is a sentinel (dummy) node for?
With a permanent node before the first real one, removing the first real node looks exactly like removing any other.
-
A singly linked list with a tail reference. Removing the last node costs:
After removing the last node,
_tailmust move to its predecessor, and only a walk from the head finds it in a singly linked list. -
Python's
collections.dequeis implemented as:Blocks give array-like memory efficiency; the links give O(1) at both ends.
-
Why does the traversal loop test
while node is not None:rather thanwhile node.next is not None:?It is the standard off-by-one:
node.next is not Noneis the right test only when you want to stop on the last node (to append after it). -
After
a = Node(1),b = Node(2, a),c = Node(3, b), what isc.next.next.value?c.nextisb, andb.nextisa, whose value is 1. -
In Python, what happens to a node that nothing refers to any more?
Unreachable objects are reclaimed automatically.
del(b) only removes a name. -
To insert a new node at index i ≥ 1, you walk to the node at index:
The node at i − 1 is the one whose
nextmust change. Index 0 ispush_front. -
Where in this course do short linked lists appear inside another structure?
ChainingHashMap(Week 13) stores anArrayof chains ofEntrynodes. -
What is printed?
ll = LinkedList([1, 2, 3, 4]) node = ll.head.next node.next = node.next.next print(list(ll), len(ll))nodeis the second node, andnode.next = node.next.nextskips node 3, so the walk finds[1, 2, 4]. But the change bypassed the list's methods, so_sizewas never decremented andlenstill says 4. (a) is whatremove(3)would leave. (b) skips the wrong node. -
On a list of 6 nodes,
insert_at(4, x)runs. How many times doesprev = prev.nextrun?prevmust stop on the node before the gap, at index 3. It starts at index 0, sorange(index - 1)moves it 3 times. 4 (c) is one step too far: the new node would land at index 5. -
ll = LinkedList([1, 2, 3]). Which call raisesIndexError?Reading allows
0 <= index < len, soll[3]is out of range. Inserting allows0 <= index <= len, so (b) is a legal append at the end and (d) ispush_front.ll[-1](c) is 3:__getitem__adds_sizeto a negative index. -
In a list with a sentinel node, the list is empty when:
The sentinel is permanent. It is never
None(a) and never removed (d), and its value is meaningless (c). The first real node issentinel.next, so no real node meanssentinel.next is None. -
In a doubly linked list,
xis a node that is neither the first nor the last. Which two assignments remove it from the list?The node before
xmust point past it, and the node afterxmust point back past it. (a) and (b) change onlyx's own references, which leaves the neighbours still linked tox. (d) makes each neighbour point at itself. -
A new node is inserted between two neighbouring nodes
aandbof a doubly linked list. How many references must be set, counting the new node's own?new.prev = a,new.next = b,a.next = newandb.prev = new. A singly linked list needs only two of these, which is the "twice the bookkeeping" of the doubly linked list. -
A student adds
_tailto the list. Theirappenddecides "empty" by testingself._tail is None, and theirpop_frontupdatesheadand_sizebut never_tail. What does this print?ll = LinkedList([7]) ll.pop_front() ll.append(5) print(list(ll), len(ll))After
pop_front,headisNonebut_tailstill refers to the old node 7.appendsees a tail that is notNone, so it links 5 after that dead node and never setshead. The walk fromheadfinds nothing, while_sizewent from 0 to 1. It fails silently and raises no error (d). Every method that can empty the list must clear_tail. -
reverse()runs on 1 → 2 → 3. After the first pass of the loop body, what is the state?The body saves
following = Node(2), turnsNode(1).nextround toprev, which isNone, then steps forward:prevbecomesNode(1)andcurrentbecomesNode(2). (d) forgets that the link was turned. (c) is the state after the second pass. -
Suppose
insert_athad noindex == 0case and went straight to the walk. What wouldinsert_at(0, 9)do to[1, 2, 3]?range(0 - 1)is empty, soprevstays on the head, and the new node is spliced in after it, at index 1. No error is raised (b), and the list is wrong. On an empty listprevisNone, andprev.nextraisesAttributeError. Position 0 has no node before it, so the head itself must change: that ispush_front. -
ll = LinkedList([4, 2, 4]), thenll.remove(4). Nowlist(ll)is:removestops at the first node holding the value: here it is the head (the special case), soheadmoves on and the second 4 stays. (a) would remove every 4. -
Walking a dynamic array and walking a linked list are both O(n), yet the array walk is usually several times faster. Why?
It is a constant factor that Big-O hides. An array's references are contiguous, and memory is fetched in blocks (the cache). A list's nodes were created one at a time, wherever there was room. Both walks are Θ(n) (a), and walking does not touch
_size(b). -
In a circular list the last node points back to the first. What does the usual loop
while node is not None:do on it?Every node has a successor, so
nodeis neverNoneand the loop never ends. A circular walk must stop when it comes back to its starting node. Nothing in the loop shown checks for that (d). -
What is printed?
a, b, c = Node(1), Node(2), Node(3) a.next = b b.next = c b.next, c.next = None, b print(a.next.value, c.next.value, b.next)a.nextis stillb, whose value is 2. The tuple assignment setsb.next = Noneandc.next = b, soc.next.valueis 2 too, andb.nextprintsNone. (a) readsc.nextas if it still pointed forward. -
LinkedList().pop_front():The contract raises
IndexError("pop from empty list"), likelist.pop(). Without the check,self.head.valuewould raiseAttributeError(c) onNone, which is W5-B3. -
You hold a reference
nodeto a node in the middle of a long singly linked list. Inserting a new node immediately before it costs:Inserting before a node means changing its predecessor's
next, and a singly linked node has no reference back. Inserting after it is O(1) (a). A doubly linked list makes both O(1). -
What is printed?
ll = LinkedList() for v in [3, 1, 2]: ll.push_front(v) ll.append(ll.pop_front()) print(list(ll))Three
push_frontcalls build[2, 1, 3](b), since the last one pushed is first.pop_fronttakes the 2, andappendputs it at the end:[1, 3, 2]. The front value has moved to the back, a rotation. -
insert_at(2, x)on a singly linked list of 5 nodes. How many references held by nodes that were already in the list change?Only the node at index 1 changes its
next, to the new node. The new node's ownnextis set as it is made. Every node after the gap is untouched (c), which is why the splice is O(1) once the walk has foundprev. -
A singly linked list with
headand_tailis reversed in place. What must happen to_tail?After reversing, the old first node is the last node. Saving
old_head = self.headbefore the loop and settingself._tail = old_headafter it costs O(1), so no walk is needed (c). The last node certainly changes (a), unless the list has at most one node.
33 marks
Written questions
9 written questions (33 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 33
-
Compare a dynamic array and a singly linked list on four operations, with their costs. For each structure, give one situation where you would choose it, and say why.
Model answer and marking points
Operation Dynamic array Singly linked list read element i O(1) O(n) insert / remove at the front O(n) O(1) append at the end amortised O(1) O(n), or O(1) with a tail insert next to a node you hold O(n) O(1) - Choose the array when you index by position, iterate a lot, or care about memory — e.g. storing measurements you read by index. It is compact and cache-friendly.
- Choose the list when you insert and remove at the front, or splice at positions you already hold — e.g. a stack of undo actions, the chains of a hash table. No copying, ever.
-
Explain
push_frontstep by step with a diagram. Show what goes wrong if the two assignments are done in the other order.Model answer and marking points
- Step 1:
new.next = self.head— the new node points at the current first node. - Step 2:
self.head = new— the list now starts at the new node. Then_size += 1. Two assignments: O(1). - Diagram: new node → old first node → … →
None, withheadmoving from the old first node to the new one. - Reversed order:
self.head = newfirst, thennew.next = self.headsetsnew.next = new— a node pointing at itself. Nothing refers to the old first node any more, so the rest of the list is lost, and iterating loops for ever over the one node.
- Step 1:
-
LinkedListsupportsll[i], just like an array. Explain why the cost is different, and whyfor i in range(len(ll)): ll[i]is a bad loop. What should be written instead?Model answer and marking points
- Array indexing is address arithmetic, O(1). List indexing must follow
nextfromheadi times, O(i) — the same interface hides a different cost. - In the loop, each
ll[i]starts again from the head: 0 + 1 + … + (n-1) = O(n2) for what should be one pass. - Write
for value in ll:—__iter__keeps its place and walks once: O(n).
- Array indexing is address arithmetic, O(1). List indexing must follow
-
A tail reference makes
appendO(1). What does it cost? Name the methods that must change, and explain why removing the last node is still O(n).Model answer and marking points
- Benefit:
appendlinks after_tailand moves_tail: O(1) instead of a walk. - Cost: one more reference to keep correct in every method that can change the last node:
push_frontandappendon an empty list (the new node is also the tail),insert_atat the end,pop_frontof the only node,removeof the last node, andreverse(head and tail swap). - Removing the last node is still O(n):
_tailmust move to the node before it, and in a singly linked list only a walk from the head finds that node.
- Benefit:
-
Explain what a doubly linked list and a sentinel node each fix, and what each costs.
Model answer and marking points
- Doubly linked: each node also references its predecessor. Removing a node you hold, and removing from the end, become O(1); the list can be walked backwards. Cost: one more reference per node, and every insertion and removal updates twice as many links.
- Sentinel: a permanent node before the first real one, so every real node has a predecessor and there is no special case for the head (or for an empty list). Cost: one extra node, and every method must remember that the first real node is
sentinel.next.
-
A music player keeps a playlist. The user presses next and previous, and can delete the song that is playing. Which structure would you choose: a dynamic array, a singly linked list or a doubly linked list? Give the cost of each of the three actions in your choice, and say why each of the other two is worse.
Model answer and marking points
- Choice: a doubly linked list, holding a reference to the current node.
- Costs: next is
current = current.next, O(1). Previous iscurrent = current.prev, O(1). Delete the current song iscurrent.prev.next = current.nextandcurrent.next.prev = current.prev, O(1), with the head and tail handled as special cases (or a sentinel). - Singly linked: next is O(1), but previous and delete need the node before the current one, so they mean a walk from the head, O(n).
- Dynamic array, holding an index: next and previous are O(1), but deleting shifts every later song left, O(n).
-
Explain
insert_at(index, value)step by step: the check onindex, the caseindex == 0, the walk, and the splice. Why does the walk stop afterindex - 1steps? Give the best-case and worst-case cost, and show what goes wrong if the loop is writtenfor _ in range(index):, both for an index in the middle and forindex == len(ll).Model answer and marking points
- Steps: raise
IndexErrorunless0 <= index <= len(index == lenmeans "at the end"). Ifindex == 0, callpush_front, because there is no node before the gap. Otherwise walkprevfrom the headindex - 1steps, thenprev.next = Node(value, prev.next)and_size += 1. - Why
index - 1: only the node before the gap holds the reference that must change. It is at indexindex - 1, which isindex - 1steps from the head. - Cost: best case O(1), at index 0 or 1. Worst case O(n), at the end. The splice itself is always O(1).
range(index): the walk goes one node too far.insert_at(1, 9)on[1, 2, 3]gives[1, 2, 9, 3], with no error. Atindex == len,prevwalks off the end toNone, andprev.nextraisesAttributeError.
- Steps: raise
-
A linked list and a dynamic array are both O(n) to walk, yet measurement shows the array is faster and smaller. Explain both differences, with numbers for CPython. When is the linked list still the right choice?
Model answer and marking points
- Memory: an array slot is one 8-byte reference. A
Nodewith__slots__is about 48 bytes on 64-bit CPython, six times as much per element, plus the value object in both cases. - Speed: the array's references are contiguous and the processor reads memory in blocks (the cache). Nodes are scattered, so every
nextmay jump to a new place. That is the same Big-O with a bigger constant. - Still the right choice: frequent insertion or removal at the front (a stack); splicing at positions you already hold (an LRU cache, an editor's buffer); never paying for a big copy at an unlucky moment; and short chains inside a hash table.
- Memory: an array slot is one 8-byte reference. A
-
Explain how
reverse()reverses a list in place with three references. State whatprevandcurrentmean at the start of each pass of the loop, whyfollowingmust be saved first, and why the extra space is O(1). Compare with building a reversed copy withpush_front.Model answer and marking points
- The invariant: at the start of each pass,
previs the head of the part already reversed (Noneat first) andcurrentis the head of the part still to reverse. The loop ends whencurrentisNone, and thenself.head = prev. - Each pass:
following = current.next, thencurrent.next = prev, thenprev, current = current, following. That turns one link round and moves one step forward. - Why save
followingfirst: oncecurrent.nextpoints backwards, it is the only reference to the rest of the list. Without the saved copy, the rest is lost, and the loop steps back ontoprev(W5-B4). - Space: three references, whatever n is, so O(1) extra space and O(n) time. A reversed copy built by
push_frontalso takes O(n) time, but it makes n new nodes, which is O(n) extra space, and it leaves the original list unchanged.
- The invariant: at the start of each pass,