AlgoViz
HomeLinked List

Introduction to Doubly LL

Easy

Each node also points backwards

Problem

A doubly linked list is a chain where each node stores a value plus two pointers: 'next' to the following node and 'prev' to the previous node, so you can walk in both directions.

In simple words

Like a singly list but each node also points back, so you can walk both ways.

The idea

A doubly linked list adds a prev pointer, so you can walk in either direction and delete a node given only that node. The cost is an extra pointer per node and the discipline of always updating both directions.

The trick

  • Every insert and delete must fix four pointers, not two.
  • Deleting a known node is O(1) here; in a singly linked list it needs the predecessor.
  • The head's prev and the tail's next are both null.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
0
1
2

Step 1 of 2. Here's the example — values = [1, 2, 3] Values: 1, 2, 3.

1/2
Optimal
timeO(n)spaceO(1)
1struct Node { val; prev; next }2// walk forward or backward using next / prev

Input

array
[1, 2, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
values = [1, 2, 3]
Output:
NULL <- 1 <-> 2 <-> 3 -> NULL

Finished the walkthrough? Add it to your streak.