Doubly Linked List: Two-Way Nodes and Operations

A doubly linked list is a linked list whose nodes carry two pointers — prev and next — so you can walk the chain forward and backward. That extra back-link makes it possible to delete a node, or insert before it, in O(1) when you already hold the node, which a singly linked list cannot do. The cost is one more pointer per node and more links to keep consistent.

The node structure

Each node stores its value plus links to both neighbors. The head’s prev and the tail’s next are null.

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int v) : data(v), prev(nullptr), next(nullptr) {}
};

class Node {
    int data;
    Node prev;
    Node next;
    Node(int v) { data = v; prev = null; next = null; }
}

class Node {
  constructor(value) {
    this.data = value;
    this.prev = null;
    this.next = null;
  }
}

class Node:
    def __init__(self, value):
        self.data = value
        self.prev = None
        self.next = None

Insert at the front

Link the new node to the old head in both directions, then move the head. O(1).

Node* pushFront(Node* head, int value) {
    Node* node = new Node(value);
    node->next = head;
    if (head != nullptr) head->prev = node;
    return node; // new head
}

Node pushFront(Node head, int value) {
    Node node = new Node(value);
    node.next = head;
    if (head != null) head.prev = node;
    return node; // new head
}

function pushFront(head, value) {
  const node = new Node(value);
  node.next = head;
  if (head !== null) head.prev = node;
  return node; // new head
}

def push_front(head, value):
    node = Node(value)
    node.next = head
    if head is not None:
        head.prev = node
    return node  # new head

Delete a node in O(1)

Here the back-link pays off. Given any node, splice it out by joining its neighbors directly — no need to walk from the head to find the predecessor.

Node* removeNode(Node* head, Node* node) {
    if (node->prev != nullptr) node->prev->next = node->next;
    else head = node->next;                 // node was the head
    if (node->next != nullptr) node->next->prev = node->prev;
    delete node;
    return head;
}

Node removeNode(Node head, Node node) {
    if (node.prev != null) node.prev.next = node.next;
    else head = node.next;                  // node was the head
    if (node.next != null) node.next.prev = node.prev;
    return head;
}

function removeNode(head, node) {
  if (node.prev !== null) node.prev.next = node.next;
  else head = node.next;                    // node was the head
  if (node.next !== null) node.next.prev = node.prev;
  return head;
}

def remove_node(head, node):
    if node.prev is not None:
        node.prev.next = node.next
    else:
        head = node.next                     # node was the head
    if node.next is not None:
        node.next.prev = node.prev
    return head

Traverse backward

Because each node knows its predecessor, you can print the list in reverse starting from the tail — impossible in a singly list without extra work.

void printReverse(Node* tail) {
    for (Node* cur = tail; cur != nullptr; cur = cur->prev)
        std::cout << cur->data << " ";
}

void printReverse(Node tail) {
    for (Node cur = tail; cur != null; cur = cur.prev)
        System.out.print(cur.data + " ");
}

function printReverse(tail) {
  for (let cur = tail; cur !== null; cur = cur.prev)
    console.log(cur.data);
}

def print_reverse(tail):
    cur = tail
    while cur is not None:
        print(cur.data)
        cur = cur.prev

Complexity and trade-offs

Operation	Singly	Doubly
Insert at front	O(1)	O(1)
Delete given a node	O(n)*	O(1)
Traverse backward	O(n) with extra work	O(1) per step
Memory per node	1 pointer	2 pointers

*Singly needs the previous node, so you must walk from the head.

For beginners: The golden rule is to fix up both directions. Whenever you change a node’s next, ask “what should the other node’s prev be now?” — and vice versa. A half-updated link silently corrupts the list.

Going deeper: A common production technique is a sentinel (dummy) head and tail node. With permanent boundary nodes, no operation ever hits a null neighbor, so you can drop the special cases above and the code becomes uniform. This is how an LRU cache keeps its eviction list.

When to use a doubly linked list

Choose a doubly linked list when you need to traverse both ways, or remove/insert relative to a node you already hold in O(1) — the backbone of a deque and an LRU cache. If you only ever move forward, the lighter singly linked list saves a pointer per node.

Next: the circular linked list, or the full set of linked list operations.