Doubly Linked List

py_ds.datastructures.linked_lists.doubly_linked.DoublyLinkedList

DoublyLinkedList(items: Iterable[T] | None = None)

Bases: LinkedList[T]

A doubly linked list with forward and backward links.

Advantages over singly linked list include O(1) append (with tail pointer), O(1) tail access, bidirectional traversal, and more efficient deletion when node reference is known.

Initialize the doubly linked list with optional items.

Parameters:

Name	Type	Description	Default
items	Iterable[T] | None	Optional iterable of items to initialize the list with.	None

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def __init__(self, items: Iterable[T] | None = None) -> None:
    """Initialize the doubly linked list with optional items.

    Args:
        items: Optional iterable of items to initialize the list with.
    """
    self._head: _DoublyNode[T] | None = None
    self._tail: _DoublyNode[T] | None = None
    super().__init__(items)

Functions

append

append(value: T) -> None

Add a value to the end of the list.

Parameters:

Name	Type	Description	Default
value	T	The value to append to the list.	required

Time complexity: O(1).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def append(self, value: T) -> None:
    """Add a value to the end of the list.

    Args:
        value: The value to append to the list.

    Time complexity: O(1).
    """
    node = _DoublyNode(value)
    if self._head is None:
        self._head = self._tail = node
    else:
        self._tail.next = node
        node.prev = self._tail
        self._tail = node
    self._length += 1

prepend

prepend(value: T) -> None

Add a value to the beginning of the list.

Parameters:

Name	Type	Description	Default
value	T	The value to prepend to the list.	required

Time complexity: O(1).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def prepend(self, value: T) -> None:
    """Add a value to the beginning of the list.

    Args:
        value: The value to prepend to the list.

    Time complexity: O(1).
    """
    node = _DoublyNode(value)
    if self._head is None:
        self._head = self._tail = node
    else:
        node.next = self._head
        self._head.prev = node
        self._head = node
    self._length += 1

insert

insert(index: int, value: T) -> None

Insert a value at a specific index.

Parameters:

Name	Type	Description	Default
index	int	The position at which to insert the value.	required
value	T	The value to insert.	required

Raises:

Type	Description
IndexError	If index is out of bounds.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def insert(self, index: int, value: T) -> None:
    """Insert a value at a specific index.

    Args:
        index: The position at which to insert the value.
        value: The value to insert.

    Raises:
        IndexError: If index is out of bounds.

    Time complexity: O(n).
    """
    if index == self._length:
        self.append(value)
        return

    new_node = _DoublyNode(value)
    index_node = self._get_node_at(index)
    prev = index_node.prev

    new_node.next = index_node
    index_node.prev = new_node

    if prev:
        prev.next = new_node
        new_node.prev = prev
    else:
        self._head = new_node
    self._length += 1

remove

remove(value: T) -> None

Remove the first occurrence of value from the list.

Parameters:

Name	Type	Description	Default
value	T	The value to remove from the list.	required

Raises:

Type	Description
ValueError	If the value is not found.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def remove(self, value: T) -> None:
    """Remove the first occurrence of `value` from the list.

    Args:
        value: The value to remove from the list.

    Raises:
        ValueError: If the value is not found.

    Time complexity: O(n).
    """
    curr = self._head
    while curr and curr.value != value:
        curr = curr.next
    if curr is None or curr.value != value:
        raise ValueError('value not found')

    prev = curr.prev
    next_ = curr.next

    if prev:
        prev.next = next_
    else:
        self._head = next_
        if self._head:
            self._head.prev = None

    if next_:
        next_.prev = prev
    else:
        self._tail = prev
        if self._tail:
            self._tail.next = None
    self._length -= 1

pop

pop(index: int = -1) -> T

Remove and return the item at the given index.

Parameters:

Name	Type	Description	Default
index	int	0-based index, negative indexes supported (Python style). Defaults to -1 (last element).	-1

Returns:

Type	Description
T	The value at the specified index.

Raises:

Type	Description
IndexError	If the list is empty or index is invalid.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def pop(self, index: int = -1) -> T:
    """Remove and return the item at the given index.

    Args:
        index: 0-based index, negative indexes supported (Python style).
            Defaults to -1 (last element).

    Returns:
        The value at the specified index.

    Raises:
        IndexError: If the list is empty or index is invalid.

    Time complexity: O(n).
    """
    curr = self._get_node_at(index)
    value = curr.value
    prev, next_ = curr.prev, curr.next

    if prev:
        prev.next = next_
    else:
        self._head = next_

    if next_:
        next_.prev = prev
    else:
        self._tail = prev
    self._length -= 1
    return value

clear

clear() -> None

Remove all elements from the list.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def clear(self) -> None:
    """Remove all elements from the list.

    Time complexity: O(n).
    """
    self._head = self._tail = None
    self._length = 0

head

head() -> T | None

Return the first value in the list.

Returns:

Type	Description
T | None	The first value in the list, or None if the list is empty.

Time complexity: O(1).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def head(self) -> T | None:
    """Return the first value in the list.

    Returns:
        The first value in the list, or None if the list is empty.

    Time complexity: O(1).
    """
    return self._head.value if self._head else None

tail

tail() -> T | None

Return the last value in the list.

Returns:

Type	Description
T | None	The last value in the list, or None if the list is empty.

Time complexity: O(1).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def tail(self) -> T | None:
    """Return the last value in the list.

    Returns:
        The last value in the list, or None if the list is empty.

    Time complexity: O(1).
    """
    return self._tail.value if self._tail else None

reverse_iter

reverse_iter() -> Iterator[T]

Iterate through values from tail to head.

This is a doubly linked list advantage, allowing efficient reverse traversal.

Yields:

Type	Description
T	The values in the list from tail to head.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def reverse_iter(self) -> Iterator[T]:
    """Iterate through values from tail to head.

    This is a doubly linked list advantage, allowing efficient reverse
    traversal.

    Yields:
        The values in the list from tail to head.

    Time complexity: O(n).
    """
    curr = self._tail
    while curr:
        yield curr.value
        curr = curr.prev

__str__

__str__() -> str

Return a string representation of the linked list.

Returns:

Type	Description
str	A visual representation of the linked list.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/doubly_linked.py

def __str__(self) -> str:
    """Return a string representation of the linked list.

    Returns:
        A visual representation of the linked list.

    Time complexity: O(n).
    """
    if not self:
        return 'HEAD ⇆ TAIL'
    return 'HEAD ⇆ ' + ' ⇆ '.join(str(item) for item in self) + ' ⇆ TAIL'

find

find(value: T) -> int

Return the index of the first occurrence of a value.

Parameters:

Name	Type	Description	Default
value	T	The value to search for.	required

Returns:

Type	Description
int	The index of the first occurrence of the value.

Raises:

Type	Description
ValueError	If the value is not found in the list.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def find(self, value: T) -> int:
    """Return the index of the first occurrence of a value.

    Args:
        value: The value to search for.

    Returns:
        The index of the first occurrence of the value.

    Raises:
        ValueError: If the value is not found in the list.
    """
    for i, node_value in enumerate(self):
        if value == node_value:
            return i
    raise ValueError('value not found')

__len__

__len__() -> int

Return the number of elements in the list.

Returns:

Type	Description
int	The number of elements in the linked list.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __len__(self) -> int:
    """Return the number of elements in the list.

    Returns:
        The number of elements in the linked list.
    """
    return self._length

__bool__

__bool__() -> bool

Return the truthiness of the list.

Returns:

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

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __bool__(self) -> bool:
    """Return the truthiness of the list.

    Returns:
        False if the list is empty, True otherwise.
    """
    return self._length > 0

__getitem__

__getitem__(index: int) -> T

Get the value at the given index.

Parameters:

Name	Type	Description	Default
index	int	0-based index, negative indexes supported (Python style).	required

Returns:

Type	Description
T	The value at the specified index.

Raises:

Type	Description
IndexError	If the index is out of range.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __getitem__(self, index: int) -> T:
    """Get the value at the given index.

    Args:
        index: 0-based index, negative indexes supported (Python style).

    Returns:
        The value at the specified index.

    Raises:
        IndexError: If the index is out of range.
    """
    return self._get_node_at(index).value

__setitem__

__setitem__(index: int, value: T) -> None

Set item at the specified index.

Parameters:

Name	Type	Description	Default
index	int	The position at which to set the value. 0-based index, negative indexes supported (Python style).	required
value	T	The value to set.	required

Raises:

Type	Description
IndexError	If index is out of bounds.

Time complexity: O(n).

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __setitem__(self, index: int, value: T) -> None:
    """Set item at the specified index.

    Args:
        index: The position at which to set the value.
            0-based index, negative indexes supported (Python style).
        value: The value to set.

    Raises:
        IndexError: If index is out of bounds.

    Time complexity: O(n).
    """
    self._get_node_at(index).value = value

__iter__

__iter__() -> Iterator[T]

Iterate through values in the list.

Yields:

Type	Description
T	The values in the list from head to tail.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __iter__(self) -> Iterator[T]:
    """Iterate through values in the list.

    Yields:
        The values in the list from head to tail.
    """
    curr = self._head
    while curr:
        yield curr.value
        curr = curr.next

__repr__

__repr__() -> str

Return a string representation of the linked list.

Returns:

Type	Description
str	A string representation showing the class name and list contents.

Source code in src/py_ds/datastructures/linked_lists/singly_linked.py

def __repr__(self) -> str:
    """Return a string representation of the linked list.

    Returns:
        A string representation showing the class name and list contents.
    """
    return f'{self.__class__.__name__}({list(self)})'