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
}
}

console.log(head) // Node {value: 1, next: Node}
```

Insertion at beginning

```function insertionAtStart(head, value) {
let newNode = new Node(value);
}```
``````var head = new Node(1); // initial list
console.log(list1)

console.log(list2)``````
``````{
"value": 3,
"next": {
"value": 1,
"next": {
"value": 2,
"next": null
}
}
}``````

Insertion at End

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

Insertion a element at start or end in empty linked list

```function insert(head, value) {
}
}
insert(null, 1);```

Complete program of insertion at end

```// TC = O(n)
} else {
while (current.next != null) { // finding last element
current = current.next;
}
current.next = new Node(value); // assign new node to the last element next.
}
}```

Insert at kth position

```// TC = O(n)

if (k == 0) { // means new element will become Head
let newNode = new Node(value);
} else {
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;
}
}```
``````
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
}
}
}
}
} ``````

```// TC = O(n)

// head here represents first item of list.
let items = '';
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 | 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