Insert Node at end of Linked List

Problem Statement: Given a linked list and an integer value val, insert a new node with that value at the end (after the tail) of the list and return the updated linked list.

Examples

Example 1:

Input Format: 0->1->2 , val = 5

Result: 0->1->2->5

Explanation: We need to insert the value 5 after the tail of the given Linked List.

Example 2:

Input Format:12->5->8->7 , val = 100

Result: 12->5->8->7->100

Explanation: Again, we need to insert the value 100 after the tail of the Linked List.

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

To insert a new node after the tail of the linked list, create a new node pointing to NULL. This node will effectively be the new tail of the linked list. Traverse till the last node of the linked list and point it to the new node created to get the new tail of the linked list.

Algorithm:

  • Create a new node with data as the given value and pointing to the NULL. This node will be made our new tail of the linked list.
  • Initialize a temp pointer to the head that will be used to traverse the linked list.
  • Once it is iterated to the last node, point the tail to the new node created, making it the new tail of the linked list.
  • Return the head of the linked list to get the final updated linked list.

Code:

C++ Code

// Node class to represent a linked list node
class Node {
public:
    int data;
    Node* next;

    // Constructor with both data and next node
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data (assuming next is initially null)
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

// Function to print the linked list
void printLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

// Function to insert a new node at the tail of the linked list
Node* insertTail(Node* head, int val) {
    if (head == NULL)
        return new Node(val);

    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    Node* newNode = new Node(val);
    temp->next = newNode;

    return head;
}

int main() {
    // Sample array and value for insertion
    vector<int> arr = {12, 8, 5, 7};
    int val = 100;

    // Creating a linked list with initial elements from the array
    Node* head = new Node(arr[0]);
    head->next = new Node(arr[1]);
    head->next->next = new Node(arr[2]);
    head->next->next->next = new Node(arr[3]);

    // Inserting a new node at the tail of the linked list
    head = insertTail(head, val);

    // Printing the linked list
    printLL(head);

    return 0;
}

Output:

12 8 5 7 100

Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.

Space Complexity: O(1), as we have not used any extra space.

Java Code

// Node class to represent a linked list node
class Node {
    public int data;
    public Node next;

    // Constructor with both data and next node
    public Node(int data1, Node next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data (assuming next is initially null)
    public Node(int data1) {
        data = data1;
        next = null;
    }
}

public class Main {
    // Function to print the linked list
    public static void printLL(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }

    // Function to insert a new node at the tail of the linked list
    public static Node insertTail(Node head, int val) {
        if (head == null)
            return new Node(val);

        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }

        Node newNode = new Node(val);
        temp.next = newNode;

        return head;
    }

    public static void main(String[] args) {
        // Sample array and value for insertion
        List<Integer> arr = Arrays.asList(12, 8, 5, 7);
        int val = 100;

        // Creating a linked list with initial elements from the array
        Node head = new Node(arr.get(0));
        head.next = new Node(arr.get(1));
        head.next.next = new Node(arr.get(2));
        head.next.next.next = new Node(arr.get(3));

        // Inserting a new node at the tail of the linked list
        head = insertTail(head, val);

        // Printing the linked list
        printLL(head);
    }
}

Output:

12 8 5 7 100

Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.

Space Complexity: O(1), as we have not used any extra space.

Python Code

# Node class to represent a linked list node
class Node:
    def __init__(self, data1, next1=None):
        self.data = data1
        self.next = next1

# Function to print the linked list
def printLL(head):
    while head is not None:
        print(head.data, end=" ")
        head = head.next

# Function to insert a new node at the tail of the linked list
def insertTail(head, val):
    if head is None:
        return Node(val)

    temp = head
    while temp.next is not None:
        temp = temp.next

    new_node = Node(val)
    temp.next = new_node

    return head

if __name__ == "__main__":
    # Sample array and value for insertion
    arr = [12, 8, 5, 7]
    val = 100

    # Creating a linked list with initial elements from the array
    head = Node(arr[0])
    head.next = Node(arr[1])
    head.next.next = Node(arr[2])
    head.next.next.next = Node(arr[3])

    # Inserting a new node at the tail of the linked list
    head = insertTail(head, val)

    # Printing the linked list
    printLL(head)

Output:

12 8 5 7 100

Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.

Space Complexity: O(1), as we have not used any extra space.

JavaScript Code

// Node class to represent a linked list node
class Node {
    constructor(data1, next1 = null) {
        this.data = data1;
        this.next = next1;
    }
}

// Function to print the linked list
function printLL(head) {
    while (head !== null) {
        console.log(head.data + " ");
        head = head.next;
    }
}

// Function to insert a new node at the tail of the linked list
function insertTail(head, val) {
    if (head === null) {
        return new Node(val);
    }

    let temp = head;
    while (temp.next !== null) {
        temp = temp.next;
    }

    const new_node = new Node(val);
    temp.next = new_node;

    return head;
}

// Sample array and value for insertion
const arr = [12, 8, 5, 7];
const val = 100;

// Creating a linked list with initial elements from the array
let head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);
head.next.next.next = new Node(arr[3]);

// Inserting a new node at the tail of the linked list
head = insertTail(head, val);

// Printing the linked list
printLL(head);

Output:

12 8 5 7 100

Time Complexity: O(N) for traversing the linked list and inserting the new node after the tail.

Space Complexity: O(1), as we have not used any extra space.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article