Singly Linked Lists

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

from typing import Generic, Optional, TypeVar

T = TypeVar("T")


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


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

    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)
        node = ListNode(val)
        node.next = p.next
        p.next = node

        self.size += 1

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

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

        self.size -= 1

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

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

        return p

The key idea here is to use a dummy head node to avoid to write a lot of code, which would be used to check the validity of the head itself.

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).