How To Insert At End of a Linked List at Constant Time – O(1)

In this tutorial i am going to show you how i insert at the end of a linked list in constant time – O(1) – time complexity as against the usual O(n).

They trick to insert at the end of a linked list each time at constant time – O(1) – is to avoid traversing the list to find the end of the list before insert by having a pointer point to the end of the linked list at all time – which i will call Tail in this post.

So the logic is very simple: create two global pointers called Head and Tail, then create a new node and assign value to the data part of the node and assign NULL to the link part. Now check if the Head pointer is NULL, if NULL, then list is empty; so make both pointer – Head and Tail – point to the newnode; now we have our first node in the linked list; otherwise if the head pointer is not NULL – meaning we have at least one node in our linked list, then point the Tail pointer link part to the newnode and then make the Tail pointer now point on the newnode – thereby indicating that the newnode is the last node in the list. With this Tail pointer always pointing to the last node, you can achieve inserting a new node at the end of a linked list at constant time O(1).

Code Implementation in c

#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *next;
};

void Print_List(struct node **head){
    struct node *temp = *head;
    while(temp != NULL){
        printf("%d ", temp->data);
        temp = temp->next;
    }
    free(temp);
    return 0;
}

struct node *Head;
struct node *Tail;

insert_at_end_of_linked_list_at_constant_time(int val){
    struct node *newnode = malloc(sizeof(struct node));
    newnode->data = val;
    newnode->next = NULL;
    if(Head==NULL){
        Head = Tail = newnode;
    }else{
        Tail->next = newnode;
        Tail = newnode;
    }
}

int main(){
    Head = NULL;
    insert_at_end_of_linked_list_at_constant_time(10);
    insert_at_end_of_linked_list_at_constant_time(20);
    insert_at_end_of_linked_list_at_constant_time(30);
    insert_at_end_of_linked_list_at_constant_time(40);
    insert_at_end_of_linked_list_at_constant_time(50);
    Print_List(&Head);
}

Output

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

You May Also Like