Singly vs Doubly vs Circular

## The claim to be careful with "Linked lists have O(1) insertion" is the sentence that gets candidates into trouble. The accurate version is: **insertion is O(1) once you already hold a reference to the node you are inserting next to.** Splicing a node in means writing two or three reference fields, which is constant work regardless of list length. Everything expensive about a linked list is *navigation*, and each variant differs exactly in what it lets you navigate to cheaply. ## The three variants and what they store - **Singly-linked:** each node holds a value and a `next` reference. The final node's `next` is NIL. The list handle usually holds `head`. - **Doubly-linked:** each node holds `prev` as well as `next`. The first node's `prev` and the last node's `next` are NIL. - **Circular:** the last node's `next` points back to the first, so there is no NIL terminator at all. A circular list can be singly or doubly linked (in a circular doubly-linked list the first node's `prev` points at the last). ## Filling in the tail-insert grid A common whiteboard exercise is to fill in the cost of "add a node at the end" for each variant, with and without a stored tail reference: | Variant | Handle stored | Append at end | Delete last node | |---|---|---|---| | Singly | head only | O(n) — walk to the last node | O(n) — need its predecessor | | Singly | head + tail | O(1) | O(n) — tail gives the node, not its predecessor | | Doubly | head only | O(n) — walk to the last node | O(n) — walk to it first | | Doubly | head + tail | O(1) | O(1) — `tail.prev` is right there | | Circular singly | last node only | O(1) — and insert-at-front is O(1) too | O(n) — predecessor unknown | | Circular doubly | any node | O(1) | O(1) | Two results in that grid are the ones interviewers actually probe. **First: a tail reference fixes append but not delete-last in a singly-linked list.** Removing the final node means writing NIL into the *previous* node's `next` field, and the previous node is exactly what a singly-linked list cannot name. You hold the victim, not the node that points at it, so you walk from the head to find it. Candidates who say "we have a tail pointer, so both ends are O(1)" have generalised one operation into two. **Second: a circular singly-linked list gets both ends from one stored reference.** If the handle is the *last* node, then `last.next` is the first node. Push-at-front is: allocate, point the new node at `last.next`, set `last.next` to the new node — done, O(1), and `last` is unchanged. Push-at-back is the same three writes plus advancing `last` to the new node. One field, two constant-time ends. That is why ring buffers of nodes — a turn order for a four-player board game, say, where play advances forever and a player can join between rounds — are often built circular rather than as a list plus a wrap-around index. Storing the *first* node instead would be the worse choice: you would be back to walking the ring to reach the end. ## Why the walk is genuinely linear There is no shortcut to node k. Nodes live wherever they were allocated, and the only way from one to the next is to read a reference field and follow it. Nothing about knowing the *length* helps: storing a count tells you how many hops to make, not how to skip them. This is the structural difference from a contiguous array, where the address of element k is arithmetic on the base address. ## The bookkeeping a tail reference imposes A stored tail is not free in maintenance terms. Every operation that can change which node is last must update it: append, delete-last, deleting from a one-element list (both head and tail become NIL), inserting into an empty list (head and tail become the same node), and clearing. A stale tail reference is one of the classic linked-list bugs, and it fails silently — appends land after a node that is no longer in the list, so the new data simply disappears from every traversal. ## What to say in an interview Separate the two costs out loud: rewiring is O(1), reaching is O(1) or O(n) depending on which references the list keeps. Then state which variant gives you which end cheaply, and flag that delete-last is the operation where singly and doubly genuinely diverge, because it needs a step backwards that only `prev` provides.