Insert node in Linked list | Linked list insertion | insertion in a linked list in data structure | Linked list insertion algorithm | How to insert a node in a linked list | Linked list insertion algorithm | Singly linked list node insertion | insert node in linked list program

💡What is a Linked List?

Linked lists are linear data structures that store information in discrete nodes, or individual items. These nodes store the information as well as a pointer to the following node in the list.

A linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.

💡Difference between Array and LinkedList?

Array stores the data elements in a contiguous memory zone. Elements are stored in Linked Lists at random, or we could say anyplace in the memory area.

In Array, The elements are not dependent on each other. In the linked list, The data elements are dependent on each other.

In an array, When performing any action, such as insertion or deletion, it takes more time.

When performing any operation, such as insertion or deletion, the linked list requires less time.

Structure: [1, next] -> [2, next] -> [3, next] -> null

💻 Create a Node Class

class Node {
    value;
    next;
    constructor(value) {
        this.value = value;
        this.next = null; // initially next is null
    }
}


var head = new Node(1);
head.next = new Node(2);
console.log(head) // Node {value: 1, next: Node}

Insertion at beginning

function insertionAtStart(head, value) {
        let newNode = new Node(value);
        newNode.next = head;
        head = newNode;
        return head;
}

var head = new Node(1); // initial list
let list1 = insertionAtStart(head, 2);
console.log(list1)

let list2 = insertionAtStart(head, 3);
console.log(list2)

{
    "value": 3,
    "next": {
        "value": 1,
        "next": {
            "value": 2,
            "next": null
        }
    }
}

Insertion at End

function insertionAtEnd(head, value) {
    let current = head;
    while (current.next != null) { // finding last element
        current = current.next;
    }
    current.next = new Node(value); // assign new node to the last element next.
    return head;
}

var head = new Node(1);
console.log(insertionAtEnd(head, 2))
console.log(insertionAtEnd(head, 3))
console.log(insertionAtEnd(head, 4))

Insertion a element at start or end in empty linked list

function insert(head, value) {
    if (!head) {
        head = new Node(value);
    }
    return head;
}
insert(null, 1);

Complete program of insertion at end

// TC = O(n)
function insertAtEnd(head, value) {
    if (!head) {
        head = new Node(value);
    } else {
        let current = head;
        while (current.next != null) { // finding last element
            current = current.next;
        }
        current.next = new Node(value); // assign new node to the last element next.
    }
    return head;
}

 Insert at kth position

// TC = O(n)
function insertAtK(head, value, k) {

    if (k == 0) { // means new element will become Head
        let newNode = new Node(value);
        newNode.next = head; // assign head into next
        head = newNode;
    } else {
        let curr = head;
        let i = 0; // 0 based indexing

        // If I do (i < k) - it will reach to kth index while I have to stop at (k-1)
        while (i < k - 1 && curr.next != null) {
            curr = curr.next;
            i++;
        }
        let newNode = new Node(value);
        newNode.next = curr.next;
        curr.next = newNode;
    }
    console.log(head); // head means list
}

insertAtK(head, 'elephant', 3); // insert at 3rd position

{
    "value": "apple",
        "next": {
        "value": "banana",
            "next": {
*            "value": "cat", -- This is (k - 1) position
                "next": {
*                "value": "elephant",    -- // this is newly added item at kth position
                    "next": {
                    "value": "dog",
                        "next": null
                }
            }
        }
    }
} 

Print Linked list items

// TC = O(n)

// head here represents first item of list.
function printList(head) {
    let items = '';
    let curr = head;
    while (curr.next != null) {
        items = items + curr.value + ' ';
        curr = curr.next;
    }
    items = items + curr.data + ' ';
    console.log(items)
}
printList(head); // apple banana cat elephant
printList(new Node('pen')) // pen

❓What is diff in an array and linked list in case of insertion at the kth position while both take O(n) time complexity?

Insertion at the kth position in Array takes O(n)

Insertion at Kth position in the Linked list takes O(n)

However, linked lists are still preferred. Because when we add an item to an array at the kth position, we must move all items following that index to the next available location and copy their data, that process of copying and relocation takes a lot of effort.
While in the Linked list, everything is a Connection, which means two nodes are joined with only a connection. Therefore, if we add a new item, we simply update the connections between the previous and subsequent items. Everything is still as it was, in the same places. That makes a lot of sense.

• Unlocking the Secrets of Cookie | Power Your Web Experience
• AI vs Human: Exploring the Boundaries of Intelligence
• Enhancing User Experience with JavaScript Throttle and Debounce
• JavaScript Custom Promise | Promise Polyfill
• JavaScript Promisify | Convert Callbacks to Promises
• JavaScript Promise and Callbacks | Everything You Must Know
• CSS Display Property – Deep dive in block | inline | inline-block
• Implementation of Queue using Linked List | JavaScript
• Insert node in Linked list | Algorithm | JavaScript
• Insertion Sort in data structure | Algorithm with Examples
• Selection Sort Algorithm & K’th Largest Element in Array
• Quick Sort Algorithm with example | Step-by-Step Guide
• Dependency Inversion Principle with Example | Solid Principles
• Object-Oriented Programming | Solid Principles with Examples
• ASCII Code of Characters | String Operations with ASCII Code
• Negative Binary Numbers & 2’s Complement | Easy explanation
• Factors of a Number | JavaScript Program | Optimized Way
• LeetCode – Game of Life Problem | Solution with JavaScript
• Fibonacci series using Recursion | While loop | ES6 Generator
• JavaScript Coding Interview Question & Answers

Insert node in Linked list | Linked list insertion | insertion in a linked list in data structure | Linked list insertion algorithm | How to insert a node in a linked list | Linked list insertion algorithm | Singly linked list node insertion | insert node in linked list program | How to insert a node in a linked list

+25

0