Inserting a new node in a linked list involves the below operations.
a) Create a new node (say Node N) to be inserted between Node A and Node B.
b) Point the link (next) of the new node N to Node B.
c) Remove the link from Node A to Node B. Now point the link from Node A to Node N.
Similarly,
Appending a new node to a linked list involves the below operations.
a) Create a new node (say Node N) to be appended to the tail node.
b) Point the link (next) of the new node N to Null.
c) Point the link from the Tail Node to Node N.
Note: After the append operation the new Node N becomes the Tail Node.
Time Complexity for Insert Operation: O(N), as the linked list has be to traversed to find the node after which a new node is to be inserted. Time Complexity for Append Operation: O(N), as the linked list has be to traversed to reach the last node after which a new node is to be inserted.
Space Complexity : O(N). N is the number of nodes in the linked list.
C++ Program to perform insert and append opeations on a Singly linked list.
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int arg_data) : data(arg_data), next(NULL)
{}
};
class SingleLinkedList {
public:
SingleLinkedList()
{}
// Insert a new node into the single linked list after the first found node.
void Insert(Node* head, int after, int data) {
Node* current = head;
// Traverse the link list till the node a node is found after
// which the data is to be insert
while (current != NULL and current->data != after) {
current = current->next;
}
if (current != NULL) {
Node * new_node = new Node(data);
// Save the location of node after current in next_node link
Node * next_node = current->next;
// Point current's link to the new node to be inserted.
current->next = new_node;
// Point new node's link to the next node location previously stored.
new_node->next = next_node;
}
}
// Append a node the the linked list
void Append(Node* head, int data) {
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
Node* new_node = new Node(data);
current->next = new_node;
}
void Display(Node* head) {
Node* current = head;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
}
};
int main() {
Node* head = new Node(2);
head->next = new Node(3);
head->next->next = new Node(5);
head->next->next->next = new Node(7);
head->next->next->next->next = new Node(13);
SingleLinkedList s;
int data = 11;
int after = 7;
cout << "Before inserting " << data << " after node " << after << endl;
s.Display(head);
s.Insert(head, after, data);
cout << "\nAfter inserting " << data << " after node " << after << endl;
s.Display(head);
data = 17;
cout <<"\nAppending " << data << " to the linked list" << endl;
s.Append(head, data);
s.Display(head);
delete head->next->next->next->next->next->next;
delete head->next->next->next->next->next;
delete head->next->next->next->next;
delete head->next->next->next;
delete head->next->next;
delete head->next;
delete head;
return 0;
}
Output of insert and append operations on a single linked list. Implemented in C++11
Before inserting 11 after node 7
2 3 5 7 13
After inserting 11 after node 7
2 3 5 7 11 13
Appending 17 to the linked list
2 3 5 7 11 13 17