Insert an element in the Linked List at any given position

Given a singly linked list, the task is to insert a new node at the beginning, at any given position, or at the end of the list. 

Input-Output Examples

Example 1: Insert at the beginning

  • Input:
    • List: 1 -> 2 -> 3 -> NULL
    • Value: 0
    • Position: 0
  • Output: 0 -> 1 -> 2 -> 3 -> NULL

Example 2: Insert at a given position

  • Input:
    • List: 1 -> 2 -> 3 -> NULL
    • Value: 4
    • Position: 2
  • Output: 1 -> 2 -> 4 -> 3 -> NULL

Example 3: Insert at the end

  • Input:
    • List: 1 -> 2 -> 3 -> NULL
    • Value: 5
    • Position: 3
  • Output: 1 -> 2 -> 3 -> 5 -> NULL

Approach:

To insert a new node in the linked list, we need to handle three cases: inserting at the beginning, inserting at a given position, and inserting at the end. We will use a single function that takes the head of the list, the value to be inserted, and the position as parameters.

Steps to implement:

  1. Insert at the Beginning:
    • Create a new node with the given value.
    • Set the new node's next pointer to the current head.
    • Update the head to the new node.
  2. Insert at a Given Position:
    • Traverse the list to the node just before the given position.
    • Create a new node with the given value.
    • Set the new node's next pointer to the next node of the current node.
    • Set the current node's next pointer to the new node.
  3. Insert at the End:
    • Traverse the list to the last node.
    • Create a new node with the given value.
    • Set the last node's next pointer to the new node.

C++ Program to insert an element in the Linked List at given position

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to insert a new node at the specified position
ListNode* insertAtPosition(ListNode* head, int val, int position) {
    ListNode* newNode = new ListNode(val);
    
    // Insert at the beginning
    if (position == 0) {
        newNode->next = head;
        return newNode;
    }
    
    ListNode* current = head;
    for (int i = 0; current != NULL && i < position - 1; i++) {
        current = current->next;
    }
    
    // If position is greater than the number of nodes, insert at the end
    if (current == NULL) {
        cout << "Position is greater than the number of nodes. Inserting at the end." << endl;
        current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
        return head;
    }
    
    // Insert at the given position
    newNode->next = current->next;
    current->next = newNode;
    
    return head;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    
    // Insert at the beginning
    head = insertAtPosition(head, 0, 0);
    cout << "After inserting 0 at position 0: ";
    printList(head);
    
    // Insert at the given position
    head = insertAtPosition(head, 4, 2);
    cout << "After inserting 4 at position 2: ";
    printList(head);
    
    // Insert at the end
    head = insertAtPosition(head, 5, 5);
    cout << "After inserting 5 at position 5: ";
    printList(head);
    
    return 0;
}

Java Program to insert an element in the Linked List at given position

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Main {
    // Function to insert a new node at the specified position
    public static ListNode insertAtPosition(ListNode head, int val, int position) {
        ListNode newNode = new ListNode(val);
        
        // Insert at the beginning
        if (position == 0) {
            newNode.next = head;
            return newNode;
        }
        
        ListNode current = head;
        for (int i = 0; current != null && i < position - 1; i++) {
            current = current.next;
        }
        
        // If position is greater than the number of nodes, insert at the end
        if (current == null) {
            System.out.println("Position is greater than the number of nodes. Inserting at the end.");
            current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            return head;
        }
        
        // Insert at the given position
        newNode.next = current.next;
        current.next = newNode;
        
        return head;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 3 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        
        // Insert at the beginning
        head = insertAtPosition(head, 0, 0);
        System.out.print("After inserting 0 at position 0: ");
        printList(head);
        
        // Insert at the given position
        head = insertAtPosition(head, 4, 2);
        System.out.print("After inserting 4 at position 2: ");
        printList(head);
        
        // Insert at the end
        head = insertAtPosition(head, 5, 5);
        System.out.print("After inserting 5 at position 5: ");
        printList(head);
    }
}

Python Program to insert an element in the Linked List at given position

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Function to insert a new node at the specified position
def insert_at_position(head, val, position):
    new_node = ListNode(val)
    
    # Insert at the beginning
    if position == 0:
        new_node.next = head
        return new_node
    
    current = head
    for _ in range(position - 1):
        if current is None:
            break
        current = current.next
    
    # If position is greater than the number of nodes, insert at the end
    if current is None:
        print("Position is greater than the number of nodes. Inserting at the end.")
        current = head
        while current.next is not None:
            current = current.next
        current.next = new_node
        return head
    
    # Insert at the given position
    new_node.next = current.next
    current.next = new_node
    
    return head

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 3 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# Insert at the beginning
head = insert_at_position(head, 0, 0)
print("After inserting 0 at position 0:", end=" ")
print_list(head)

# Insert at the given position
head = insert_at_position(head, 4, 2)
print("After inserting 4 at position 2:", end=" ")
print_list(head)

# Insert at the end
head = insert_at_position(head, 5, 5)
print("After inserting 5 at position 5:", end=" ")
print_list(head)

DSA

8928

111

Related Articles