How to Insert a Node in Singly Linked List C++
- Implement a Function to Insert a Node at The End of a Linked List
- Implement a Function to Insert a Node After a Given Node in a Linked List
- Implement a Function to Insert a Node at the Beginning of a Linked List
This article explains the method of how to insert a new node in a singly linked list in C++.
Implement a Function to Insert a Node at The End of a Linked List
Linked lists are linear data structures that consist of nodes pointing to each other, sequentially. In this article, we’re focusing more on a singly linked list structure and implement multiple insertion operations correspondingly.
In a singly linked list, we have a data object(s) and a pointer to the next node in the list. We defined a node structure named ListNode and two helper functions (freeNodes and printNodes) to demonstrate the list insertion operations better. Note that the insertion operation time complexity varies based on the position we are inserting a node to. For example, the insertion at the end of the list takes linear time if the end of the list is unknown.
On the other hand, inserting a new node at the beginning always takes constant time. The following code demonstrates the insertNodeEnd function, which can be treated as the core function to construct a list. It takes the head of the list as the first parameter and the string data that needs to be stored at a new node. The function can create the first element in the list and append new elements at the end of it. The function allocates new nodes on free store memory. Thus, the freeNodes function is needed to free all the memory before the program exit.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeEnd(head, "Utopic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
Implement a Function to Insert a Node After a Given Node in a Linked List
Inserting a node in the middle of the list generally takes constant time plus the time complexity of the search algorithm used to find the given position. Although, we assume the search function is implemented separately and construct the insertNodeAfter function so that the position of the target node needs to be supplied as the first argument.
Since the insertNodeEnd function returns the pointer to a newly appended node, we utilize its return value to demonstrate the operation of insertNodeAfter. Keep in mind that you’d need a separate search function for arbitrary position insertions and even might need an external data structure to implement a faster search operation on a linked list.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
if (!prev) return nullptr;
auto new_node = new ListNode;
new_node->next = nullptr;
new_node->data = std::move(data);
prev->next = new_node;
return new_node;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
auto iter = insertNodeEnd(head, "Utopic");
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeAfter(iter, "Xenial");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
node 5 - data: Xenial
Implement a Function to Insert a Node at the Beginning of a Linked List
Another useful insertion operation for the singly linked list is to append a new node at the beginning. This function has the best running time O(1) since the head of the list is always stored to access the list itself. The insertNodeFront function takes the reference to a root pointer and the string object that needs to be stored at the node. The process is implemented so that you can use it to initialize a new linked list as well as the front insertion.
Alternatively, you may rewrite the function to allocate a new node when the root argument is not nullptr. Otherwise, return nullptr to indicated that the function failed. The interface of these functions depends on the programmers’ needs and the structure of the ListNode.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
auto new_node = new ListNode;
if (root) {
new_node->next = root;
new_node->data = std::move(data);
root = new_node;
return root;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeFront(head, "Bionic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Bionic
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook