Design a Doubly Linked List [Solution]
Below is the Python implementation of the
DoublyLinkedList
class with the specified operations:
class ListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_at_head(self, val):
new_node = ListNode(val)
if not self.head:
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_tail(self, val):
new_node = ListNode(val)
if not self.head:
self.head = self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def insert_after_node(self, node, val):
if not node:
return
new_node = ListNode(val)
new_node.next = node.next
new_node.prev = node
if node.next:
node.next.prev = new_node
node.next = new_node
def delete_at_head(self):
if not self.head:
return
if self.head == self.tail:
self.head = self.tail = None
else:
self.head = self.head.next
self.head.prev = None
def delete_at_tail(self):
if not self.tail:
return
if self.head == self.tail:
self.head = self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
def delete_node(self, node):
if not node:
return
if node == self.head:
self.delete_at_head()
elif node == self.tail:
self.delete_at_tail()
else:
node.prev.next = node.next
node.next.prev = node.prev
def display(self):
current = self.head
while current:
print(current.val, end=" <-> ")
current = current.next
print("None")
# Example usage:
dll = DoublyLinkedList()
dll.insert_at_head(1)
dll.insert_at_tail(2)
dll.insert_at_tail(3)
dll.insert_after_node(dll.head.next, 4)
dll.display() # Output: 1 <-> 2 <-> 4 <-> 3 <-> None
dll.delete_at_head()
dll.display() # Output: 2 <-> 4 <-> 3 <-> None
dll.delete_at_tail()
dll.display() # Output: 2 <-> 4 <-> None
dll.delete_node(dll.head.next)
dll.display() # Output: 2 <-> None
This implementation demonstrates the creation of a doubly linked list with the specified operations and displays the elements of the doubly linked list after each operation.