Linked List Deque Implementation
You'll learn how to build a deque using a doubly linked list to achieve constant-time insertions and deletions at both ends.
Why Use a Doubly Linked List?
A deque (double-ended queue) needs efficient operations at both the front and back. A doubly linked list is perfect for this because each node has pointers to both its predecessor and successor. With head and tail pointers, you can instantly access either end—no shifting elements like in arrays.
Core Structure
Your deque maintains three key attributes:
- A
headpointer to the first node - A
tailpointer to the last node - A
sizecounter for tracking elements
Each node contains data plus next and prev pointers.
The Key Operations
AddFront (push_front): Create a new node, set its next to current head, update the old head's prev, then move head to the new node. If the deque was empty, tail also points to this node. O(1) time.
AddBack (push_back): Create a new node, set its prev to current tail, update the old tail's next, then move tail to the new node. Handle the empty case similarly. O(1) time.
RemoveFront (pop_front): Save the head's data, move head to head->next, update the new head's prev to NULL, and deallocate the old node. If the deque becomes empty, set tail to NULL too. O(1) time.
RemoveBack (pop_back): Save the tail's data, move tail to tail->prev, update the new tail's next to NULL, and deallocate the old node. O(1) time.
Why This Works
Unlike array-based deques that eventually need wraparound logic, the linked list naturally grows and shrinks from either end without any reshuffling.
Key Takeaway: A doubly linked list deque provides true O(1) operations at both ends by maintaining head and tail pointers with bidirectional links between nodes.