Posted on by Kalkicode
Code Single linked list

Insert node at end of linked list

In computer science, linked lists are fundamental data structures used to store collections of elements. They consist of nodes, where each node holds a value and a reference (or "link") to the next node in the sequence. In this article, we'll address the problem of inserting a new node at the end of a singly linked list. We'll cover the problem statement, provide a step-by-step solution with pseudocode and explanations, discuss the time complexity of the solution, and finally, explain the provided code with an example and its output.

Problem Statement

Given a singly linked list, we want to insert a new node containing a specific value at the end of the list. This involves modifying the pointers of the last node in the list to point to the new node.

Solution

insert node at end of linked list
  1. Create a New Node

    To begin, we need to create a new node with the given data value.

  2. Insertion Process
    • If the linked list is empty (i.e., the head pointer is NULL), we set both the head and tail pointers to the new node.
    • If the linked list is not empty, we set the next pointer of the current tail node to point to the new node. Then, we update the tail pointer to the new node.
  3. Displaying Linked List

    To verify our insertion, we'll display the linked list elements.

Pseudocode

function addNode(sll, data):
    node = createNode(data)
    if sll.head is NULL:
        sll.head = node
        sll.tail = node
    else:
        sll.tail.next = node
        sll.tail = node

function display(node):
    temp = node
    while temp is not NULL:
        print temp.data
        temp = temp.next

function main():
    sll = newLinkedList()
    addNode(sll, 10)
    addNode(sll, 20)
    addNode(sll, 30)
    addNode(sll, 40)
    addNode(sll, 50)
    display(sll.head)

main()

Explanation

  1. In the addNode function, we first create a new node using the createNode function. If the linked list is empty, we set both the head and tail pointers to the new node. Otherwise, we update the next pointer of the current tail node and move the tail pointer to the new node.

  2. The display function traverses the linked list and prints each node's data value.

  3. In the main function, we create a new linked list, add elements 10, 20, 30, 40, and 50 using the addNode function, and then display the linked list using the display function.

Code Solution

Time Complexity

The time complexity of inserting a node at the end of a linked list is O(1), which means it's a constant-time operation. This is because we directly update the tail pointer to point to the new node, and we don't need to traverse the entire list to perform the insertion.

Comment

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