Linked Lists

Doubly linked list operations with prev and next links

Linked Lists: Doubly Linked List

Doubly Linked Chain

Pick a doubly linked list operation to animate prev/next updates.

Insert Head and Insert Tail can update both sides of the link relationship in constant time when the right node references are available.

Delete relinks both neighbors, which is why doubly linked lists are often easier to update in the middle.

Move To Front mirrors the key LRU-cache behavior: detach a node from the middle and promote it to the head.

Insert Head

Time:O(1)

Space:O(1)

Insert Tail

Time:O(1)

Space:O(1)

Delete

Time:O(1)*

Space:O(1)

Move To Front

Time:O(1)

Space:O(1)

* Assuming you already have the node reference you want to remove.