Double Ended Lists

Overview

A double-ended list is a sequence that provides constant-time operations at both ends: adding/removing from the front and adding/removing from the back. It is typically implemented as a linked structure with explicit references to both the head and the tail. This enables efficient, predictable performance for queue-like and stack-like behaviors in the same structure.

Double-ended lists are closely related to deques (double-ended queues). In many libraries, a deque is the abstract interface, and a double-ended list is one of the concrete ways to implement that interface.

Core Operations (Typical API)

• push_front(x): insert x at the front
• push_back(x): insert x at the back
• pop_front(): remove and return the front element
• pop_back(): remove and return the back element
• front(): read the front element without removing
• back(): read the back element without removing
• is_empty(), size(): status and bookkeeping
• iteration from head to tail (and often tail to head, if doubly linked)

Time and Space Complexity

• push_front / push_back: O(1)
• pop_front / pop_back: O(1)
• Search by value or index: O(n) in linked implementations
• Space: O(n) for elements plus pointer overhead per node

Common Implementations

• Singly linked list with head and tail: constant-time at both ends for insertion/removal at ends, but removing from the back is not O(1) unless you maintain extra bookkeeping; hence singly linked is best for push_back/pop_front patterns.
• Doubly linked list: nodes have prev and next pointers; supports O(1) insertions and deletions at both ends and O(1) removal given a node reference.
• Circular list: tail.next points to head; often used with sentinel nodes to simplify edge cases.
• Array-backed ring buffer: not a linked list, but commonly used to implement a deque with excellent cache locality; capacity changes may require resizing.

Relationship to Other Concepts

• Deque ADT: a double-ended list is a common implementation strategy for deques.
• LRU cache: often implemented with a doubly linked list plus a hash map for O(1) updates and lookups.
• Sliding window and BFS: benefit from O(1) operations at both ends.

Pseudocode (Doubly Linked Version)

# Node with links in both directions
class Node:
    value
    prev
    next

class DoubleEndedList:
    head
    tail
    size

    def __init__():
        head = null
        tail = null
        size = 0

    def is_empty():
        return size == 0

    def push_front(x):
        n = new Node()
        n.value = x
        n.prev = null
        n.next = head
        if head != null:
            head.prev = n
        else:
            # list was empty; new node is also the tail
            tail = n
        head = n
        size += 1

    def push_back(x):
        n = new Node()
        n.value = x
        n.next = null
        n.prev = tail
        if tail != null:
            tail.next = n
        else:
            # list was empty; new node is also the head
            head = n
        tail = n
        size += 1

    def pop_front():
        if head == null: raise Empty
        x = head.value
        head = head.next
        if head != null:
            head.prev = null
        else:
            # became empty
            tail = null
        size -= 1
        return x

    def pop_back():
        if tail == null: raise Empty
        x = tail.value
        tail = tail.prev
        if tail != null:
            tail.next = null
        else:
            # became empty
            head = null
        size -= 1
        return x

Advantages

• Predictable O(1) operations at both ends
• Easy splicing: constant-time concatenation or node removal when references are known (doubly linked)
• No reallocation costs as with resizing arrays

Trade-offs and Pitfalls

• Memory overhead: each node stores pointer fields
• Poor cache locality compared to arrays
• Indexing by position is O(n)
• Edge cases: empty and single-element lists require careful handling
• Concurrency: operations require synchronization in multithreaded contexts

When to Use

• Implementing queues/deques where both ends are frequently modified
• LRU caches and eviction policies
• Undo/redo stacks that need efficient movement at both ends
• Streaming and scheduling where elements arrive and depart from ends

Comparisons

• Array list: O(1) random access, but insert/remove at front are O(n)
• Singly linked list: lighter weight but less flexible at the back without extra bookkeeping
• Array-backed deque: great cache locality and often faster in practice; may require resizing

Practice Ideas

1. Implement a double-ended list with a sentinel node to reduce edge-case branching.
2. Build a deque API and back it with both a doubly linked list and a ring buffer; compare performance.
3. Combine a hash map with a doubly linked list to implement an LRU cache.

Next Topic