# Singly Linked List : Inserting, Appending and Freeing nodes.

Inserting a new node in a linked list involves the below operations.
a) Create a new node ( new_node ) to be inserted between Node A and Node B.
b) Point the link (next) of new_node to Node B.
c) Remove the link that goes from Node A to Node B. Now point the link from Node A to new_node.

Appending a new node to a linked list involves the below operations.
a) Create a new node (new_node) to be appended to the tail node.
b) Point the link of the last node in the singly linked list to new_node.

Freeing the singly linked list or deleting all the allocated nodes involve the below operations.
While the HEAD node of the singly linked list is not NULL.
a) Store the node next to HEAD in a temporary node.
c) Point the HEAD to the temporary node. Time complexity for inserting a node : 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 appending a node : O ( N ), as the linked list has be to traversed to reach the last node after which a new node is to be inserted.
Time complexity for freeing the linked list : O ( N ), as every node of the linked list has be to traversed before it is deleted.

Space complexity : O ( N ). N is the number of nodes in the linked list.

C++ program for inserting, appending and freeing the nodes of a singly linked list.

``````#include<iostream>

using namespace std;

class Node {

public:
int data;
Node* next;
Node (int arg_data) : data (arg_data), next (nullptr)
{}
};

public:

{}

// Insert a new node into the single linked list after the first found node.
void Insert (Node* head, int data, int after) {

// Traverse the link list till the node a node is found after
// which the data is to be insert
while (current->data != after) {
current = current->next;
}

if (current != nullptr) {
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 to the singly linked list
void Append (Node* head, int data) {

while (current->next != nullptr) {
current = current->next;
}
Node* new_node = new Node(data);
current->next = new_node;
}

while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
}

}
}
};

int main() {

Node *node_3 = new Node(3);
Node *node_5 = new Node(5);
Node *node_7 = new Node(7);
Node *node_13 = new Node(13);

node_3->next = node_5;
node_5->next = node_7;
node_7->next = node_13;

int data, after, opt = 0;

while (opt != 3) {
cout << "\n\nOptions" << endl;
cout << "1. Insert" << endl;
cout << "2. Append" << endl;
cout << "3. Exit" << endl;
cout << "Enter Option : ";
cin >> opt;
switch (opt) {

case 1:
cout << "\nEnter new node (data) : ";
cin >> data;
cout << "After node : ";
cin >> after;
break;

case 2:
cout << "\nEnter new node (data) : ";
cin >> data;
break;

case 3:
cout << "Freeing the linked list." << endl;
break;
}
}
return 0;
}
``````

Output

``````Options
1. Insert
2. Append
3. Exit
Enter Option : 1
Linked list 2 3 5 7 13
Enter new node (data) : 8
After node : 7
2 3 5 7 8 13

Options
1. Insert
2. Append
3. Exit
Enter Option : 1
Linked list 2 3 5 7 8 13
Enter new node (data) : 20
After node : 8
2 3 5 7 8 20 13

Options
1. Insert
2. Append
3. Exit
Enter Option : 2
Linked list 2 3 5 7 8 20 13
Enter new node (data) : 40
2 3 5 7 8 20 13 40

Options
1. Insert
2. Append
3. Exit
Enter Option : 2
Linked list 2 3 5 7 8 20 13 40
Enter new node (data) : 100
2 3 5 7 8 20 13 40 100

Options
1. Insert
2. Append
3. Exit
Enter Option : 3