DSA — Linear DS

Doubly Linked List

Each node has next AND prev pointers. O(1) delete with reference. Bidirectional traversal.

— min read
O(n)Access
O(1)Insert
O(n)Search
←Node→Bidirect.
2xPointers
// DOUBLY LINKED LIST
Use buttons to operate on the list
How It Works
Python Code
Complexity
Quiz
Practice
01
Node
data + next + prev.
self.val, self.next, self.prev
02
Push Front
4 pointer updates — O(1).
new.next=head; head.prev=new; head=new
03
Delete w/Ref
Use prev directly — O(1)!
node.prev.next=node.next; node.next.prev=node.prev
04
LRU Cache
Classic use: O(1) move-to-front.
Python — DLL Delete 
class DLL:
    def delete(self, node):  # O(1) with reference
        if node.prev: node.prev.next = node.next
        if node.next: node.next.prev = node.prev
O(1)
Del w/Ref
No need to find previous
O(1)
Both Ends
Push/pop head AND tail
2x
Space
Extra prev pointer per node
LRU
Use Case
Hash map + DLL = O(1) LRU
Main advantage of DLL over SLL for deletion?
Progress0 / 6 solved
6 problems · 4 PBC · 2 Startup
#1951 LRU Cache Amazon, Google PBC →
#1952 Design Browser History Meta PBC →
#1953 Flatten a Multilevel Doubly LL Microsoft, Meta PBC →
#1954 Reverse Linked List II Amazon, Google PBC →
#1955 Design Linked List Meesho STARTUP →
#1956 All O(1) Data Structure Zepto STARTUP →
← Singly Linked List