Problem statement

https://leetcode.com/problems/design-linked-list/

Solution

Not difficult problem, but you need to code quite a lot. It is simpler to work with double-linked list with two sentinels: head and tail.

Complexity

Complexity of get(index) is O(index), complexity of {addAtIndex(index, val) and deleteAtIndex(index) is also O(index); complexity of addAtHead(val) is O(1) and complexity of addAtTail(val) is O(n) now, but for doubly-lined lists it can be reduced to O(1). Space complexity is O(n) for list with $n$ elements.

Code

class ListNode:
    def __init__(self, val=0, nxt=None, prv=None):
        self.val = val
        self.next = nxt
        self.prev = prv

class MyLinkedList:
    def __init__(self):
        self.head = ListNode(None)
        self.tail = ListNode(None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.len = 0
        
    def move_right(self, start, steps):
        for _ in range(steps):
            start = start.next
        return start
        
    def get(self, index):
        if index not in range(0, self.len): return -1
        return self.move_right(self.head, index + 1).val

    def addAtHead(self, val):
        self.addAtIndex(0, val)

    def addAtTail(self, val):
        self.addAtIndex(self.len, val)
        
    def addAtIndex(self, index, val):
        if index not in range(0, self.len+1): return
        start = self.move_right(self.head, index)
        nxt = start.next
        NewNode = ListNode(val)
        start.next = NewNode
        NewNode.prev = start
        NewNode.next = nxt
        nxt.prev = NewNode
        self.len += 1

    def deleteAtIndex(self, index):
        if index not in range(0, self.len): return -1
        start = self.move_right(self.head, index)
        nxt = start.next.next
        start.next = nxt
        nxt.prev = start
        self.len -= 1