Doubly Linked List

A doubly linked list is a linear data structure where elements are stored in nodes, and each node contains data and references to both the next and previous nodes in the sequence. It provides efficient insertion/deletion at both ends and allows bidirectional traversal.

Features

Bidirectional traversal - can traverse forward and backward
Dynamic size - grows and shrinks during runtime
Fast insertion/deletion at both ends (O(1))
Memory efficient - allocates memory as needed
Generic type support for type safety
Previous node references for efficient backward operations

Time Complexities

Operation	Time Complexity
Prepend	O(1)
Append	O(1)
Insert	O(n)
Remove First	O(1)
Remove Last	O(1)
Remove by Value	O(n)
Remove by Index	O(n)
Search	O(n)
Access by Index	O(n)

Basic Usage

Creating and Initializing

from algo.data_structs.lists.doubly_linked_list import DoublyLinkedList

# Create empty list
dll = DoublyLinkedList()

# Check if empty
print(dll.is_empty())  # True
print(len(dll))        # 0
print(dll.size())      # 0

Adding Elements

# Prepend elements (add to beginning)
dll.prepend(3)
dll.prepend(2)
dll.prepend(1)
print(list(dll))  # [1, 2, 3]

# Append elements (add to end)
dll.append(4)
dll.append(5)
print(list(dll))  # [1, 2, 3, 4, 5]

# Extend with multiple elements
dll.extend([6, 7, 8])
print(list(dll))  # [1, 2, 3, 4, 5, 6, 7, 8]

# Insert at specific position
dll.insert(0, 0)     # Insert at beginning
dll.insert(4, 3.5)   # Insert in middle
dll.insert(len(dll), 9)  # Insert at end
print(list(dll))     # [0, 1, 2, 3, 3.5, 4, 5, 6, 7, 8, 9]

Accessing Elements

# Get head and tail
print(dll.get_head())  # 0 (first element)
print(dll.get_tail())  # 9 (last element)

# Access by index
print(dll.get(0))   # 0 (first element)
print(dll.get(5))   # 4 (sixth element)

# Modify elements
dll.set(1, 10)
print(dll.get(1))   # 10

# Get list length
print(len(dll))     # 11
print(dll.size())   # 11

Removing Elements

# Remove first element
first = dll.remove_first()
print(first)       # 0
print(list(dll))   # [10, 2, 3, 3.5, 4, 5, 6, 7, 8, 9]

# Remove last element
last = dll.remove_last()
print(last)        # 9
print(list(dll))   # [10, 2, 3, 3.5, 4, 5, 6, 7, 8]

# Remove by value (first occurrence)
result = dll.remove(3.5)
print(result)      # True
print(list(dll))   # [10, 2, 3, 4, 5, 6, 7, 8]

# Remove by index
removed = dll.remove_at(0)
print(removed)     # 10
print(list(dll))   # [2, 3, 4, 5, 6, 7, 8]

# Clear all elements
dll.clear()
print(len(dll))    # 0

Bidirectional Traversal

dll = DoublyLinkedList()
dll.extend([1, 2, 3, 4, 5])

# Forward iteration
print("Forward:")
for item in dll:
    print(item)  # 1, 2, 3, 4, 5

# Backward iteration
print("Backward:")
for item in dll.reverse_iter():
    print(item)  # 5, 4, 3, 2, 1

# Get reversed iterator
reversed_dll = reversed(dll)
for item in reversed_dll:
    print(item)  # 5, 4, 3, 2, 1

Search Operations

dll = DoublyLinkedList()
dll.extend([1, 2, 3, 2, 4, 2])

# Find index of element (first occurrence)
print(dll.find(2))      # 1
print(dll.find(4))      # 4
print(dll.find(99))     # -1 (not found)

# Check if element exists
print(2 in dll)         # True
print(99 in dll)        # False

# Count occurrences
print(dll.count(2))     # 3
print(dll.count(1))     # 1
print(dll.count(99))    # 0 (non-existent)

List Manipulation

dll = DoublyLinkedList()
dll.extend([1, 2, 3, 4, 5])

# Reverse the list
dll.reverse()
print(list(dll))  # [5, 4, 3, 2, 1]

# Copy the list
dll_copy = dll.copy()
print(list(dll_copy))  # [5, 4, 3, 2, 1]

# Lists are independent
dll_copy.append(6)
print(len(dll))        # 5 (original unchanged)
print(len(dll_copy))   # 6 (copy modified)

# Convert to Python list
python_list = dll.to_list()
print(python_list)     # [5, 4, 3, 2, 1]
print(type(python_list))  # <class 'list'>

Working with Different Types

Strings

str_dll = DoublyLinkedList()
str_dll.extend(['apple', 'banana', 'cherry'])

print(str_dll.find('banana'))   # 1
print(str_dll.count('apple'))   # 1
print('cherry' in str_dll)      # True

# Backward iteration with strings
for item in str_dll.reverse_iter():
    print(item)  # cherry, banana, apple

Mixed Types

mixed_dll = DoublyLinkedList()
mixed_dll.extend([1, 'hello', 3.14, True])

print(len(mixed_dll))    # 4
print(mixed_dll.get(1))  # 'hello'
print(mixed_dll.get(3))  # True

Custom Objects

class Person:
    def __init__(self, name: str, age: int):
        self.name = name
        self.age = age

    def __eq__(self, other):
        return isinstance(other, Person) and self.name == other.name

    def __str__(self):
        return f"Person({self.name}, {self.age})"

people = DoublyLinkedList()
alice = Person("Alice", 30)
bob = Person("Bob", 25)

people.extend([alice, bob])
print(people.count(alice))    # 1
print(people.find(bob))       # 1
print(alice in people)        # True

# Traverse people backward
for person in people.reverse_iter():
    print(person)  # Person(Bob, 25), Person(Alice, 30)

Performance Characteristics

Insertion Performance

Prepend: O(1) - Fast as it only modifies the head
Append: O(1) - Fast as it only modifies the tail (unlike singly linked list)
Insert at arbitrary position: O(n) - Must traverse to position

dll = DoublyLinkedList()

# Fast prepend operations
for i in range(1000):
    dll.prepend(i)  # O(1) each

# Fast append operations (advantage over singly linked list)
for i in range(1000):
    dll.append(i)   # O(1) each

Removal Performance

Remove first: O(1) - Direct access to head
Remove last: O(1) - Direct access to tail (advantage over singly linked list)
Remove by value/index: O(n) - May need to traverse

dll = DoublyLinkedList()
dll.extend(range(1000))

# Fast removal from both ends
first = dll.remove_first()  # O(1)
last = dll.remove_last()    # O(1)

Memory Efficiency

Doubly linked lists use more memory per node than singly linked lists due to the additional previous pointer:

# Memory grows with elements (more overhead than singly linked list)
dll = DoublyLinkedList()
for i in range(10):
    dll.append(i)  # Each append allocates one new node with prev/next pointers

# Memory freed when elements removed
dll.clear()  # All nodes can be garbage collected

Error Handling

dll = DoublyLinkedList()

# Index errors for empty list
try:
    dll.get(0)  # IndexError: list index out of range
except IndexError:
    print("Cannot access empty list")

try:
    dll.remove_first()  # IndexError: remove from empty list
except IndexError:
    print("Cannot remove from empty list")

try:
    dll.remove_last()  # IndexError: remove from empty list
except IndexError:
    print("Cannot remove from empty list")

# Index errors for invalid indices
dll.extend([1, 2, 3])
try:
    dll.get(5)  # IndexError: list index out of range
except IndexError:
    print("Index out of range")

try:
    dll.insert(-1, 5)  # IndexError: negative index not allowed
except IndexError:
    print("Invalid insert index")

# Value error for non-existent elements
try:
    dll.remove(99)  # Returns False (doesn't raise error)
    print("Element not found")
except:
    pass

String Representation

dll = DoublyLinkedList()
dll.extend([1, 2, 3])

print(str(dll))   # DoublyLinkedList([None <- 1 <-> 2 <-> 3 -> None])
print(repr(dll))  # DoublyLinkedList(size=3, head=DoublyListNode(1), tail=DoublyListNode(3))

# Empty list representation
empty_dll = DoublyLinkedList()
print(str(empty_dll))  # DoublyLinkedList([])

Common Patterns

Building from Iterables

# From list
dll = DoublyLinkedList()
dll.extend([1, 2, 3, 4, 5])

# From tuple
dll2 = DoublyLinkedList()
dll2.extend((1, 2, 3))

# From range
dll3 = DoublyLinkedList()
dll3.extend(range(10))

# From another doubly linked list
dll4 = DoublyLinkedList()
dll4.extend(dll)  # Copy elements from dll

Deque-like Usage (Double-ended Queue)

deque = DoublyLinkedList()

# Add to both ends efficiently
deque.prepend("first")    # Add to front
deque.append("last")      # Add to back
deque.prepend("new_first")
deque.append("new_last")

print(list(deque))  # ['new_first', 'first', 'last', 'new_last']

# Remove from both ends efficiently
front = deque.remove_first()  # O(1)
back = deque.remove_last()    # O(1)
print(front, back)  # new_first new_last

Stack-like Usage (LIFO)

stack = DoublyLinkedList()

# Push elements (can use either end)
stack.append(1)    # Push to back
stack.append(2)
stack.append(3)

# Pop elements from same end
while not stack.is_empty():
    item = stack.remove_last()  # Pop from back
    print(item)  # 3, 2, 1

Queue-like Usage (FIFO)

queue = DoublyLinkedList()

# Enqueue (add to back)
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue (remove from front)
while not queue.is_empty():
    item = queue.remove_first()
    print(item)  # 1, 2, 3

Palindrome Checking

def is_palindrome_dll(dll):
    """Check if doubly linked list represents a palindrome."""
    if dll.is_empty() or len(dll) == 1:
        return True

    # Use bidirectional iteration
    forward_iter = iter(dll)
    backward_iter = dll.reverse_iter()

    for _ in range(len(dll) // 2):
        if next(forward_iter) != next(backward_iter):
            return False

    return True

# Test palindrome
palindrome_dll = DoublyLinkedList()
palindrome_dll.extend([1, 2, 3, 2, 1])
print(is_palindrome_dll(palindrome_dll))  # True

non_palindrome_dll = DoublyLinkedList()
non_palindrome_dll.extend([1, 2, 3, 4, 5])
print(is_palindrome_dll(non_palindrome_dll))  # False

Window/Sliding Operations

def sliding_window_max(dll, window_size):
    """Find maximum in each sliding window."""
    if len(dll) < window_size:
        return []

    result = []
    dll_list = dll.to_list()

    for i in range(len(dll_list) - window_size + 1):
        window = dll_list[i:i + window_size]
        result.append(max(window))

    return result

# Example usage
data = DoublyLinkedList()
data.extend([1, 3, 2, 5, 4, 6, 8, 7])
windows = sliding_window_max(data, 3)
print(windows)  # [3, 5, 5, 6, 8, 8]

Filtering Elements

dll = DoublyLinkedList()
dll.extend(range(10))

# Remove all even numbers
i = 0
while i < len(dll):
    if dll.get(i) % 2 == 0:
        dll.remove_at(i)
    else:
        i += 1

print(list(dll))  # [1, 3, 5, 7, 9]

Merging Lists

dll1 = DoublyLinkedList()
dll1.extend([1, 3, 5])

dll2 = DoublyLinkedList()
dll2.extend([2, 4, 6])

# Merge dll2 into dll1
dll1.extend(dll2)
print(list(dll1))  # [1, 3, 5, 2, 4, 6]

# Merge at specific position
dll3 = DoublyLinkedList()
dll3.extend([10, 20])

for i, item in enumerate(dll2):
    dll3.insert(i + 1, item)  # Insert after first element

print(list(dll3))  # [10, 2, 4, 6, 20]

Use Cases

When to Use Doubly Linked Lists

Good for:

Frequent insertion/deletion at both ends
Bidirectional traversal requirements
Implementing deques or double-ended queues
Undo/redo functionality with navigation
Browser history with back/forward navigation
Music playlists with previous/next functionality

Examples:

href="#__codelineno-23-1"># Browser history with navigation class="k">class BrowserHistory: def __init__(self): self.history = DoublyLinkedList() self.current_pos = -1 def visit(self, url): # Remove any forward history while len(self.history) > self.current_pos + 1: self.history.remove_last() self.history.append(url) self.current_pos += 1 def back(self): if self.current_pos > 0: self.current_pos -= 1 return self.history.get(self.current_pos) return None def forward(self): if self.current_pos < len(self.history) - 1: self.current_pos += 1 return self.history.get(self.current_pos) return None class="c1"># Text editor with undo/redo class="k">class TextEditor: def __init__(self): self.actions = DoublyLinkedList() self.current_pos = -1 def execute(self, action): # Remove any redo history while len(self.actions) > self.current_pos + 1: self.actions.remove_last() self.actions.append(action) self.current_pos += 1 def undo(self): if self.current_pos >= 0: action = self.actions.get(self.current_pos) self.current_pos -= 1 return action return None def redo(self): if self.current_pos < len(self.actions) - 1: self.current_pos += 1 return self.actions.get(self.current_pos) return None class="c1"># Cache with LRU eviction class="k">class LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = {} # key -> node self.order = DoublyLinkedList() # most recent first def get(self, key): if key in self.cache: # Move to front self.order.remove(key) self.order.prepend(key) return self.cache[key] return None def put(self, key, value): if key in self.cache: # Update existing self.cache[key] = value self.order.remove(key) self.order.prepend(key) else: # Add new if len(self.order) >= self.capacity: # Evict least recent lru_key = self.order.remove_last() del self.cache[lru_key] self.cache[key] = value self.order.prepend(key)

When NOT to Use Doubly Linked Lists

Avoid for:

Frequent random access by index
Memory-constrained environments (higher overhead than singly linked)
Simple sequential processing (singly linked list sufficient)
Cache-friendly memory access patterns

Better alternatives:

# For random access, use dynamic array
from algo.data_structs.arrays.dynamic_array import DynamicArray
arr = DynamicArray()  # Better for arr[index] operations

# For simple stack/queue, use collections.deque
from collections import deque
efficient_deque = deque()  # Optimized C implementation

# For memory efficiency with forward-only access
from algo.data_structs.lists.singly_linked_list import SinglyLinkedList
sll = SinglyLinkedList()  # Lower memory overhead

Node Structure

The underlying DoublyListNode class provides the building blocks:

from algo.data_structs.lists.doubly_linked_list import DoublyListNode

# Create individual nodes
node1 = DoublyListNode(1)
node2 = DoublyListNode(2)
node3 = DoublyListNode(3)

# Link nodes manually
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2

print(node1.data)    # 1
print(node1.next)    # node2
print(node1.prev)    # None
print(node2.prev)    # node1
print(node2.next)    # node3

# String representation
print(str(node1))    # "1"
print(repr(node1))   # "DoublyListNode(1)"

Performance Comparison

Operation	Doubly Linked List	Singly Linked List	Dynamic Array
Prepend	O(1)	O(1)	O(n)
Append	O(1)	O(n)	O(1) amortized
Insert Middle	O(n)	O(n)	O(n)
Remove First	O(1)	O(1)	O(n)
Remove Last	O(1)	O(n)	O(1)
Access by Index	O(n)	O(n)	O(1)
Search	O(n)	O(n)	O(n)
Bidirectional Traversal	✓	✗	✓
Memory Overhead	Higher	Lower	Medium

Advanced Features

Custom Iteration Patterns

dll = DoublyLinkedList()
dll.extend([1, 2, 3, 4, 5])

# Skip every other element
def skip_iter(dll, step=2):
    current_index = 0
    for item in dll:
        if current_index % step == 0:
            yield item
        current_index += 1

for item in skip_iter(dll):
    print(item)  # 1, 3, 5

# Backward skip iteration
def backward_skip_iter(dll, step=2):
    items = list(dll.reverse_iter())
    for i in range(0, len(items), step):
        yield items[i]

for item in backward_skip_iter(dll):
    print(item)  # 5, 3, 1

List Comparison

def compare_lists(dll1, dll2):
    """Compare two doubly linked lists element by element."""
    if len(dll1) != len(dll2):
        return False

    for item1, item2 in zip(dll1, dll2):
        if item1 != item2:
            return False

    return True

dll1 = DoublyLinkedList()
dll1.extend([1, 2, 3])

dll2 = DoublyLinkedList()
dll2.extend([1, 2, 3])

print(compare_lists(dll1, dll2))  # True

API Reference

Doubly Linked List Implementation

A doubly linked list is a linear data structure where each element (node) contains data and references to both the next and previous nodes in the sequence. This provides bidirectional traversal capabilities compared to singly linked lists.

Key Features:

Dynamic size allocation
Efficient insertion/deletion at both ends
Bidirectional traversal
No memory waste (allocates exactly what's needed)

Time Complexities:

Access: O(n) - must traverse from head or tail
Search: O(n) - linear search required
Insertion: O(1) at head/tail, O(n) at arbitrary position
Deletion: O(1) at head/tail, O(n) at arbitrary position
Append/Prepend: O(1)

Space Complexity: O(n)

`DoublyLinkedList()`

Bases: Generic[T]

A doubly linked list implementation with comprehensive operations.

This implementation maintains references to both head and tail nodes and tracks the size for efficient length operations.

Initialize an empty doubly linked list.

`contains(value)`

Check if a value exists in the list.

`iter()`

Return an iterator over the list elements.

`len()`

Return the number of elements in the list.

`repr()`

Return detailed string representation for debugging.

`str()`

Return string representation of the list.

`append(data)`

Add an element to the end of the list.

Time Complexity: O(1)

Parameters:

Name	Type	Description	Default
`data`	`T`	Element to add	required

`clear()`

Remove all elements from the list.

Time Complexity: O(1)

`copy()`

Create a shallow copy of the list.

Time Complexity: O(n)

Returns:

Type	Description
`DoublyLinkedList[T]`	A new DoublyLinkedList with the same elements

`count(data)`

Count the number of occurrences of the specified element.

Time Complexity: O(n) - must traverse the entire list

Parameters:

Name	Type	Description	Default
`data`	`T`	Element to count	required

Returns:

Type	Description
`int`	Number of occurrences

`extend(iterable)`

Extend the list by appending all elements from the iterable.

Time Complexity: O(k) where k is the number of elements to add

Parameters:

Name	Type	Description	Default
`iterable`		Iterable containing elements to add	required

`find(data)`

Find the index of the first occurrence of the specified element.

Time Complexity: O(n) - may need to traverse the entire list

Parameters:

Name	Type	Description	Default
`data`	`T`	Element to find	required

Returns:

Type	Description
`int`	Index of the first occurrence, or -1 if not found

`get(index)`

Get the element at the specified index.

Time Complexity: O(n) - may need to traverse to the position

Parameters:

Name	Type	Description	Default
`index`	`int`	Index of element to get (0-based)	required

Returns:

Type	Description
`T`	The element at the specified index

Raises:

Type	Description
`IndexError`	If index is out of range

`get_head()`

Get the first element without removing it.

Time Complexity: O(1)

Returns:

Type	Description
`Optional[T]`	The first element, or None if list is empty

`get_tail()`

Get the last element without removing it.

Time Complexity: O(1)

Returns:

Type	Description
`Optional[T]`	The last element, or None if list is empty

`insert(index, data)`

Insert an element at the specified index.

Time Complexity: O(n) - may need to traverse to the position

Parameters:

Name	Type	Description	Default
`index`	`int`	Index where to insert (0-based)	required
`data`	`T`	Element to insert	required

Raises:

Type	Description
`IndexError`	If index is out of valid range

`is_empty()`

Check if the list is empty.

Returns:

Type	Description
`bool`	True if the list is empty, False otherwise

`prepend(data)`

Add an element to the beginning of the list.

Time Complexity: O(1)

Parameters:

Name	Type	Description	Default
`data`	`T`	Element to add	required

`remove(data)`

Remove the first occurrence of the specified element.

Time Complexity: O(n) - may need to traverse the entire list

Parameters:

Name	Type	Description	Default
`data`	`T`	Element to remove	required

Returns:

Type	Description
`bool`	True if element was found and removed, False otherwise

`remove_at(index)`

Remove and return the element at the specified index.

Time Complexity: O(n) - may need to traverse to the position

Parameters:

Name	Type	Description	Default
`index`	`int`	Index of element to remove (0-based)	required

Returns:

Type	Description
`T`	The removed element

Raises:

Type	Description
`IndexError`	If index is out of range

`remove_first()`

Remove and return the first element.

Time Complexity: O(1)

Returns:

Type	Description
`T`	The removed element

Raises:

Type	Description
`IndexError`	If the list is empty

`remove_last()`

Remove and return the last element.

Time Complexity: O(1)

Returns:

Type	Description
`T`	The removed element

Raises:

Type	Description
`IndexError`	If the list is empty

`reverse()`

Reverse the list in place.

Time Complexity: O(n) Space Complexity: O(1)

`reverse_iterator()`

Return an iterator that traverses the list in reverse order.

Time Complexity: O(n) for complete traversal

Returns:

Type	Description
`Iterator[T]`	Iterator yielding elements from tail to head

`set(index, data)`

Set the element at the specified index.

Time Complexity: O(n) - may need to traverse to the position

Parameters:

Name	Type	Description	Default
`index`	`int`	Index of element to set (0-based)	required
`data`	`T`	New value for the element	required

Raises:

Type	Description
`IndexError`	If index is out of range

`size()`

Get the number of elements in the list.

Returns:

Type	Description
`int`	The number of elements

`to_list()`

Convert the linked list to a Python list.

Time Complexity: O(n)

Returns:

Type	Description
`list[T]`	A Python list containing all elements

`DoublyListNode(data, prev_node=None, next_node=None)`

Bases: Generic[T]

A node in a doubly linked list.

Each node contains data and references to both the next and previous nodes.

Initialize a new doubly linked list node.

Parameters:

Name	Type	Description	Default
`data`	`T`	The data to store in this node	required
`prev_node`	`Optional[DoublyListNode[T]]`	Reference to the previous node (default: None)	`None`
`next_node`	`Optional[DoublyListNode[T]]`	Reference to the next node (default: None)	`None`

`repr()`

Return detailed string representation for debugging.

`str()`

Return string representation of the node.

Doubly Linked List

Features

Time Complexities

Basic Usage

Creating and Initializing

Adding Elements

Accessing Elements

Removing Elements

Bidirectional Traversal

Search Operations

List Manipulation

Working with Different Types

Strings

Mixed Types

Custom Objects

Performance Characteristics

Insertion Performance

Removal Performance

Memory Efficiency

Error Handling

String Representation

Common Patterns

Building from Iterables

Deque-like Usage (Double-ended Queue)

Stack-like Usage (LIFO)

Queue-like Usage (FIFO)

Palindrome Checking

Window/Sliding Operations

Filtering Elements

Merging Lists

Use Cases

When to Use Doubly Linked Lists

When NOT to Use Doubly Linked Lists

Node Structure

Performance Comparison

Advanced Features

Custom Iteration Patterns

List Comparison

API Reference

DoublyLinkedList()

__contains__(value)

__iter__()

__len__()

__repr__()

__str__()

append(data)

clear()

copy()

count(data)

extend(iterable)

find(data)

get(index)

get_head()

get_tail()

insert(index, data)

is_empty()

prepend(data)

remove(data)

remove_at(index)

remove_first()

remove_last()

reverse()

reverse_iterator()

set(index, data)

size()

to_list()

DoublyListNode(data, prev_node=None, next_node=None)

__repr__()

__str__()

`DoublyLinkedList()`

`contains(value)`

`iter()`

`len()`

`repr()`

`str()`

`append(data)`

`clear()`

`copy()`

`count(data)`

`extend(iterable)`

`find(data)`

`get(index)`

`get_head()`

`get_tail()`

`insert(index, data)`

`is_empty()`

`prepend(data)`

`remove(data)`

`remove_at(index)`

`remove_first()`

`remove_last()`

`reverse()`

`reverse_iterator()`

`set(index, data)`

`size()`

`to_list()`

`DoublyListNode(data, prev_node=None, next_node=None)`

`repr()`

`str()`