Inserting in a Linked List

Given a Singly linked list. Write functions to insert at different positions in the list:

• At start of the linked list.
• At end of the linked list.
• After k nodes from the start of list.
• After k nodes from the end of linked list.
• Insert in a sorted linked list.

Solution:

We have already written a post to insert in a sorted linked list. We will use the same definition of node as given in that post.

    struct Node
    {
        int data;
        Node* link;
        // Constructor
        Node(int n):data(n), link(NULL) {}
    };

The declaration of LinkedList class is also similar:

class LinkedList
{
public:
    LinkedList():head(NULL){}
    void printList();
    // Insert as the first Node
    void insertAtStart(int data);
    // Insert as Last Node
    void insertElementAtEnd(int data);
    // Insert in a sorted list
    void insertSorted(int data);
    // Insert after k nodes from the start of list
    void insertFromStart(int data, int k);
    // Insert after k nodes from end of list
    void insertFromEnd(int data, int k);
private:
    Node* head;
};

The functions in above class are, in a way, self-contradicting. Because, if we are inserting in a sorted linked list then it does not make sense to provide functions to insert at any other position (which may distort the sorted-ness of the list). So, it is more from the demonstrating purpose only. Let's look at each method one-by-one

1. Inserting at the start of the list

This is very easy. we just need to update the head pointer. Let the given linked list be

And we want to insert 9 at the start of the list. Then the steps are as follows.

Step-1: Create a temp node with data 9 and link null

Step-2: make link of above node point to head of list:

Step-3: Make head point to temp (hence temp node will be the new head of the linked list)

The special case, when the list is empty will also he taken care of in the above algorithm.

Code:

void LinkedList::insertAtStart(int data)
{
    Node* temp = new Node(data);
    temp->link = head;
    head = temp;
}

Time Complexity: O(1)

This is how elements are pushed when Stack is implemented using linked list.

2. Inserting at the end of the list.

In this case we need to take care of the case when the list is empty. If list is empty then head pointer will be updated else head will not be updated and only the link of last node of the list will be updated.

Code:

void LinkedList::insertElementAtEnd(int data)
{
    if(head == NULL)
    {
        head = new Node(data);
    }
    else
    {
        Node* temp = head;
        while(temp->link != NULL)
        {
            temp = temp->link;
        }
        temp->link = new Node(data);
    }
}

Time Complexity: O(n)

3. Inserting after k nodes from the start of the list

It assumes that the list has at least k nodes. If the list have less than k nodes, then the insertion will fail and exception will be thrown.

The Algorithm is simple. Move forward by k positions and then insert the node in between (or at end). The special case that need to be handled is if (k==0) which means inserting at the head (start) of list, and hence, head pointer must be updated. 

Code:

void LinkedList::insertFromStart(int data, int k)
{
    // -ve not accepted
    if(k<0){ return; }
    // case of inserting at the start of list
    if(k==0)
    {
        insertAtStart(data);
        return;
    }
    // Move forward so that temp point to
    // the k'th element from front
    Node* temp = head;
    for(int i=0; i<k-1; i++)
    {
        // throw exception if there are < k elements
        if(temp == NULL)
            throw ;
        temp = temp->link;
    }
    if(temp == NULL)
    {
        throw;
    }
    else
    {
        // Actual insertion
        Node* newNode = new Node(data);
        newNode->link = temp->link;
        temp->link = newNode;
    }
}

Time Complexity: O(n)

4. Inserting after k nodes from end of the list.

This is similar to the previous one, the only tricky part is how to reach at the k'th node from the end of list. It is discussed in detail in this post.

Once we have a pointer to the k'th node from end of the list, the logic is same as above. i.e

    Node* newNode = new Node(data);
    newNode->link = temp->link;
    temp->link = newNode;

5. Inserting in a Sorted linked list

This is discussed in details in this post.

Note: If it is a C language code, then we have to pass &head (address of head pointer) in all the cases, because there is a chance that the function may need to update the head pointer itself.