Understanding insertion at end

Inserting at the end of a list is a common operation used to extend the list. Unlike insertion at the beginning, this operation adds a new node at the end of the list. To add a new node at the end of a singly linked list, we first need to locate the tail node of the linked list. Then, we can create a new node and update the next pointer of the tail node to point to the newly created node. Since we need to traverse the entire list to insert the new node, this operation is not as efficient as insertion at the beginning. When inserting at the end of a singly linked list, there are two cases to consider.

1. The list is empty

In this scenario, if the linked list is empty, the head will be null. We need to initialize the head node of the linked list and ensure that the next pointer of this newly created head node is null, as this newly created node will also be the last node of the list.

Algorithm

• Step 1: Create a new node with the given data.
• Step 2: Set the new node's `next` pointer to `null` since it's the only node.
• Step 3: Return the new node, as this node is also the head node.

2. The list is not empty

In this scenario, once the new node is created, we must move through the list from the beginning until we reach the last node. Also, we need to ensure that the next pointer of the newly created node is set to null. Finally, we update the next pointer of the last node to point to the newly created node.

Algorithm

• Step 1: Create a new node with the given data.
• Step 2: Traverse the list, keeping track of the `current` node until reaching the last node.
• Step 3: Set the new node's `next` pointer to `null` since it will be the new last node.
• Step 4: Set the last node's `next` pointer to hold the reference of the new node.
• Step 5: Return the original head node.

Implementation

When implementing the logic for insert at the end operation, we consider both possible cases and write the code for each in conditional blocks. 

Complexity Analysis

The time complexity of the above function depends on the number of nodes in the linked list. Since we must traverse the entire list to reach the end, its time complexity is O(N), where N is the number of nodes in the list.

The function's space complexity is O(1) because it only creates a single new node and does not use any additional data structures.

Best Case

• Space Complexity - O(1)
• Time Complexity - O(1)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(N)