Linked List: Singly and Doubly Linked Insert, Delete and Reverse

The idea: relink pointers, never shift elements

An array keeps its values side by side in one block of memory. A linked list does not. Each value lives in its own node, which can be anywhere in memory, and each node holds a pointer to the next node. The list itself is just a pointer to the first node, called head. The last node's next is null (drawn as /).

So changing a list means changing pointers. To insert, you point the new node at its successor and its predecessor at the new node. To delete, you point the predecessor past the victim. No value is ever copied. The counters at the top of the canvas show this for every operation: hops (steps of the walk), pointer writes, elements copied (always 0), and what an array would have shifted.

Insert: two writes, in the right order

To insert value v at index i in a singly linked list:

1. Walk a pointer cur from head to index i − 1, the node before the gap.
2. Allocate the new node.
3. new.next = cur.next
4. cur.next = new

The order matters. If you write cur.next = new first, the only pointer to the rest of the list is gone, and so is the rest of the list (Demo: insert 25 at index 2 (singly)). Inserting at index 0 has no node before the gap, so the second write is head = new (Demo: insert at the head (singly)). That is exactly what a linked-list stack does on every push.

Delete: point past the victim

To delete index i, walk to the node before it, then write cur.next = victim.next. After that one write, walking from head never reaches the victim, even though the victim still points into the list. Then the node is freed (in C with free; in Java or Python the garbage collector does it) (Demo: delete index 1 (singly)). Deleting index 0 is head = head.next.

The relink is O(1), finding the spot is not

The pointer writes take constant time, but a list has no index arithmetic: list[i] means following next i times. So insert or delete at index i costs O(i) for the walk plus O(1) for the writes. The list wins when you already hold a pointer to the spot: the head, the tail, or a node a hash map points to, as in an LRU cache.

Singly vs doubly linked

A doubly linked node also has prev, and the list keeps tail as well as head. Each insert now writes four pointers (Demo: insert 25 at index 2 (doubly, 4 pointers)), but a node can be unlinked using only itself: victim.prev.next = victim.next and victim.next.prev = victim.prev. A walk can also start from whichever end is nearer.

Operation	Singly (head only)	Doubly (head and tail)
Insert or delete at the head	O(1): 2 or 1 writes	O(1): 3 or 2 writes
Insert at the end	O(n) walk	O(1) through tail
Delete the last node	O(n): walk to the node before it	O(1) through tail.prev
Delete a node you hold a pointer to	O(n): need its predecessor	O(1)
Walk to index i	i hops from head	min(i, n − 1 − i) hops
Memory per node	value + 1 pointer	value + 2 pointers

Demo: delete the tail, singly vs doubly runs both: 2 hops and 1 write in the singly list, 0 hops and 2 writes in the doubly list. This is why a linked-list queue keeps a tail pointer, and why an LRU cache needs a doubly linked list.

Reverse in place: prev, cur, next

Reversing a singly linked list walks it once with three pointer variables:

prev = null; cur = head
while cur != null:
    next = cur.next     # save the rest of the list
    cur.next = prev     # flip this node's pointer
    prev = cur
    cur = next
head = prev

That is one pointer write per node plus the new head: 5 writes for 4 nodes, O(n) time and O(1) extra memory (Demo: reverse a singly linked list). The canvas draws each flipped node mirrored so its arrow can point left, and redraws the list left to right at the end. A doubly linked list reverses by swapping prev and next in every node, then swapping head and tail: 10 writes for 4 nodes (Demo: reverse a doubly linked list).

Array vs linked list

	Array (dynamic array)	Linked list
Read index i	O(1)	O(i) walk
Insert or delete at index i	O(n − i) shifts	O(i) walk + O(1) writes
Insert at a known node	O(n) shifts	O(1)
Grow	copy to a bigger block now and then	one node at a time
Memory and cache	contiguous, cache friendly	a pointer per node, nodes scattered

In practice an array is often faster even for middle inserts of small lists, because shifting contiguous memory is cheap and every hop of a list walk can be a cache miss. Lists shine when the program already holds node pointers.

Where linked lists are used

• Stacks and queues: stack (push and pop at the head) and queue (enqueue at the tail, dequeue at the head).
• Hash table buckets in separate chaining.
• LRU caches: a hash map points at the nodes of a doubly linked list.
• The Linux kernel's struct list_head: a circular doubly linked list embedded in other structs.
• Java's java.util.LinkedList: doubly linked, and get(i) walks from the nearer end, as on this page.
• The bottom level of a skip list is a sorted linked list.

See Array vs Linked List for the same operations run on an array beside a linked list, with steps and cache misses counted.

What the page leaves out

A tail pointer for the singly linked list (many implementations keep one, which makes append O(1) but not delete-last), sentinel (dummy) head nodes that remove the special cases at index 0, circular lists, search by value, XOR linked lists, unrolled lists that store several values per node, and lock-free concurrent lists. Real memory addresses are not drawn; the canvas places nodes in a row only to keep the arrows short.

References

Linked list (Wikipedia)

Doubly linked list (Wikipedia)

java.util.LinkedList (Java SE 21 API)

Linked Lists in Linux (kernel documentation)