Doubly Linked Lists

Let's use Design Linked List to design our Doubly Linked List.

from typing import Generic, Optional, TypeVar

T = TypeVar("T")


class ListNode(Generic[T]):
    def __init__(
        self,
        val: T,
        prev_ptr: Optional["ListNode"] = None,
        next_ptr: Optional["ListNode"] = None,
    ) -> None:
        self.val = val
        self.prev = prev_ptr
        self.next = next_ptr


class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head = ListNode(-1)
        self.tail = ListNode(-1)

        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        return self._getNodeAtIndex(index + 1).val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return

        p = self._getNodeAtIndex(index)
        n = p.next

        node = ListNode(val)
        node.prev = p
        node.next = n
        p.next = node
        n.prev = node

        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        p = self._getNodeAtIndex(index)
        n = p.next.next

        p.next = n
        n.prev = p

        self.size -= 1

    def _getNodeAtIndex(self, index: int) -> ListNode[int]:
        p = self.head

        for _ in range(index):
            p = p.next

        return p

As for the Singly Linked List, besides the dummy head node we need the dummy tail as well. For the same reason, we can use such nodes to avoid to write code to handle edge cases.

Except for addAtHead, which is $O (1)$ for the time complexity, all the other operations are $O (n)$ .

The space complexity is $O (1)$ for each operation, however, after $k$ operations we might end up having a list of $k$ elements (assuming that they are all valid consecutive insert operations).