Types of LinkedList

A linked list's behavior — which directions you can walk it, and whether it ever ends — is entirely determined by two design choices baked into the node: how many pointers it carries (one next, or next plus prev), and what the last node's pointer holds (null, or a reference back into the list). Three combinations of those choices give the singly, doubly, and circular variants; picking the wrong one is what turns an otherwise-correct algorithm from O(1) into O(n), or makes it loop forever.

Recognize the pattern

• Only forward iteration needed, minimal memory per node, inserts/deletes mostly at the head → Singly Linked List (SLL).
• Need to walk backward, or delete a given node in O(1) without a pointer to its predecessor (LRU cache, browser history, text editor undo) → Doubly Linked List (DLL).
• Need wraparound semantics — round-robin CPU scheduling, circular buffers, Josephus-style elimination, a playlist that loops → Circular Linked List (CLL), singly or doubly.

Structure and cost, derived

The DLL's O(1) delete isn't magic: it trades one extra pointer per node (O(n) total across the list) for eliminating the O(n) predecessor scan an SLL needs before every mid-list delete. That single trade is the whole story. Traversal for all variants is O(n) since each node visit is O(1) and there are n nodes — no shortcuts, no random access (unlike an array's O(1) index).

Brute force vs. optimal: deleting a node by value

Brute force (any type): scan from head comparing values, track previous node, relink — O(n) time, O(1) space. The scan-and-relink logic is identical on SLL, DLL, and CLL, but the loop's termination check is not: on SLL/DLL you stop at node == null; on a circular list there is no null, so that same check never fires and the scan spins forever unless you instead stop at node == head (or count visited nodes) — see Pitfalls.

Where the type actually changes the answer: if you are handed a direct reference to the node to delete (not a value to search for), an SLL forces you back to O(n) to find its predecessor, while a DLL does it in O(1) because node.prev is already stored. This is why DLLs back LRU caches: the hash map gives you the node pointer directly, and the DLL lets you unlink it in O(1).

Traced example: deleting node 'B' by reference, DLL vs SLL

List: A(10) ↔ B(20) ↔ C(30), and we already hold a reference to node B (e.g. from a hash map lookup).

Result both cases: A(10) ↔ C(30).

// Minimal DLL delete-by-reference (Java)
class Node {
    int val;
    Node prev, next;
    Node(int val) { this.val = val; }
}

class DoublyLinkedList {
    Node head, tail;

    void deleteNode(Node x) {
        if (x.prev != null) x.prev.next = x.next;
        else head = x.next;               // x was head
        if (x.next != null) x.next.prev = x.prev;
        else tail = x.prev;                // x was tail
        x.prev = null; x.next = null;      // help GC, avoid stale links
    }
}

Pitfalls

• Circular list infinite loop: traversing with while (node != null) on a circular list never terminates — you must check while (node != head) (or track a count) instead. The degenerate case is a circular list of one node — its next points to itself, so a null test can never fire.
• Copy-next-value “O(1) delete” hack: given only a node reference in an SLL, copying next.val into it and unlinking next looks like O(1) delete — but it fails for the true last node (no next to cannibalize) and doesn't actually delete the object callers may still hold.
• Floyd vs. intentional circularity: fast/slow cycle detection is for finding accidental cycles in lists that should be linear; on a deliberately circular list it trivially reports “cycle” — use a fixed stop (head or count) there instead.
• DLL pointer desync: updating next without updating the paired prev (or vice versa) silently corrupts the list; every insert/delete must update both links atomically.
• Losing the only reference: in a singly circular list, if you only hold a pointer to the tail's predecessor and drop it before relinking, you cannot recover the loop's start.
• Off-by-one at head/tail: forgetting to update head/tail sentinels when deleting the first or last node (shown explicitly in the Java snippet above).

When to use / when not

SLL — use for stacks, forward-only iteration, minimal-memory adjacency lists. Avoid when you need O(1) deletion by reference or backward traversal.

DLL — use for LRU caches, deques, undo/redo, text buffers. Costs one extra reference per node (4 bytes on a 64-bit JVM with compressed oops, 8 without — and 8-byte object alignment can round that up or absorb it entirely, e.g. a 12-byte-header + int + next node pads 20 → 24 bytes, the same size a prev field needs) and more bookkeeping on every mutation; skip it if you never delete by direct node reference and memory is tight.

CLL — use for round-robin schedulers, circular buffers, repeating structures. Avoid for generic list-of-items code — it invites infinite-loop bugs for no benefit.

Named alternative — dynamic array (ArrayList): gives O(1) random access and better cache locality than any linked list (contiguous memory), but insert/delete in the middle is O(n) due to shifting, versus O(1) relink once you're at the position in a linked list. Choose array-backed structures when access pattern is index-heavy; choose linked lists when you mutate frequently at known positions/ends and don't need random access.

Takeaways

• The type is fully determined by pointer count (1 vs 2) and what the last node points to (null vs. back into the list).
• DLL's O(1) delete-by-reference is bought with one extra pointer per node (O(n) total) — not free, a deliberate trade.
• Circular variants remove the null terminator, so traversal must stop on a revisited node, not on null.
• Linked lists never beat arrays on random access or cache locality; they win on O(1) mutation at a known position.

Recall: Given only a reference to a node in the middle of the list (no head pointer, no search), which list type lets you delete it in O(1), and why does an SLL fail at this?

Synthesized from standard DSA references (GeeksforGeeks, CLRS linked list chapter) and verified traces; adapted for this guide.