707. Design Linked List

Medium

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the index^th node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the index^th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the index^th node in the linked list, if the index is valid.

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

0 <= index, val <= 1000
Please do not use the built-in LinkedList library.
At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.


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

class MyLinkedList:
    def __init__(self):
        self.sentinel_head = ListNode(0)
        self.sentinel_tail = ListNode(0)
        self.sentinel_head.next = self.sentinel_tail
        self.sentinel_tail.prev = self.sentinel_head
        self.size = 0

    def show(self):
        node = self.sentinel_head.next
        for _ in range(self.size):
            print(node.val, end=" ")
            node = node.next
        print()


    def addAtHead(self, value):
        new_head = ListNode(value, self.sentinel_head.next, self.sentinel_head)
        # updating old head ponters
        self.sentinel_head.next.prev = new_head
        self.sentinel_head.next = new_head
        self.size+=1

    def addAtTail(self, value):
        new_tail = ListNode(value, self.sentinel_tail, self.sentinel_tail.prev)
        self.sentinel_tail.prev.next = new_tail
        self.sentinel_tail.prev  = new_tail
        self.size+=1

    def addAtIndex(self, index, value):

        if index > self.size:
            return 

        if index < 0:
            index = 0

        # decide shortest node index position

        if index < self.size-index: # head is closer

            pred = self.sentinel_head
            for _ in range(index):
                pred = pred.next

            succ = pred.next                
            # adding node
            new_node = ListNode(value, succ, pred)
            pred.next = new_node
            succ.prev = new_node

        else: # tail is closer
            succ = self.sentinel_tail

            for _ in range(self.size-index):
                succ = succ.prev

            pred = succ.prev
            # new node
            new_node = ListNode(value, succ, pred)
            succ.prev = new_node
            pred.next = new_node

        self.size+=1


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

        # find predecessor and successor of the node to be deleted
        if index < self.size - index:
            pred = self.sentinel_head
            for _ in range(index):
                pred = pred.next
            succ = pred.next.next
        else:
            succ = self.sentinel_tail
            for _ in range(self.size - index - 1):
                succ = succ.prev
            pred = succ.prev.prev

        # delete pred.next 
        self.size -= 1
        pred.next = succ
        succ.prev = pred


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

        if index < (self.size//2): # head
            node = self.sentinel_head
            for _ in range(index+1):
                node = node.next

            return node.val
        else:
            node = self.sentinel_tail
            for _ in range(self.size-index):
                node = node.prev
            return node.val

707. Design Linked List

Random Note