Basics

Design

Python

from typing import Optional


class DoublyLinkedListNode:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

    def __str__(self):
        return f"{self.val}{f' <-> {self.next}' if self.next else ''}"


class DoublyLinkedList:
    def __init__(self):
        self.sentinel_head = DoublyLinkedListNode(val=None)
        self.sentinel_tail = DoublyLinkedListNode(val=None, prev=self.sentinel_head)
        self.sentinel_head.next = self.sentinel_tail
        self.len = 0

    @property
    def head(self):
        if self.sentinel_head.next != self.sentinel_tail:
            return self.sentinel_head.next

    @property
    def tail(self):
        if self.sentinel_tail.prev != self.sentinel_head:
            return self.sentinel_tail.prev

    def goTo(self, index: int) -> Optional[DoublyLinkedListNode]:
        if index == -1:
            return self.sentinel_head
        elif index == self.len:
            return self.sentinel_tail
        elif index == self.len - 1:
            return self.sentinel_tail.prev
        elif index == self.len - 2:
            return self.sentinel_tail.prev.prev
        elif 0 <= index < self.len:
            p = self.head
            for _ in range(index):
                p = p.next
            return p

    def insert(self, index: int, val):
        if 0 <= index <= self.len:
            prev = self.goTo(index - 1)
            prev.next = DoublyLinkedListNode(val=val, prev=prev, next=prev.next)
            prev.next.next.prev = prev.next
            self.len += 1

    def insertAtHead(self, val):
        return self.insert(index=0, val=val)

    def insertAtTail(self, val):
        return self.insert(index=self.len, val=val)

    def get(self, index: int):
        if 0 <= index < self.len:
            return self.goTo(index).val
        return -1

    def remove(self, index: int):
        if 0 <= index < self.len:
            prev = self.goTo(index - 1)
            prev.next.next.prev = prev
            prev.next = prev.next.next
            self.len -= 1

    def __len__(self):
        return self.len

    def __str__(self):
        return str(self.sentinel_head.next)