Inserting a node at the end of a doubly linked list involves creating a new node and updating the next reference of the last node to point to this new node, as well as updating the previous reference of the new node to point to the last node. This operation requires traversing the list to find the last node.
Consider a doubly linked list with the following structure before insertion:
Head <-> 1 <-> 2 <-> 3 <-> 4 <-> None
We want to insert a new node with the value 5 at the end. Follow these steps:
After performing these steps, the linked list will have the following structure:
Head <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> None
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 self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def traverse(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
# Example usage:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.append(4)
print("Doubly linked list before insertion at end:")
dll.traverse() # Output: 1 <-> 2 <-> 3 <-> 4 <-> None
dll.insert_at_end(5)
print("Doubly linked list after insertion at end:")
dll.traverse() # Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> None
This Python program defines a doubly linked list with methods for appending nodes, inserting a node at the end, and traversing the list. The insert_at_end method creates a new node, traverses to the last node, updates the last node's next reference to point to the new node, and updates the new node's previous reference to point to the last node.