Exercises — Linked list — singly - node structure, traversal, insert head - tail - middle, delete

(a) 3 nodes — count the boxes: 7, 3, 9. (b) The next of the last node is ==null==. That is how you know it is the last node — nothing comes after it. (c) The list becomes unreachable garbage. head is the only external arrow into the chain; with no arrow pointing at the first box, there is no way to find any box, and the whole chain is lost (garbage-collected/freed). WHY: unlike an array, there is no base + i*size address you can recompute — the only door in is head.

• Insert at head → $O(1)$. Two pointer moves, no walking: new.next = head; head = new.
• Insert at tail → $O(n)$. You must walk to the box whose next is null before attaching.
• Access element at index i → $O(n)$. No index arithmetic exists; you hop from head up to $i$ times.

The pattern: anything you can do at the front door is cheap; anything that needs the end or the middle costs a walk.

Every insert_head puts the new value in front of everything (steps: new.next = head; head = new). So the list grows leftward:

• after insert_head(5): head → [5] → null
• after insert_head(2): head → [2] → [5] → null
• after insert_head(8): head → [8] → [2] → [5] → null

Final list: ==8 → 2 → 5 → null==. Value at head: ==8==. Notice the output is the reverse of the insertion order — a hallmark of head-insertion (this is exactly how a stack pushes).

Position 1 (0-indexed) is the node holding ==4== (position 0 is 1, position 1 is 4). Call it cur. Apply wire-then-redirect:

1. new.next = cur.next → the new 9 node points to the node holding 6.
2. cur.next = new → the 4 node now points to 9.

Result: ==1 → 4 → 9 → 6 → null==.

(a) It prints ==1, 2== only. The loop stops when cur.next is None, i.e. when cur is the 3 node — so 3 is never printed. It stops one node early. (b) On an empty list, cur = self.head is None, and the very first check None.next crashes with an attribute error. (c) Loop on the node itself, process, then advance:

cur = self.head
while cur is not None:
    print(cur.data)
    cur = cur.next

WHY this works: while cur is not None is true even for the last box (its next may be null but cur itself is a real box). We print before hopping, so the final box gets printed, and an empty list skips the body entirely — no crash.

20 is not at the head, so we set prev = head (the 10 node) and cur = head.next (the 20 node).

• Iteration 1: cur is 20. Comparison #1: 20 == 20 → true. Unlink: prev.next = cur.next, i.e. the 10 node now points to the 30 node.

Comparisons made: 1. (We already know the head is not the target from the pre-check cur.data == value, which was one earlier comparison against 10; if the problem counts that pre-check too, it is 2 comparisons total. Counting only comparisons inside the walk loop: 1.) Final list: ==10 → 30 → 20-node-is-garbage== → 10 → 30 → null.

def get_size(self):
    count = 0
    cur = self.head
    while cur is not None:
        count += 1
        cur = cur.next
    return count

On 1 → 4 → 9 → 6 → null this returns ==4. On an empty list it returns 0== (loop body never runs — correct, no special case needed). Time $O(n)$: exactly one pointer-follow per node. Extra space $O(1)$: only count and cur, independent of $n$. See Big-O Notation.

def insert_tail_fast(self, data):
    new = Node(data)
    if self.head is None:        # empty: new is both head and tail
        self.head = new
        self.tail = new
        return
    self.tail.next = new         # old last node points to new
    self.tail = new              # tail pointer moves forward

Now no walk is needed — we jump straight to the last node via tail, so it is ==$O(1)$==. What delete must maintain: if the deleted node was the tail, tail now dangles at a freed box. So after unlinking, if cur is self.tail, set self.tail = prev (the new last node). And if you delete the only node, set both head and tail to null. Forgetting this leaves tail pointing at garbage — the classic bug that a plain queue must guard against.

Idea: walk the chain once, and as you pass each node, flip its next arrow to point backward. You need three pointers: prev (what we've already reversed), cur (the node we're flipping now), and nxt (saved so we don't lose the forward chain — this is the wire-first principle again).

def reverse(self):
    prev = None
    cur = self.head
    while cur is not None:
        nxt = cur.next     # 1) save the forward link BEFORE we destroy it
        cur.next = prev    # 2) flip this node's arrow to point backward
        prev = cur         # 3) prev advances to the node we just flipped
        cur = nxt          # 4) cur advances using the saved link
    self.head = prev       # prev is the old last node = new front door

Trace on 1 → 2 → 3 → null (showing prev, cur at the top of each loop):

• start: prev=null, cur=1. Save nxt=2; 1.next=null; prev=1, cur=2.
• prev=1, cur=2. Save nxt=3; 2.next=1; prev=2, cur=3.
• prev=2, cur=3. Save nxt=null; 3.next=2; prev=3, cur=null.
• loop ends; head = prev = 3.

Final list: ==3 → 2 → 1 → null. Cost: $O(n)$ time, $O(1)$ space==. WHY save nxt first? The instant we do cur.next = prev, the original forward arrow is gone. If we hadn't stashed it in nxt, we could never reach the rest of the list — the same "wire before you redirect" rule from insertion, applied in reverse.

Floyd's tortoise-and-hare. Use two walkers: slow moves 1 hop per step, fast moves 2 hops per step.

def has_cycle(self):
    slow = fast = self.head
    while fast is not None and fast.next is not None:
        slow = slow.next          # 1 step
        fast = fast.next.next      # 2 steps
        if slow is fast:           # same box -> cycle
            return True
    return False                   # fast fell off the end -> no cycle

Why it terminates & is correct:

• No cycle: fast reaches null after at most $\lceil n/2\rceil$ steps and the loop exits with False.
• Cycle: fast can never hit null (the chain has no end), so it enters the loop forever. Once both are inside the loop, fast gains 1 box of ground on slow every step; the gap shrinks by 1 each step (mod the loop length), so fast must land on slow — they collide. Return True.

Applied: (a) 1 → 2 → 3 → null: fast walks off the end (fast.next becomes null), loop exits → ==False==. (b) 1 → 2 → 3 → 2 → 3 → 2 …: fast never reaches null; slow and fast collide inside the 2 → 3 loop → ==True. Extra space: $O(1)$== (two pointers), time $O(n)$.

Cover the answers. (1) End marker of a singly list? (2) Cheapest insert? (3) Why carry prev in delete? (4) Space cost of in-place reverse? End marker ::: null. Cheapest insert ::: at head, $O(1)$. Why prev ::: no backward pointer, so unlink needs the predecessor's next. Reverse space ::: $O(1)$ (three pointers).