**WHAT IS LINKED LIST :**

Linked list is a data structure which contains a set of elements linked to its successor.

**WHERE TO USE LINKED LIST** :

When there is a need of lot of insertions and deletions , linked list is preferred over Array .

One simple example is this : Say we have array of 1000 numbers . 2 to 1001 . Now we need to insert 1 at the beginning of the array. Its not so simple, we need to shift all the numbers from 2 to 1001 one step right for inserting one element at the beginning.

Linked list over comes this problem. Just allocate memory and play with pointers to give connections. 1 will be inserted at the beginning.

**WHERE NOT TO USE LINKED LIST :**

There are certain scenarios where in we need more number of searches than insert and delete. On such occasion arrray gives us a better result.

**HOW TO IMPLEMENT LINKED LIST :**

In this post we will be discussing 12 basic set of items on linked list

1. Structure of Linked List

2. Creating One node Linked List

3. Creating 3 Node Linked List

4. Creating N Node linked List

5. Inserting a node at front of linked list

6. Inserting a node at end of linked list

7. Inserting a node at N point of linked list

8. Deleting first element from list

9. Deleting last element from list

10. Deleting random element from list

11. Searching linked list

12. Copying Linked lis**t**

**STRUCTURE OF LINKED LIST**

A linked list contains data element along with the pointer which points to the next element.

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

**Creating One node Linked List:**

Lets create a simple one node linked list . For creating a node , we need to follow three steps.

- Create a new node pointer
- Allocate memory and insert element
- Point the pointer to appropriate position

#include // for cout
#include // for malloc
using namespace std;
// create the struture of linked list
struct node
{
int data;
struct node* next;
};
void print_ll(struct node* head);
int main()
{
// create head pointer
struct node* head = NULL;
// allocate memory to it
head = (struct node*) malloc(sizeof(struct node));
// insert the data
head->data = 1;
// point the next pointer
head->next = NULL;
// printing the list
print_ll(head);
return 0;
}
void print_ll(struct node* head)
{
struct node* current = head;
cout << "List contains" <<endl;
while(current != NULL)
{
cout << current->data << endl;
current = current->next;
}
}

**CREATING 3 NODE LINKED LIST**

Now, we know the size of linked list. So, lets create a function that will build 3 nodes in a linked list.

#include <iostream> // for cout
#include <stdlib.h> // for malloc
using namespace std;
// create the struture of linked list
struct node
{
int data;
struct node* next;
};
void print_ll(struct node* head);
struct node* three_node_ll();
int main()
{
// call the function to create the list
struct node* head = three_node_ll();
// printing the list
print_ll(head);
return 0;
}
struct node* three_node_ll()
{
// create 3 pointers for 3 nodes
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
// allocate memory for 3 nodes
head = (struct node*) malloc(sizeof(struct node));
second = (struct node*) malloc(sizeof(struct node));
third = (struct node*) malloc(sizeof(struct node));
// insert data into 3 nodes and point the sequence in right order
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
return head;
}
void print_ll(struct node* head)
{
struct node* current = head;
cout << "List contains" <<endl;
while(current != NULL)
{
cout << current->data << endl;
current = current->next;
}
}

**CREATING N NODE LINKED LIST**

In the previous case, we know the definite size of linked list . But , now we need to build a list based on the input given by the user. Hence , we need to write a generic function which will insert the numbers into list dynamically.It is easy to push elements at the front of the list . It comprises of 3 steps.

- Allocate memory for the new node and insert data into it.
- Point the next pointer to old head
- Change head to new node

#include <iostream> // for cout
#include <stdlib.h> // for malloc
using namespace std;
// create the struture of linked list
struct node
{
int data;
struct node* next;
};
void print_ll(struct node* head);
void n_node_ll(struct node*&,int);
int num_of_nodes;
int main()
{
cout << "Enter number of nodes to be created " << endl;
cin >> num_of_nodes;
struct node* head = NULL;
// call the function to create the list
for(int i=0 ; i<num_of_nodes; i++)
{
n_node_ll(head,i+1);
}
// printing the list
print_ll(head);
return 0;
}
void n_node_ll(struct node*& head, int d)
{
// allocate memory and insert data
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = d;
// point next pointer to old head
newNode->next = head;
// point head to new node
head = newNode;
}
void print_ll(struct node* head)
{
struct node* current = head;
cout << "List contains" <<endl;
while(current != NULL)
{
cout << current->data << endl;
current = current->next;
}
}

INSERTING NODE AT FRONT OF LINKED LIST

Say, we have linked list with 2 elements . 4 and 3 . Now we need to push 5 into the list at the front .

As explained in the previous code , it will be done with same 3 steps.

#include <iostream> // for cout
#include <stdlib.h> // for malloc
using namespace std;
// create the struture of linked list
struct node
{
int data;
struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_front(struct node*&,int);
int main()
{
// call the function to create the list
struct node* head = two_node_ll();
// inserting number 5 at the front
insert_at_front(head,5);
// printing the list
print_ll(head);
return 0;
}
void insert_at_front(struct node*& head,int d)
{
struct node* current = head;
// create node and allocate memory
struct node* newNode = (struct node*)malloc(sizeof(struct node));
//insert data into the memory
newNode->data = d;
// point the next pointer to old head
newNode->next = head;
// change head of the list to new node
head = newNode;
}
struct node* two_node_ll()
{
// create 3 pointers for 3 nodes
struct node* head = NULL;
struct node* second = NULL;
// allocate memory for 3 nodes
head = (struct node*) malloc(sizeof(struct node));
second = (struct node*) malloc(sizeof(struct node));
// insert data into 3 nodes and point the sequence in right order
head->data = 4;
head->next = second;
second->data = 3;
second->next = NULL;
return head;
}
void print_ll(struct node* head)
{
struct node* current = head;
cout << "List contains" <<endl;
while(current != NULL)
{
cout << current->data << endl;
current = current->next;
}
}

**INSERTING A NODE AT END OF THE LIST**

For adding the node at the tail end we need to follow these steps

- Iterate through the list and find the point the last element in the list
- Create new node and insert data to it
- Point the next pointer of new node to null since it is going to be the last element
- Link the old last element pointer to new node

#include <iostream> // for cout
#include <stdlib.h> // for malloc
using namespace std;
// create the struture of linked list
struct node
{
int data;
struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_end(struct node*&,int);
int main()
{
// call the function to create the list
struct node* head = two_node_ll();
// inserting number 3 at the end
insert_at_end(head,3);
// printing the list
print_ll(head);
return 0;
}
void insert_at_end(struct node*& head,int d)
{
struct node* current = head;
while(current->next != NULL)
{
current = current->next;
}
// create node and allocate memory
struct node* newNode = (struct node*)malloc(sizeof(struct node));
//insert data into the memory
newNode->data = d;
// point the next pointer to null since its the last element
newNode->next = NULL;
// change head of the list to new node
current->next = newNode;
}
struct node* two_node_ll()
{
// create 3 pointers for 3 nodes
struct node* head = NULL;
struct node* second = NULL;
// allocate memory for 3 nodes
head = (struct node*) malloc(sizeof(struct node));
second = (struct node*) malloc(sizeof(struct node));
// insert data into 3 nodes and point the sequence in right order
head->data = 5;
head->next = second;
second->data = 4;
second->next = NULL;
return head;
}
void print_ll(struct node* head)
{
struct node* current = head;
cout << "List contains" <<endl;
while(current != NULL)
{
cout << current->data << endl;
current = current->next;
}
}