Skip to content
Back to Data StructuresAll lessons

Data Structures

Doubly Linked List

Add to the front or back: O(1) · Find an item: O(n) · Remove a node you already have: O(1), since you don't need to search for its neighbors.

The idea, in plain English

A doubly linked list is like a train. Each car connects to the car in front and the car behind. A regular linked list only lets you walk forward. This one lets you walk backward too.

How it works

  1. 1Each node stores a value, a link to the next node, and a link to the previous node.
  2. 2The list remembers both the first node, called the head, and the last node, called the tail.
  3. 3Walk forward by following .next links, or backward by following .prev links.

When you'd use it

Use this for anything you browse in both directions, like a browser's back and forward history, or a music player's next and previous track.

Common beginner mistakes

  • When you insert or remove a node, update both .next and .prev. If you forget one, you break the chain in that direction.
  • Remember to update the tail pointer when you add to the end. If you forget, finding the last node needs a slow walk from the head.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Forward: 10 -> 20 -> 30
Backward: 30 -> 20 -> 10

See it in motion

Walk it both waysDoubly linked listAdd to the front or back: O(1) · Find an item: O(n) · Remove a node you already have: O(1), since you don't need to search for its neighbors.
102030headtail

A doubly linked list: every node points to the next node AND the previous one.

3
Length
ready
Operation
1/14
Step
0.0s
Time
Cursor herePointer rewiredInserted / doneIdle .next / .prev

Not sure this is the right topic? See the learning paths → or where this leads →