DoublyLinkedList Design (with bidirectional search to perform faster)

Our Linked List will contains value next and tail value. We'll create sentinel node for next and tail. They'll just be there and won't have any other activity.

Steps:

1. Out Node will contains value, next and prev value.
2. We'll create a variable that will hold the size of the linked list.
3. Initially, we'll create sentinel head and tail with and point them to one another.
4. addAtHead: we will create a node and point the sentinel node to this.
5. addAtTail: we'll create a node and update sentinel tail.prev to our new node
6. addAtIndex:
7. We need to find the target node where we can Insert the new node.
8. We can handel add head and tail from this funtion also. By passing index as 0, and the (last_index +1), which is actually the size of the list will be enough for us.
9. We can just iterate from the start node and find the target node. Imagine, we need to add a node which is just 1 node before the tail node, we just need to do a lot of unnecessary work. We can easily reduce the work by finding whether the target node is closer to head or tail.
10. If the index is smaller than floor(size/2) then we can it is closer to head otherwise to tail. Right?
11. Then, We can calculate the number of loop we need to iterate. If head is closer then the number will be size of index. If tail is closer, (size-index) will be the number of loops.
12. We'll get the value of the predecessor and successor of the node. Then create the node and update them.
13. get: getting the target indexed value process is similar to insert one. Here we'll also find the short distance and return the value of the node.
14. deleteAtIndex: get predecessor and successor of the targeted node and update the predecessor.next = successor and successor.prev = 'predecessor

Note:

Used bidirectional search to perform faster.

Complexity Analysis:

Time & Space

1. addAtHead: O(1) and O(1)
2. addAtTail: O(1) andO(1)
3. addAtIndex: O(min(k, Size-k)) where k is the index, O(1)
4. get: O(min(k, Size-k)) where k is the index, O(1)
5. deleteAtIndex: O(min(k, Size-k)) where k is the index, O(1)

Here is my demo implementaion in Python 3.

class Node:
    def __init__(self, value, head = None, tail=None):
        self.value  = value
        self.next = head
        self.prev = tail


class DoublyLinkedList:

    def __init__(self):
        self.size = 0
        self.head = Node(0)
        self.tail = Node(0)

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

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

    def addAtTail(self, value):
        self.addAtIndex(self.size, value)

    def addAtIndex(self, index, value):

        # checking for invalid input
        if index < 0:
            index = 0

        elif index > self.size:
            return "Invalid index"

        # # adding value
        # if index == 0:
        #     # add at index
        #     node = Node(value, self.head.next, self.head)
        #     self.head.next = node

        # elif index == self.size:
        #     new_node = Node(value, None, self.tail)
        #     self.tail.prev = new_node

        # else:
        #     # adding node in other index

        if index < (self.size//2):
            # head is nearer
            pred = self.head
            for _ in range(index):
                pred = pred.next
            succ = pred.next

        else:
            # tail is nearer
            succ = self.tail
            for _ in range(self.size - (index) ):
                succ = succ.prev
            pred = succ.prev

            # new_node = Node(value, node.prev, node)
            # node.next = new_node

        self.size += 1
        new_node = Node(value, succ, pred)
        pred.next = new_node
        succ.prev = new_node


    def get(self, index):

        # invalid input check
        if index < 0:
            index = 0
        if index >= self.size:
            return

        # select head or tail which is nearer
        if index < (self.size // 2):
            # head
            node = self.head
            for _ in range(index+1):
                node = node.next
            return node.value

        else:
            # tail
            node = self.tail
            for _ in range(self.size - index):
                node = node.prev
            return node.value


    def deleteAtIndex(self, index):
        # invalid input check
        if index < 0:
            index = 0
        if index >= self.size:
            return

        # select head or tail which is nearer
        if index < (self.size // 2):
            # head
            prev = self.head
            for _ in range(index):
                prev = prev.next
            succ = prev.next.next

        else:
            # tail
            succ = self.tail
            for _ in range(self.size - index - 1):
                succ = succ.prev
            prev = succ.prev.prev


        prev.next = succ
        succ.prev = prev

For printing the list

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

    dll = DoublyLinkedList()
    dll.addAtHead(1)
    dll.addAtTail(2)
    dll.addAtHead(0)
    dll.addAtHead(-1)
    dll.addAtTail(9)
    dll.addAtIndex(5, 10)
    dll.show()
    dll.deleteAtIndex(0)
    dll.show()
    dll.addAtHead(99)
    dll.show()

Output of this Code:

-1 0 1 2 9 10 
0 1 2 9 10 0 
99 0 1 2 9 10 0