Course contentsShow
← Computer Science
Lesson 398 of 2,8729. Stacks and QueuesFree lesson

Linked List Deque Implementation

Building a deque using a doubly linked list to enable constant-time operations at both ends.

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 head pointer to the first node
  • A tail pointer to the last node
  • A size counter 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.