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.
      b) Delete the HEAD node.
      c) Point the HEAD to the temporary node.


Single_Link_List_Insert_Append

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)
    {}
};

class SingleLinkedList {

    public:

    SingleLinkedList()
    {}

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

        Node* current = head;

        // 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) {

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

    void Display (Node* head) {

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

    // Free the linked list
    void Free (Node *head) {
         while (head != nullptr) {
             Node * temp = head->next;
             head->next = nullptr;
             delete head;
             head = temp;
         }
    }
};

int main() {

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

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

    SingleLinkedList s;
    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 << "Linked list ";
                s.Display(head);
                cout << "\nEnter new node (data) : ";
                cin >> data;
                cout << "After node : ";
                cin >> after;
                s.Insert(head, data, after);
                s.Display(head);
                break;

            case 2:
                cout << "Linked list ";
                s.Display(head);
                cout << "\nEnter new node (data) : ";
                cin >> data;
                s.Append(head, data);
                s.Display(head);
                break;

            case 3:
                cout << "Freeing the linked list." << endl;
                s.Free(head);
                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
Freeing the linked list.


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.