Insert a Node at the End of a Doubly Linked List

Inserting a Node at the End

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.

---

Step-by-Step Process

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:

1. Create a New Node: Create a new node with the desired value (5).
2. Traverse to the Last Node: Start at the head and follow the next references until you reach the last node (node with value 4).
3. Update the Last Node's Next Reference: Set the next reference of the last node to point to the new node.
4. Set the Previous Reference of the New Node: Set the previous reference of the new node to point to the last node.
5. Set the Next Reference of the New Node: Set the next reference of the new node to None, since it is now the last node in the list.

After performing these steps, the linked list will have the following structure:

Head <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> None

---

Python Program to Insert a Node at the End

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.