Insert node at end of linked list c program

Write a program which is create and add linked list node at the end (tail, last) position in c language.

Suppose we are inserted the following (10, 20, 30 ,40 ,50) node in a sequence.

insert node at end of linked list

Initial linked list are no element, In this situation create a dynamic linked list node and append this node at the front position. And assign this node address to head of linked list.

When linked list are not empty, In this situation using of head pointer reference finding the last node of linked list. We can use while loop of this situation to find last node. This process are tack to O(n) time. And add new node to last position.

/*
    C program for
    Insert linked list element at end position set A
*/
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
    int data;
    struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
    struct LinkNode *head;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
    // Create memory of head and tail Nodes
    struct SingleLL *sll = (struct SingleLL *)
    malloc(sizeof(struct SingleLL));
    if (sll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        sll->head = NULL;
    }
    return sll;
}
// Handles the request of adding new node at end of linked list
void addNode(struct SingleLL *sll, int data)
{
    // Create dynamic node
    struct LinkNode *node = (struct LinkNode *)
    malloc(sizeof(struct LinkNode));
    if (node == NULL)
    {
        // Handle memory overflow 
        printf("Memory overflow to Create LinkNode\n");
        return;
    }
    else
    {
        // Set initial node value
        node->data = data;
        node->next = NULL;
    }
    if (sll->head == NULL)
    {
        // First node in linked list
        sll->head = node;
    }
    else
    {
        struct LinkNode *temp = sll->head;
        // Find the last node
        while (temp != NULL && temp->next != NULL)
        {
            temp = temp->next;
        }
        // Add node at last position
        temp->next = node;
    }
}
// Display linked list element
void display(struct LinkNode *node)
{
    if (node == NULL)
    {
        return;
    }
    struct LinkNode *temp = node;
    // iterating linked list elements
    while (temp != NULL)
    {
        printf(" %d →", temp->data);
        // Visit to next node
        temp = temp->next;
    }
    printf(" NULL\n");
}
int main(int argc, char
    const *argv[])
{
    struct SingleLL *sll = newLinkedList();
    // Linked list
    // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
    addNode(sll, 1);
    addNode(sll, 2);
    addNode(sll, 3);
    addNode(sll, 4);
    addNode(sll, 5);
    addNode(sll, 6);
    addNode(sll, 7);
    addNode(sll, 8);
    printf(" Linked List \n");
    display(sll->head);
    return 0;
}
 Linked List
 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL

Time complexity of above program is O(n). We can optimize above algorithm using one extra pointer. Which is hold the reference of last node. Below are implementation of this logic.

/*
    C program for
    Insert linked list element at end position set B
*/
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
    int data;
    struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
    struct LinkNode *head;
    struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
    // Create memory of head and tail Nodes
    struct SingleLL *sll = (struct SingleLL *)
    malloc(sizeof(struct SingleLL));
    if (sll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        sll->head = NULL;
        sll->tail = NULL;
    }
    return sll;
}
// Handles the request of adding new node at end of linked list
void addNode(struct SingleLL *sll, int data)
{
    // Create dynamic node
    struct LinkNode *node = (struct LinkNode *)
    malloc(sizeof(struct LinkNode));
    if (node == NULL)
    {
        printf("Memory overflow to Create LinkNode\n");
        return;
    }
    else
    {
        // Set initial node value
        node->data = data;
        node->next = NULL;
    }
    if (sll->head == NULL)
    {
        sll->head = node;
    }
    else
    {
        sll->tail->next = node;
    }
    sll->tail = node;
}
// Display linked list element
void display(struct LinkNode *node)
{
    if (node == NULL)
    {
        return;
    }
    struct LinkNode *temp = node;
    // iterating linked list elements
    while (temp != NULL)
    {
        printf(" %d →", temp->data);
        // Visit to next node
        temp = temp->next;
    }
    printf(" NULL\n");
}
int main(int argc, char const *argv[])
{
    struct SingleLL *sll = newLinkedList();
    // Linked list
    // 10 → 20 → 30 → 40 → 50 → NULL
    addNode(sll, 10);
    addNode(sll, 20);
    addNode(sll, 30);
    addNode(sll, 40);
    addNode(sll, 50);
    printf(" Linked List \n");
    display(sll->head);
    return 0;
}
 Linked List
 10 → 20 → 30 → 40 → 50 → NULL

Time complexity of above program is O(1).



Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved