What is Doubly Linked List? Write an algorithm to insert and delete a node in Doubly Linked List.

A Doubly Linked List (DLL) is a type of linked list in which each node contains a reference to the next node as well as the previous node in the sequence. This allows for more efficient operations such as insertion and deletion at both ends, and can be traversed in both directions (forward and backward).

Here's a simple representation of a node in a doubly linked list:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None

Each node has three attributes: data (to store the actual data), next (to point to the next node), and prev (to point to the previous node).

Algorithm to Insert a Node in a Doubly Linked List

1. Create a new node.
2. If the list is empty, point the head to the new node.
3. Otherwise, traverse to the end of the list and point the next of the last node to the new node and the prev of the new node to the last node.
4. If the insertion is at the beginning of the list, point the prev of the current head to the new node, the next of the new node to the current head, and then update the head to the new node.
5. If the insertion is at a specific position, traverse to the node before the position and adjust the next and prev pointers accordingly.

Here's a Python implementation of the insertion algorithm:

def insert(self, data, position=None):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    elif position is None:
        cur_node = self.head
        while cur_node.next:
            cur_node = cur_node.next
        cur_node.next = new_node
        new_node.prev = cur_node
    elif position == 0:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    else:
        cur_node = self.head
        cur_pos = 0
        while cur_node and cur_pos < position:
            prev_node = cur_node
            cur_node = cur_node.next
            cur_pos += 1
        prev_node.next = new_node
        new_node.prev = prev_node
        new_node.next = cur_node
        if cur_node:
            cur_node.prev = new_node

Algorithm to Delete a Node from a Doubly Linked List

1. If the list is empty, there's nothing to delete.
2. If the list has only one node, delete it and update the head to None.
3. If the deletion is at the beginning of the list, point the head to the next node and set the prev of the new head to None.
4. If the deletion is at a specific position, traverse to that node, adjust the next of the previous node and the prev of the next node, and then delete the node.

Here's a Python implementation of the deletion algorithm:

def delete(self, position=None):
    if self.head is None:
        return
    elif self.head.next is None:
        self.head = None
    elif position is None:
        cur_node = self.head
        while cur_node.next:
            prev_node = cur_node
            cur_node = cur_node.next
        prev_node.next = None
        cur_node = None
    elif position == 0:
        self.head = self.head.next
        self.head.prev = None
    else:
        cur_node = self.head
        cur_pos = 0
        while cur_node and cur_pos < position:
            prev_node = cur_node
            cur_node = cur_node.next
            cur_pos += 1
        prev_node.next = cur_node.next
        if cur_node.next:
            cur_node.next.prev = prev_node
        cur_node = None

These algorithms allow us to insert and delete nodes in a doubly linked list at any position with a time complexity of O(n), where n is the length of the list.