Question: Design a doubly linked list class that supports the following operations: insert at head, insert at tail, insert at index, delete at index, get element at index, get length of the linked list, and print the linked list.
Answer:
To design a doubly linked list, we will create the DoublyLinkedList class that contains the following methods:
__init__(): Initializes an empty doubly linked list, setting both the head and tail pointers to None, and the length to 0.
insert_at_head(value): Inserts a new node with the given value at the beginning of the linked list. This method has a time complexity of O(1).
insert_at_tail(value): Inserts a new node with the given value at the end of the linked list. This method has a time complexity of O(1).
insert_at_index(value, index): Inserts a new node with the given value at the specified index in the linked list. This method has a time complexity of O(n) in the worst-case scenario, where n is the number of elements in the linked list.
delete_at_index(index): Deletes the node at the specified index in the linked list. This method has a time complexity of O(n) in the worst-case scenario.
get_element_at_index(index): Returns the value of the node at the specified index in the linked list. This method has a time complexity of O(n) in the worst-case scenario.
get_length(): Returns the number of nodes in the linked list. This method has a time complexity of O(1).
print_list(): Prints the values of all nodes in the linked list.
Implementation of the DoublyLinkedList class:
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def insert_at_head(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
def insert_at_tail(self, value):
new_node = Node(value)
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
def insert_at_index(self, value, index):
if index < 0 or index > self.length:
print('Invalid index')
return
if index == 0:
self.insert_at_head(value)
return
if index == self.length:
self.insert_at_tail(value)
return
new_node = Node(value)
curr_node = self.head
for _ in range(index - 1):
curr_node = curr_node.next
new_node.next = curr_node.next
new_node.prev = curr_node
curr_node.next.prev = new_node
curr_node.next = new_node
self.length += 1
def delete_at_index(self, index):
if index < 0 or index >= self.length:
print('Invalid index')
return
if index == 0:
self.head = self.head.next
if self.head is None:
self.tail = None
else:
self.head.prev = None
elif index == self.length - 1:
self.tail = self.tail.prev
self.tail.next = None
else:
curr_node = self.head
for _ in range(index):
curr_node = curr_node.next
curr_node.prev.next = curr_node.next
curr_node.next.prev = curr_node.prev
self.length -= 1
def get_element_at_index(self, index):
if index < 0 or index >= self.length:
print('Invalid index')
return
curr_node = self.head
for _ in range(index):
curr_node = curr_node.next
return curr_node.value
def get_length(self):
return self.length
def print_list(self):
curr_node = self.head
while curr_node:
print(curr_node.value, end=' ')
curr_node = curr_node.next
print()
Example Usage:
dll = DoublyLinkedList()
dll.insert_at_head(1)
dll.insert_at_head(2)
dll.insert_at_tail(3)
dll.insert_at_index(4, 1)
dll.print_list()
# Output: 2 4 1 3
print(dll.get_element_at_index(2))
# Output: 1
dll.delete_at_index(0)
dll.print_list()
# Output: 4 1 3
print(dll.get_length())
# Output: 3
Explanation: The DoublyLinkedList class maintains two pointers, head and tail, to keep track of the first and last nodes of the linked list, respectively. The length variable stores the number of nodes in the list.
The insert_at_head() method inserts a new node at the beginning of the list. It creates a new_node with the given value and updates the head pointer accordingly.
The insert_at_tail() method inserts a new node at the end of the list. It creates a new_node with the given value and updates the tail pointer accordingly.
The insert_at_index() method inserts a new node at the specified index in the list. It traverses the list to find the node before the specified index, and then updates the pointers to include the new_node.
The delete_at_index() method deletes the node at the specified index in the list. It handles the edge cases where the node to be deleted is at the head or tail position separately.
The get_element_at_index() method returns the value of the node at the specified index in the list. It traverses the list until it reaches the desired index and returns the value of that node.
The get_length() method returns the length of the list by simply returning the length variable.
The print_list() method traverses the list from head to tail and prints the value of each node.
The example usage demonstrates the operations on the doubly linked list, such as inserting nodes at different positions, deleting a node, retrieving the value at a specific index, and printing the list.