Can you explain doubly linked lists in Python with examples?

Can you explain doubly linked lists in Python with examples?

Sure! A doubly linked list is a data structure where each node contains a reference to both the next and previous node. Here's a simple example:

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=' <-> ')
            current = current.next
        print('None')

# Example usage:
list = DoublyLinkedList()
list.append(1)
list.append(2)
list.append(3)
list.display()  # Output: 1 <-> 2 <-> 3 <-> None

What are the advantages of using a doubly linked list over a singly linked list?

Doubly linked lists allow traversal in both directions (forward and backward), making operations like deletion and insertion more efficient. You can easily access the previous node, which is not possible in singly linked lists.

Can you show me how to delete a node from a doubly linked list?

Certainly! Here's how you can delete a node from a doubly linked list:

def delete_node(self, key):
    current = self.head
    while current:
        if current.data == key:
            if current.prev:
                current.prev.next = current.next
            if current.next:
                current.next.prev = current.prev
            if current == self.head:
                self.head = current.next
            return
        current = current.next

What is the time complexity for insertion and deletion in a doubly linked list?

The time complexity for both insertion and deletion in a doubly linked list is O(1) if you have a reference to the node to be inserted or deleted. If you need to search for the node first, it would be O(n).