# Rotate an Array

This post deals with the question of how to rotate an array?

### Rotate an Array problem Statement :

Given an array ,we need to rotate the array the specified number of times. Array rotation can be done in 2 ways.

### Method 1:

This is the simplest way to solve the problem.

Algorithm:

1. Store the first “d” elements in a temp array.
2. Shift the elements of the array to the right or the left.
3. Store the “d” elements back in the array.

Here is the working code:

```#include <bits/stdc++.h>
using namespace std;

/*Function to rotate arr[] of size n by d*/
void RotateArray(int arr[], int d, int n)
{
int temp[d];

/*Storing d elements in temp array*/
for(int i=0;i<d;i++)
temp[i]=arr[i];

/*Shifting rest of array*/
for(int j=0;j<n-d;j++)
arr[j]=arr[j+d];

/*Storing back d elements*/
for(int k=n-d,i=0;k<n;k++,i++)
arr[k]=temp[i];
}

/* Function to print the array */
void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
cout<<arr[i]<<" ";
}

/* Driver program to test above functions */
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
printArray(arr,7);
RotateArray(arr, 3, 7);
cout<<"\nArray after Rotation is:\n";
printArray(arr, 7);
return 0;
}```

Output:

```1 2 3 4 5 6 7
Array after Rotation:
4 5 6 7 1 2 3```

Time Complexity : O(N)
Auxiliary space:O(d)

### Method 2:

We rotate the array one by one by storing the first element in temp variable and move A[1] to A[0]…and temp to A[n-1].

1. Rotate the array by 1 element.
2. Repeat the above process “d” times.

We are using left rotation in the solution.

```#include <bits/stdc++.h>
using namespace std;

/*Function to rotate an array k times*/
void RotateArray(int A[], int d, int n)
{
for (int i = 0; i < d; i++)
{
int j, temp;
/*Rotating array by one step*/
temp = A[0];
for (j = 0; j < n-1; j++)
A[j] = A[j+1];
A[j] = temp;
}
}

/*Function to print the array */
void printArray(int A[], int size)
{
for(int i=0; i < size; i++)
cout<<A[i]<<" ";
}

/*Driver program to test the above functions*/
int main()
{
int A[] = {10, 20, 30, 40, 50, 60, 70};
printArray(A,7);
RotateArray(A, 4, 7);
cout<<"\nArray After Rotation \n";
printArray(A, 7);
return 0;
}```

Output:

```10 20 30 40 50 60 70
Array After Rotation
50 60 70 10 20 30 40```

Time Complexity: O(N*d)
Space Complexity:O(1)

### Method 3:

Also known as the juggling algorithm this method extends method 2 and is used to rotate an array.
The algorithm divides the array into some blocks and then it swaps the elements present in the array in the intervals of length of GCD(n,d).
Instead of moving one by one, the array is divided in different sets where number of sets is equal to GCD of n and d and  the elements within sets are moved.
If GCD is 1, then elements will be moved within one set only, we just start with temp = arr[O] and keep moving arr[i+d] to arr[i] and finally store temp at the right place.

Algorithm:

1. Find GCD of “n” and “d”.Let it be “g”.
2. Array is divided into consecutive sets containing g elements.
3. The first element of each set is rotated once.
4. Then the second element and so on.

Example:

```Let the array be arr[]={1,2,3,4,5,6}. Here n=6 and d=2. GCD(6,2)=2

Array after first set elements are rotated. arr[]={3,2,5,4,1,6}
Array after second set elements are rotated. arr[]={3,4,5,6,1,2}```

Here is the working code in c++:

```#include <bits/stdc++.h>
using namespace std;

/*Function to get gcd of a and b*/
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}

/*Function to rotate arr[] of size n by d*/
void RotateArray(int arr[], int d, int n)
{
int i, j, k, temp;
for (i = 0; i < gcd(d, n); i++)
{
/* move i-th values of blocks */
temp = arr[i];
j = i;
while(1)
{
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}

/* Function to print the array */
void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
cout<<arr[i]<<" ";
}

/* Driver program to test above functions */
int main()
{
int arr[] = {10, 20, 30, 40, 50, 60, 70};
printArray(arr,7);
RotateArray(arr, 2, 7);
cout<<"\nArray after Rotation\n";
printArray(arr, 7);
return 0;
}
```

Output:

```10 20 30 40 50 60 70
Array after Rotation
30 40 50 60 70 10 20
```

Time Complexity:O(N)
Space Complexity:O(1)
It takes no extra space and its the most efficient algorithm to rotate an array.

# Deletion of a node from a Linked List at a given position.

Problem statement for deleting a node from Linked List:

Given a singly linked list, you need to delete a node from a given position.

Deletion of a node from Linked list Example:
Given the following singly linked list-

```80->34->19->56->10->62
```

If the 4th node is to be deleted, the resultant linked list after deletion of the node should be:

`80->34->19->10->62`

### Algorithm to delete a node from a given position in a Linked List:

1. Find the node at the position before the given position.
2. Change the next pointer of this node and make it point to the address of the node which is after the node to be deleted.
3. Free the memory allocated to the node to be deleted.

### Solution code in c++ for deleting a node from a given position in a singly linked list:

```#include <bits/stdc++.h>
using namespace std;

/*Standard structure that defines the node*/
struct node
{
int data;
node * next;
};

/*Function that inserts nodes in front of
{
node *temp = new node;
temp->data = data;
}

/*Function that will delete the node.
"pos" is the position of the node
to be deleted. */
{
/*"prev" will point to the node
whose position is before the node to be deleted.
"temp" is a copy of head pointer*/

node *prev;
is empty */
if(temp == NULL)
return;
/*If the head is the node that is
to be deleted*/
if(pos == 1)
{
delete temp;
return;
}

/*Traversing till we find the
node to be deleted*/
for(int i=1 ; i!=pos ; i++)
{
prev = temp;
temp = temp->next;
}

/*This condition is true, if the
data is not present in LL*/
if(temp == NULL)
{
cout<<"Data not present\n";
return;
}
else
{
/*Deletion of the node*/
prev->next = temp->next;
delete temp;
}
}

/*Function that is used to
{
{
}
cout<<"NULL";
}

int main()
{

/*Deleting node at position 4*/

return 0;
}
```

Output:

```Created Linked list is:
80-> 34-> 19-> 56-> 10-> 62-> NULL
80-> 34-> 19-> 10-> 62-> NULL```

Time Complexity of node deletion in a singly linked list: O(n)

This post deals with the question how to reverse a linked list? A linked list can be reversed either recursively or iteratively.

### Iterative Solution:

Here we use 3 pointers,
current, previous and next.

1. Change next pointer of current to point to previous.
2. Make prev = curr, curr = next.
3. Repeat the above process till we current is not NULL.

### Reverse a Linked List Problem Solution code in C++:

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in
struct node
{
int data;
node * next;
};

/*This function is used to add
new nodes to the Linked List*/
{
node *temp=new node;
temp->data=data;
}

/*This function is used to
{
{
}
cout<<endl;
}

/*This function is used to
{
node *prev=NULL;
node *next=NULL;
while(curr)
{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
}

/*driver program to test the
above function*/
int main() {

cout<<"The reverse List is: \n";
return 0;
}```

Output:

```Original Linked List:
85 15 4 20
The reverse List is:
20 4 15 85```

Time Complexity: O(N) where N is the number of nodes in the linked list.

### Algorithm to reverse a linked list recursively:

1. Start from the head node, pointed to by “first”.
2. If the next node is null, return.
3. Traverse the list recursively.
4. Set first->next->next to first.
5. Set first->next to NULL.

### Solution code for reversing a Linked List recursively:

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in
struct node
{
int data;
node * next;
};

/*This function is used to add
new nodes to the Linked List*/
{
node *temp = new node;
temp->data = data;
}

/*This function is used to
{
{
}
}

/*Function to reverse list*/
{

/*rest points to next of first*/
node* rest = first ->next;

/*if rest is the last node*/
if (rest == NULL)
{ return; }

/*recursive function call*/
reverse(&rest);

to second last node(new next)*/
first->next->next = first;

/*removes original links of the list*/
first->next = NULL;

}

/*driver program to test the
above function*/
int main()
{
cout<<" Entered list is: \n";

/*calling reverse function*/
cout<<"\nThe reverse List is: \n";
return 0;
}```

Output:

```Entered list is:
1 2 3 4 5
The reverse List is:
5 4 3 2 1
```

Time Complexity of reversing a linked list recursively is: O(N)
Space Complexity
of reversing a linked list recursively is: O(1)

# Print inorder traversal of a Binary Search Tree (BST) represented using array

Given a BST represented by an array, print inorder traversal of this array, i.e. print the elements of the array is such a way, that it represents the inorder Traversal of a BST.

### Print inorder traversal of a Binary Search Tree (BST) represented using array Example:

```Input:
4
/     \
2       6
/  \     /  \
1    3    5   7
This BST is stored in array as
arr[] = {4, 2, 6, 1, 3, 5, 7}

The Output should be:
1 2 3 4 5 6 7```

### Print inorder traversal of a Binary Search Tree (BST) represented using array Solution:

When a tree is stored using an array, then if the parent is given by the index i,
Then its
left child is given by index 2*i +1,
right child is given by index 2*i +2.

So, we recursively use first print the left subtree, followed by the present node and then the rescursively the right subtree.
We use the start and end indexes of the array to stop the recursion.

### Print inorder traversal of a Binary Search Tree (BST) represented using array code in C++:

```#include<bits/stdc++.h>
using namespace std;

void printInorder(int a[],int start,int end)
{
if(start>end)
return;
/*Printing the left subtree*/
printInorder(a,start*2+1,end);

/*printing present value*/
cout<<a[start]<<" ";

/*Printing the right subtree*/
printInorder(a,start*2+2,end);
}

int main()
{
int arr[] = {4, 2, 6, 1, 3, 5, 7};
int arr_size = sizeof(arr)/sizeof(int);
cout<<"The InOrder Traversal is:\n";
printInorder(arr, 0, arr_size-1);
return 0;
}```

Output:

```The InOrder Traversal is:
1 2 3 4 5 6 7```

Time Complexity: O(N) as all nodes are visited once.

# Remove Binary Search Tree (BST) keys outside a given range

Or Remove BST keys that don’t lie in given range/remove bina.

### Remove BST keys outside a given range Problem Statement:

Given a Binary Search Tree(BST) and a range say [ k1 , k2 ], remove all the nodes, whose values lie outside the given range.
While removing the nodes, the BST property is maintained.

### Remove BST keys outside a given range Example:

```Input:
10
/      \
5        20
/   \      /  \
1     7    15   25

Range = [6,22]
Output after Modification:

10
/    \
7      20
/
15```

### Remove Binary Search Tree (BST) keys outside a given range solution:

Here we follow POST-ORDER fashion to remove nodes.
This way when we reach a root node, its children are already processed and we do not need to worry about the sub-trees below this node.

When we find a node that is not in range, there can be two cases that arise:

1. Node’s data is smaller than the min value.
Here remove the root, and return the right subtree as the new root.
2. Node’s data is greater that the max value.
Here remove the root, and return the left subtree as the new root.

Note that when we return the left/right subtrees, they have already been processed.

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
int data;
node *left;
node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
node *temp=new node;
temp->left=NULL;
temp->right=NULL;
temp->data=key;
return temp;
}

/*This funciton is used to Insert
new values in BST*/
node *Insert(node *root,int key)
{
if(!root)
return newNode(key);
if(key<root->data)
root->left=Insert(root->left,key);
else
root->right=Insert(root->right,key);
return root;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
if(!root)
return;
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}

/*This function deletes the nodes whose value
doesn't lie in range. It follows Postorder fashion*/
node *RemoveKeysNotInRange(node *root,int min,int max)
{
if(!root)
return NULL;

/*PostOrder fashion is followed*/
root->right=RemoveKeysNotInRange(root->right,min,max);
root->left=RemoveKeysNotInRange(root->left,min,max);

/*These Ifs are self explainatory*/
if(root->data < min)
{
node *temp=root->right;
delete root;
return temp;
}
if(root->data > max)
{
node *temp=root->left;
delete root;
return temp;
}
return root;
}

int main() {
/* Let us create following BST
10
/    \
5     20
/  \    /  \
1    7  15   25 */
node *root = NULL;
root = Insert(root, 10);
Insert(root, 20);
Insert(root, 25);
Insert(root, 15);
Insert(root, 5);
Insert(root, 7);
Insert(root, 1);

cout << "Inorder traversal of the given BST is: ";
Inorder(root);

root = RemoveKeysNotInRange(root, 6, 22);

cout << "\nInorder traversal of the modified BST is: ";
Inorder(root);
return 0;
}```

Output:

```Inorder traversal of the given BST is: 1 5 7 10 15 20 25
Inorder traversal of the modified BST is: 7 10 15 20```

Time Complexity: O(N) as all  nodes are visited once.

# Inorder Successor and Predecessor of a given Key in Binary Search Tree (BST)

### Inorder Successor and Predecessor of a given Key in BST Problem Statement:

Given a Binary Search Tree (BST) and a key, you need to tell the values will precede and succeed the given key in the Inorder Traversal.
If the given key doesn’t exist in the BST, then print the values between which the given key will lie.

### Algorithm to find the Inorder Successor and Predecessor of a given Key in Binary Search Tree (BST):

1. Return if root is NULL.
2. If the root->data = key, then
1. If the Left subtree exists,
then the predecessor is the Rightmost node is the left subtree.
2. If the Right subtree exists,
then the Successor is the Left node is the Right subtree.
3. Return.
3. If root->data > key
1. set successor = root.
2. Recur on left Subtree.
4. If root->data < key
1. set Predecessor = root.
2. Recur on Right Subtree.

The above algorithm also works even if the key does’t exist in the tree. In that case, it gives the range in which the number lies.

### C++ code to find Inorder Successor and Predecessor of a given Key in BST :

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
int data;
node *left;
node *right;
};

/*This functio is used to create and
initialise new nodes*/
node *newNode(int key)
{
node *temp=new node;
temp->left=NULL;
temp->right=NULL;
temp->data=key;
return temp;
}

/*This funciton is used to Insert
new values in BST*/
node *Insert(node *root,int key)
{
if(!root)
return newNode(key);
if(key<root->data)
root->left=Insert(root->left,key);
else
root->right=Insert(root->right,key);
return root;
}

/*This function is used to find Inorder successor and
Predecessor. NOTE that we pass the variables by
reference */
void inorderPreSuc(node *root, node *&pre, node *&suc,int key)
{
if(!root)
return;
/*Here the key is found*/
if(root->data==key)
{
if(root->left)
{
/*Finding the Right most
node of left subtree*/

node *temp=root->left;
while(temp->right)
temp=temp->right;
pre=temp;
}
if(root->right)
{
/*Finding the left most
node of right subtree*/

node *temp=root->right;
while(temp->left)
temp=temp->left;
suc=temp;
}
return;
}
if(root->data > key)
{
suc=root;
/*Recur on left subtree*/
inorderPreSuc(root->left,pre,suc,key);
}
else
{
pre=root;
/*Recur on right subtree*/
inorderPreSuc(root->right,pre,suc,key);
}

}

int main() {
int key = 20;    //Key to be searched in BST

/* Let us create following BST
10
/    \
5     20
/  \    /  \
1    7  15   25 */
node *root = NULL;
root = Insert(root, 10);
Insert(root, 20);
Insert(root, 25);
Insert(root, 15);
Insert(root, 5);
Insert(root, 7);
Insert(root, 1);

node *pre = NULL, *suc = NULL;

inorderPreSuc(root, pre, suc, key);
/*Checking the existence of predecessor and
successor*/
if (pre)
cout << "Predecessor is " << pre->data << endl;
else
cout << "No Predecessor";

if (suc)
cout << "Successor is " << suc->data;
else
cout << "No Successor";

return 0;
}```

Output:

```Predecessor is 15
Successor is 25```

Time Complexity: O(H) where H is the height of the BST

# Convert BST to Greater Sum Tree

This problem can also be stated as BST to Binary Tree Conversion with data of nodes as the sum of all greater elements.

This program/question can be seen as an extension/ modification of converting BST to Binary Tree with data of nodes as sum of all greater value nodes.

### Convert BST to Greater Sum Tree Problem Statement:

Given a Binary Search Tree (BST), we need to add to each node, the sum of all greater values node.

### Convert BST to Greater Sum Tree Example:

```Input:
10
/      \
5        20
/   \      /  \
1     7    15   25

Output after Modification:

60
/      \
77        25
/   \      /  \
82    70    45   0```

NOTE: This program will convert a BST into a Binary Tree with value of nodes as the sum of all greater elements.

### Convert Binary Search Tree to Greater Sum Tree solution:

We use Reverse Inorder Traversal (recursion is called on right subtree first rather than left subtree) and maintain a variable to store the sum of nodes that have been traversed so far.

We then use this sum to modify the value of our present node, by first adding its value to the sum, and then replacing the value of the node with this sum.

#### C/C++ code for converting BST to Greater Sum Tree:

```#include <bits/stdc++.h>
using namespace std;

/*Stucture of each node of the tree*/
struct node
{
int data;
node *left;
node *right;
};

/*Function that allocates memory for
each new node and initialises it*/
node *newNode(int key)
{
node *temp=new node;
temp->left=NULL;
temp->right=NULL;
temp->data=key;
return temp;
}

/*This functions is used to print the
inOrder traversal of the array*/
void Inorder(node *root)
{
if(!root)
return;
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}

/*This function inserts new nodes
into the Binary Search Tree*/
node *Insert(node *root,int key)
{
if(!root)
return newNode(key);
if(key<root->data)
root->left=Insert(root->left,key);
else
root->right=Insert(root->right,key);
return root;
}

/*The function that uses reverse
value of all greater elements*/
{
if(!root)
return;

then replace the value in
node*/
sum += root->data;
root->data = sum - root->data;

}

/*utility function that hides
the actual implementation using
the above function*/
{
int sum=0;
}

int main() {
/* Let us create following BST
10
/    \
5     20
/  \    /  \
1    7  15   25 */
node *root = NULL;
root = Insert(root, 10);
Insert(root, 20);
Insert(root, 25);
Insert(root, 15);
Insert(root, 5);
Insert(root, 7);
Insert(root, 1);

cout<<"Initial BST Inorder Travesal:\n";
Inorder(root);
cout<<endl;

/*print inoder tarversal of
the modified BST*/
cout<<"Modified BST Inorder Travesal:\n";
Inorder(root);
cout<<endl;
return 0;
}```

Output:

```Initial BST Inorder Travesal:
1 5 7 10 15 20 25
Modified BST Inorder Travesal:
82 77 70 60 45 25 0```

Time Complexity: O(n) where n is number of nodes in the given BST.

# Lowest Common Ancestor (LCA) in Binary Search Tree (BST)

### Problem Statement LCA in a binary Search Tree (BST):

Given a binary search Tree(BST) and two numbers, we need to print the LCA of these two numbers numbers.
It can be assumed for simplicity that both these numbers exist in the given BST.

### LCA of two numbers:

Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

### Lowest Common Ancestor in a binary Search Tree (BST) Example:

```        80
/  \
60   110
/  \   /  \
35  40  85 130```

Case I:
If the two numbers are 85 and 40 then the output is 80, as it is the only node that has both of these numbers as descendants.

Case II:
If the two numbers are 110 and 130 then the output is 110, as per the definition of LCA given above.

### Lowest Common Ancestor in a Binary Search Tree (BST) Solution:

Here we use recursion to find  the LCA of two number, there can be 3 cases that arise:

1. If both the numbers are less than the root’s data, then LCA lies in the left subtree,and we recur on it.
n1,n2<root’s data.
2. If both the numbers are greater than the root’s data, then LCA lies in the right subtree,and we recur on it.
n1,n2 > root’s data.
3. If any of the above case doesnt match, then we have our LCA as this node, print the data of this node.This case is combination of these 2 sub-cases:
1. If the root’s data lies between the two numbers.
n1<root’s data<n2 or n2<root’s data<n1.
2. If one of the number matches with the root’s data.
root’s data == n1 or n2.

#### Lowest Common Ancestor (LCA) in a Binary Search Tree (BST) Solution in c++:

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node of tree*/
struct node{
int data;
node *left;
node *right;
};

/*This function creates and
initialises new nodes*/
node * newNode(int data)
{
node * temp = new node;
temp->data=data;
temp->right=temp->left=NULL;
return temp;
}

/*This function inserts new nodes
int the Binary Search Tree*/
node * Insert(node * root, int data)
{
if(!root)
return newNode(data);

if(data<root->data)
root->left=Insert(root->left,data);
else
root->right=Insert(root->right,data);

return root;
}

/*This function is used or print the
LCA of two numbers*/
void LCA(node *root,int n1,int n2)
{
if(!root)
return;

/*If both numbers are smaller than
the root's data, then LCA lies on
left subtree*/
if(root->data >n1 && root->data >n2 )
return LCA(root->left,n1,n2);

/*If both numbers are greater than
the root's data, then LCA lies on
right subtree */
else if(root->data <n1 && root->data <n2 )
return LCA(root->right,n1,n2);
else
{
/*this case occurs when either of
the number matches with the root's
data or root's data lies in between
of the two numbers*/
cout<<"The LCA of "<<n1<<" and "
<<n2<<" is \n"<<root->data<<"\n";
return;
}
}

/* Driver Program to test above functions */
int main()
{
/* The following insertions create this
Binary Search Tree
80
/     \
60      110
/  \    /  \
35   40  85   130 */

node *root = NULL;
root = Insert(root, 80);
Insert(root, 110);
Insert(root, 85);
Insert(root, 130);
Insert(root, 60);
Insert(root, 40);
Insert(root, 35);

/*Finding LCA of n1 and n2*/
int n1=110,n2=130;
LCA(root,n1,n2);
LCA(root,85,40);
return 0;
}```

Output:

```The LCA of 110 and 130 is
110
The LCA of 85 and 40 is
80```

Time Complexity: O(H) where H is the height of the tree

This post will cover Introduction to Doubly Linked List  (DLL) , we recommend you go through Singly Linked List, to get a better understanding.

A Doubly Linked List (DLL) contains two pointers along with the data.
One of them points to the next node in the sequence, known as next pointer.
The other points back to the last node in the sequence, known as previous pointer.

Following is representation of a Doubly Linked List (DLL) node in C/C++ language:

### Doubly Linked List Introduction Video Explanation:

We recommend you go through this video too, to get a complete understanding.

### Doubly Linked list representation in c++:

Each node contains a data variable and 2 pointers 1 pointing to the previous node, and one pointing to the next node.

```struct node
{
int data;
node *next;
node *prev;
};```

1. A Doubly Linked List (DLL) can be traversed in both forward and backward direction.
2. The delete operation in Doubly Linked List (DLL) can be done in constant time: In singly linked list, to delete a node, pointer to the node before it is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

1. The nodes require extra space for an previous pointer. It is possible to implement Doubly Linked List (DLL) with single pointer though.
2. All operations require the extra pointer previous to be maintained and rewired along with the next pointer.

Up until now, we used arrays to store linear data of similar types but arrays have following limitations:

1. The size of the array must be known beforehand i.e. must know the upper limit on the number of elements in advance.
2. Inserting a new element in an array of elements is more time taking, because space has to be created for the new elements by shifting old ones.
3. Deletion is also time taking with arrays.

For example:
In a system if we maintain a sorted list of numbers in an array arr[ ].
arr[ ] = {10, 11, 15, 20, 40}
Consider we want to insert a new number, 12, then we have to move all elements after and including 15.
Similarly if we have to delete 15, we will have to shift everything after it to one place to the left.

This post is a can be used as Linked list tutorials for beginners, or by anyone who wants to clear the basics of Linked List.

### Linked List Representation in C/C++:

Each node in a list consists of at least two parts:

1. Data: The information we store in arrays as elements.
2. Pointer to the next node: Address of the location of the next node of the linked list.

We use a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then value of head is NULL.