JIYIK CN >

In this article, we will learn how to insert a node into a linked list. We can see that 4 different cases occur.

1. We want to insert a node before the head of the linked list. This operation is similar to the push operation in a stack.
2. We want to insert a node at the end of the linked list (that is, next to the tail node).
3. We want to insert a node at the ith position of the linked list.
4. We have a reference to the node, and then we want to insert the new node.

Linked list insertion algorithm

Let headbe a pointer to the first node of the linked list, and let xbe the data to be inserted into the linked list.

push()Insert a node at the beginning of a linked list

• xCreate a new node with data temp.
• Set temp->nextto to insert headbefore . headtemp
• Sets tempto the beginning of the linked list.

append()Insert a node at the end of the linked list

• xCreate a new node with data temp.
• Initializes pointer headto tail.
• If the linked list is empty, tempsets to the linked list's headand then returns .
• Otherwise, iterate to the end of the linked list, making tail->next!= NULLso that you reach the last element
• Set tail->nextto temp.

Insert a node at position insertNpos()in the linked listi-th

• If position pos<= 0, then return; otherwise return 0.
• If pos== 0and headis empty, create a xnew node with data and set it to head.
• If pos== 1, then call push().
• Additionally, xcreate a new node with the data temp.
• Initializes pointer headto curr.
• When pos--, do the following.

  • If pos== 1,

    • If currnotNULL
      • Set temp->nextto curr->nextto currinsert after temp.
      • Set curr->nextto tempto currconnect to temp.
    • return;

  • Otherwise currset to curr->next.

Inserts a node next to the given node's reference −insertAfter()

• If prev== NULL, then return;
• xCreate a new node with data curr.
• curr->nextPoint to prev->nextto add a new node after prev.
• prev->nextPoint to currto complete the insertion.

Linked list insertion diagram

Suppose we have a node tempwith data value equal to 5, and we want to insert it into the linked list. Let's consider all 4the cases and illustrate how the above algorithm works.

To insert a node at the beginning of a linked list −push()

• tempSet the pointer of to head.
• headPoint to temp.

append()Insert a node at the end of the linked list

• Point currto head, the data is 2.
• Set currto curr->next, and move it to 3the node with data .
• Set currto curr->next, and move it to 4the node with data .
• Exit the while loop and curr->nextsettemp

i-thInsert a node at position in the linked list -insertNpos()

We insert the node at position 3.

• Set currto point to headand data to be 1, pos= pos-1= 2.
• Set currto curr->next, and move it to the node whose data is 3, pos= pos -1= 1.
• Set temp->nextto curr->nextso that currtemp is inserted after .
• Set curr->nextto tempto complete the insertion of between currand . curr->nexttemp

insertAfter()Inserts a node next to the given node 's reference

• Set temp->nextto to insert prev->nextbetween prevand . prev->nexttemp
• Set prev->nextto tempto complete the insert.

Linked list insertion implementation

#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node* next;
        Node(int x) {
            this->data = x;
            this->next = NULL;
        }
};

void push(Node** head, int x)
{
    Node* temp = new Node(x);
    temp->next = (*head);
    (*head) = temp;
}

void insertAfter(Node* prev, int x)
{
    if (prev == NULL) {
        return;
    }
    Node* curr = new Node(x);
    curr->next = prev->next;
    prev->next = curr;
}

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}
void insertNpos(Node**head, int x, int pos) {
    if (pos <= 0) {
        return;
    }
    if (!head && pos == 1) {
        *head = new Node(x);
    }
    else if (pos == 1) {
        push(head, x);
    }
    Node* temp = new Node(x);
    Node*curr = *head;
    while (pos--) {
        if (pos == 1) {
            if (curr) {
                temp->next = curr->next;
                curr->next = temp;
            }
            return;
        }
        curr = curr->next;
    }
}
void append(Node** head, int x)
{
    Node* temp = new Node(x);
    Node *tail = *head;
    if (*head == NULL)
    {
        *head = temp;
        return;
    }
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = temp;
    return;
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    printList(head); cout << "\n";
    push(&head, 3);
    push(&head, 4);
    printList(head); cout << "\n";
    append(&head, 5);
    printList(head); cout << "\n";
    insertAfter(head->next->next, 6);
    printList(head); cout << "\n";
    insertNpos(&head, 24, 2);
    printList(head);
    return 0;
}

Complexity of linked list insertion algorithm

Time Complexity

• Average situation

To insert a node into the position in the linked list 第 i 个, we have to visit inodes. So, the time complexity is about O(i). And we have nodes in the linked list n, so the time complexity in the average case is O(n/2)or O(n). The time complexity is about O(n).

• Best Case

The best case scenario is when we want to insert a node at the beginning of the linked list or when there is a reference to the node before the insertion site. The time complexity for the best case scenario is O(1).

• Worst case scenario

The worst case time complexity is O(n). This is the same as the average case time complexity.

Space complexity

The space complexity of this insertion algorithm is O(1), since currno additional space is required except for the pointer.