Singly Linked List: Structure and Basic Operations

Introduction and Basics of Singly Linked List

A Singly Linked List (SLL) is a linear data structure where elements are stored inside individual nodes. Each node contains two parts:

• Data – Stores the actual value.

• Next Pointer – Stores the address of the next node.

Unlike arrays, linked list nodes are not stored in contiguous memory locations. Instead, every node points to the next node, forming a chain-like structure.

Example:

10 → 20 → 30 → 40 → NULL

Here, 10 is the head node and NULL indicates the end of the linked list.

1. Traversal in a Singly Linked List

Given the head of a singly linked list, traverse the list from the first node to the last node. Visit each node exactly once and print its value. Stop when you reach NULL.

Algorithm

• Check whether the linked list is empty. If the head is NULL, there are no nodes available to traverse.

• Create a temporary pointer and initialize it with the head node because traversal always begins from the first node.

• Visit the current node and process its value according to the problem requirement.

• Move the temporary pointer to the next node so that traversal can continue further in the list.

• Repeat the visiting and moving process until the temporary pointer becomes NULL.

• Once NULL is reached, it indicates that every node has been visited exactly once and traversal is complete.

Time Complexity: O(N) because every node in the linked list is visited exactly one time.

Space Complexity: O(1) because only a single temporary pointer is used regardless of the list size.

2. Insert at Head

Given the head of a singly linked list and a value X, insert a new node containing X at the beginning of the linked list. Return the head of the updated linked list after the insertion.

Algorithm

• Create a new node containing the value X because a separate node is required to store the new element.

• Check whether the linked list is empty. If the head is NULL, the new node automatically becomes the head.

• Connect the new node to the current head node by updating its next pointer.

• Update the head pointer so that it points to the newly created node.

• Ensure that the remaining nodes stay connected through the original head node.

• Return the updated head pointer as the starting point of the modified linked list.

Time Complexity: O(1) because insertion happens using a constant number of pointer updates.

Space Complexity: O(1) auxiliary space because no extra data structure is used apart from the new node being inserted.

3. Insert at Tail

Given the head of a singly linked list and a value X, insert a new node containing X at the end of the linked list. Return the head of the updated linked list after the insertion.

Algorithm

• Create a new node containing the value X because this node will be attached at the end of the linked list.

• Check whether the list is empty. If the head is NULL, return the newly created node as the head.

• Start a temporary pointer from the head node to locate the current tail node.

• Continue moving forward until a node whose next pointer is NULL is reached.

• Connect the last node to the newly created node by updating its next pointer.

• Return the original head pointer because the starting node of the linked list remains unchanged.

Time Complexity: O(N) because we may need to traverse the entire linked list to reach the last node.

Space Complexity: O(1) because only a temporary traversal pointer is used.

4. Insert at Kth Position

Given the head of a singly linked list, a position K, and a value X, insert a new node containing X at the Kth position in the linked list. Return the head of the updated linked list after the insertion.

Algorithm

• Check whether K equals 1 because insertion at the first position is simply a head insertion operation.

• Create a new node containing the value X that needs to be inserted into the linked list.

• Traverse the linked list until the node just before the Kth position is reached.

• Store the current connection of that node because it must be preserved after insertion.

• Connect the new node to the original Kth node so that the remaining list remains attached.

• Update the previous node's next pointer to the new node and return the head pointer.

Time Complexity: O(N) because locating the insertion position may require traversing multiple nodes.

Space Complexity: O(1) because only a few pointers are used during insertion.

5. Insert Before Value X

Given the head of a singly linked list, a target value X, and a new value, insert a new node immediately before the first occurrence of X in the linked list. Return the head of the updated linked list after the insertion.

Algorithm

• Check whether the linked list is empty because insertion before a value is not possible when no nodes exist.

• If the target value is present at the head node, perform a head insertion and return the updated list.

• Traverse the linked list while checking the value stored in the next node.

• Stop traversal when the next node contains the target value because insertion must happen before it.

• Create a new node and connect it to the target node so that the remaining list remains unchanged.

• Update the previous node's next pointer to the new node and return the head pointer.

Time Complexity: O(N) because the target value may be present near the end of the linked list.

Space Complexity: O(1) because only traversal pointers are used.

6. Delete Head Node

Given the head of a singly linked list, delete the first node of the linked list and return the head of the modified list. If the list is empty, return NULL.

Algorithm

• Check whether the linked list is empty because no deletion can be performed on an empty list.

• Store the current head node temporarily because it will be removed from memory.

• Move the head pointer to the second node of the linked list.

• Disconnect the old head node from the remaining list structure.

• Delete the stored node to free its memory safely.

• Return the updated head pointer representing the modified linked list.

Time Complexity: O(1) because deletion occurs directly at the beginning without traversal.

Space Complexity: O(1) because only one temporary pointer is required.

7. Delete Tail Node

Given the head of a singly linked list, delete the last node of the linked list and return the head of the modified list. If the list is empty, return NULL.

Algorithm

• Check whether the linked list is empty because there is no node available for deletion.

• If only one node exists, delete it and return NULL because the list becomes empty.

• Start traversing from the head node to locate the second-last node of the linked list.

• Continue moving forward until the node whose next node is the tail is reached.

• Store the tail node temporarily because it will be removed.

• Update the second-last node's next pointer to NULL, delete the tail node, and return the head.

Time Complexity: O(N) because we must reach the second-last node before removing the tail.

Space Complexity: O(1) because only temporary pointers are used.

8. Delete Kth Node

Given the head of a singly linked list and a position K, delete the node present at the Kth position in the linked list. Return the head of the modified linked list after the deletion.

Algorithm

• Check whether the linked list is empty because deletion cannot be performed on an empty structure.

• If K equals 1, perform a head deletion since the first node must be removed.

• Traverse the linked list until the node immediately before the Kth position is reached.

• Store the Kth node temporarily because its connection needs to be removed safely.

• Connect the previous node directly to the node after the Kth node to preserve the remaining list.

• Delete the stored node and return the head pointer of the modified linked list.

Time Complexity: O(N) because reaching the Kth position may require traversing multiple nodes.

Space Complexity: O(1) because only a constant number of pointers are maintained.

9. Delete Node with Value X

Given the head of a singly linked list and a value X, delete the first node whose value is equal to X. Return the head of the modified linked list after the deletion.

Algorithm

• Check whether the linked list is empty because no deletion can be performed when no nodes exist.

• If the head node itself contains value X, perform a head deletion and return the updated list.

• Traverse the linked list while checking the value stored in the next node.

• Stop traversal when the next node contains the target value because that node must be removed.

• Store the target node temporarily and connect the previous node directly to the node after it.

• Delete the stored node and return the head pointer of the modified linked list.

Time Complexity: O(N) because the target value may appear at the last node of the linked list.

Space Complexity: O(1) because only traversal pointers are used during deletion.