Insert a Node at the End of a Singly Linked List

Inserting a Node at the End

Inserting a node at the end of a singly linked list involves creating a new node and updating the next reference of the last node to point to this new node. This operation requires traversing the list to find the last node.

---

Step-by-Step Process

Consider a singly 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 reference to None).
3. Update the Last Node's Next Reference: Set the next reference of the last node to point to the new node.

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

class SinglyLinkedList:
    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

    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

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
print("Linked list before insertion:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> None
linked_list.insert_at_end(5)
print("Linked list after insertion at the end:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None

This Python program defines a singly 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, and updates the last node's next reference to the new node.