Insert node in Linked list | Algorithm

💡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.

Insert node in Linked list | Algorithm | JavaScript

Selection Sort Algorithm & K’th Largest Element in Array

+25

JS Mount

Learn More

Insert node in Linked list | Algorithm | JavaScript

💡What is a Linked List?

💡Difference between Array and LinkedList?

💻 Create a Node Class

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

Leave a Reply Cancel Reply