Algotree > Algorithms > Linked List > Inserting in and appending to a singly linked list

Inserting in and appending to a singly linked list

Singly Linked List : Insert and Append Operations

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.

Single_Link_List_Insert_Append

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