Last Updated on May 12, 2023 by Prepbytes
A singly linked list is a data structure that consists of a series of nodes, each of which contains a value and a pointer to the next node in the list. One common operation on a singly linked list is inserting a new node at a specific position in the list, such as the nth node.
What is the Singly Linked List?
A singly linked list is a type of data structure where each node has a value and a reference to the node after it in the list. The first node in the list is called the head, and the last node is called the tail. The tail node’s next reference is typically null, indicating the end of the list.
Singly-linked lists are commonly used in computer programming as a way to efficiently store and manipulate collections of data. They are especially useful when the size of the collection is not known beforehand, or when we need to frequently insert or remove elements from the list.
Insertion at the Nth Node of the Singly Linked List
To insert a new node at the nth position in a singly linked list, we first need to traverse the list to find the n-1th node. Once we have found this node, we can insert the new node by updating its next pointer to point to the current nth node and updating the n-1th node’s next pointer to point to the new node.
Algorithm
- Step 1: if the position is not 0 and the Head is null. Then, leave it.
- Step 2: If both Head and position is null, then. After that, remove it and add a new node to the head.
- Step 3: If the position is 0 and the Head is not null. The Head reference was then changed to the new Node. Finally, quit it and set a new Node to the Head.
- Step 4: If not, keep trying until you reach the Nth place or stop.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* nextNode;
};
struct LinkedList {
struct Node* head;
};
void insert(struct LinkedList* ls, int data) {
// create a new Node and store a data.
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->nextNode = NULL;
// check the head is null or not.
// if head is null, assign the Node and exit.
if (ls->head == NULL) {
ls->head = node;
return;
}
// assign a head into the temp Node and loop it until find the null reference.
struct Node* tempNode = ls->head;
while (tempNode->nextNode != NULL) {
tempNode = tempNode->nextNode;
}
// assign new node.
tempNode->nextNode = node;
}
void insertNth(struct LinkedList* ls, int data, int position) {
// create new node.
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->nextNode = NULL;
if (ls->head == NULL) {
// if head is null and position is zero then exit.
if (position != 0) {
return;
} else { // node set to the head.
ls->head = node;
}
}
if (ls->head != NULL && position == 0) {
node->nextNode = ls->head;
ls->head = node;
return;
}
struct Node* current = ls->head;
struct Node* previous = NULL;
int i = 0;
while (i < position) {
previous = current;
current = current->nextNode;
if (current == NULL) {
break;
}
i++;
}
node->nextNode = current;
previous->nextNode = node;
}
void print(struct LinkedList* ls) {
if (ls->head == NULL) {
return;
}
// print all nodes
struct Node* tempNode = ls->head;
while (tempNode != NULL) {
printf("%d->", tempNode->data);
tempNode = tempNode->nextNode;
}
printf("NULL\n");
}
int main() {
struct LinkedList ls;
ls.head = NULL;
insert(&ls, 10);
insert(&ls, 20);
insert(&ls, 30);
print(&ls);
insertNth(&ls, 25, 2);
print(&ls);
return 0;
}
Output
10->20->30->NULL
10->20->25->30->NULLConclusion
Inserting a new node at the nth position of a linked list can be a useful operation in many applications. It involves traversing the list to find the n-1th node, and then inserting the new node by updating its next pointer to point to the current nth node, and updating the n-1th node’s next pointer to point to the new node.
When implementing this operation, it is important to handle edge cases, such as inserting at the beginning of the list or when the list is empty, as well as checking for out-of-range indices. In addition, it is important to properly allocate memory for the new node and to update the next pointers of the affected nodes to maintain the integrity of the linked list.
Frequently Asked Questions
Q1. What is a linked list?
Ans. Linked list is a data structure consisting of a sequence of nodes, where each node stores a value and a reference to the next node in the list.
Q2. How do I insert a new node at the nth position of a linked list?
Ans. To insert a new node at the nth position of a linked list, you need to first traverse the list to find the n-1th node, and then insert the new node by updating its next pointer to point to the current nth node and updating the n-1th node’s next pointer to point to the new node.
Q3. What is the time complexity of inserting a new node at the nth position of a linked list?
Ans. Inserting a new node at the nth position of a linked list requires traversing the list to find the n-1th node, which takes O(n) time in the worst case. Once the n-1th node is found, the actual insertion takes O(1) time. Therefore, the overall time complexity of inserting a new node at the nth position of a linked list is O(n).
Q4. What is the space complexity of inserting a new node at the nth position of a linked list?
Ans. Inserting a new node at the nth position of a linked list requires creating a new node, which takes O(1) space. Therefore, the space complexity of inserting a new node at the nth position of a linked list is O(1).
Q5. What are some common applications of linked lists?
Ans. Linked lists can be used in many applications where dynamic insertion and deletion of elements is required, such as implementing stacks, queues, and hash tables. They can also be used in situations where the size of the collection is not known beforehand or where efficient random access is not required.