UP | HOME

DoublyLinkedLists

Doubly Linked List Cheat Sheet

Node Structure

class Node:
    data          # the value
    prev          # pointer to previous node (None if head)
    next          # pointer to next node (None if tail)

Core Operations + Pseudocode

Operation Time Complexity Description & Pseudocode
Create empty list O(1) head = None, tail = None, size = 0
Insert at Head O(1) Add new node before current head=<br>insertfirst(value)<br> newnode = Node(value)<br> newnode.next = head<br> newnode.prev = None<br> if head != None:<br> head.prev = newnode<br> head = newnode<br> if tail = None: # list was empty<br> tail = new_node<br> size + 1<br>=
Insert at Tail O(1) Add new node after current tail=<br>insertlast(value)<br> newnode = Node(value)<br> newnode.next = None<br> newnode.prev = tail<br> if tail != None:<br> tail.next = newnode<br> tail = newnode<br> if head = None: # list was empty<br> head = new_node<br> size + 1<br>=
Insert After a Node O(1) Given pointer to a node=<br>insertafter(node, value)<br> if node = None: return<br> new_node = Node(value)<br> new_node.next = node.next<br> new_node.prev = node<br> node.next = new_node<br> if new_node.next ! None:<br> newnode.next.prev = newnode<br> else:<br> tail = newnode # inserted at end<br> size += 1<br>=
Insert Before a Node O(1) Given pointer to a node=<br>insertbefore(node, value)<br> if node = None: return<br> new_node = Node(value)<br> new_node.prev = node.prev<br> new_node.next = node<br> node.prev = new_node<br> if new_node.prev ! None:<br> newnode.prev.next = newnode<br> else:<br> head = newnode # inserted at beginning<br> size += 1<br>=
Delete Head O(1) <br>delete_first()<br> if head = None: return<br> if head.next = None: # only one node<br> head = tail = None<br> else:<br> head = head.next<br> head.prev = None<br> size - 1<br>=
Delete Tail O(1) <br>delete_last()<br> if tail = None: return<br> if tail.prev = None: # only one node<br> head = tail = None<br> else:<br> tail = tail.prev<br> tail.next = None<br> size - 1<br>=
Delete Specific Node O(1) Given pointer to the node to delete=<br>deletenode(node)<br> if node = None: return<br> if node.prev ! None:<br> node.prev.next = node.next<br> else:<br> head = node.next # deleting head<br> if node.next != None:<br> node.next.prev = node.prev<br> else:<br> tail = node.prev # deleting tail<br> size -= 1<br>=
Search by Value O(n) <br>search(value)<br> curr = head<br> while curr ! None:<br> if curr.data = value:<br> return curr<br> curr = curr.next<br> return None<br>
Traverse Forward O(n) <br>traverse_forward()<br> curr = head<br> while curr ! None:<br> print(curr.data)<br> curr = curr.next<br>=
Traverse Backward O(n) <br>traverse_backward()<br> curr = tail<br> while curr ! None:<br> print(curr.data)<br> curr = curr.prev<br>=
Get Size O(1) or O(n) Keep a size variable → O(1)Or traverse → O(n)

Advantages of Doubly Linked List (vs Singly)

  • O(1) deletion of a node if you have the pointer
  • O(1) insert before/after a given node
  • Efficient reverse traversal
  • O(1) removal of last element (with tail pointer)

Keep this cheat sheet handy—almost every doubly-linked-list problem is just a clever combination of the O(1) insert/delete operations above!