What is a Linked list?

A link list is a linear data structure that can link one element with another through pointers. In the linked list elements are not placed back to back.

Linked List

Why we used a linked list over arrays?

The size of the arrays is fixed
Inserting a new element in an array of elements is expensive
Deletion is also expensive with arrays unless some special techniques are used.

Advantages over arrays

1) Dynamic size
2) Ease of insertion/deletion

Representation:

A linked list is represented by a pointer to the first node of the linked list.
The first node is called the head.
Each node in a list consists of at least two parts:
1) data
2) Pointer (Or Reference) to the next node



#include<iostream>
using namespace std;
struct node       
{
	int data;
	node *next;
};
node *head=NULL;
node *tail=NULL;
node* create_node (int val)
{
	node* temp = new node;   
	temp->data=val;          
	temp->next=NULL;
	if(head == NULL)
        {
            head = temp;
            tail = temp;
        }
        else
        {
            tail->next = temp;
            tail = tail->next;
        }
	return temp;
}
void insert_start(int val)
{
	node* temp = new node;
    temp->data=val;
    temp->next=head;
    head=temp;
}
void insert_after(int val)
{
	node *temp = new node;
	temp->data=val;
	temp->next=NULL;
	tail->next=temp;
	tail=tail->next;
	
}
void insert_position(int pos , int val)
{
	node * temp = new node;
	node * current = new node;
	node * previous = new node;
	current = head;
	for(int i = 1 ; i<pos ; i++)
	{
		previous = current;
		current = current->next;
	}
	temp->data=val;
	previous->next=temp;
	temp->next=current;
}
void display (node* t1)
{
	t1 = head;
	while(t1 != NULL)
	{
		cout<<t1->data<<" ";
		t1=t1->next;
	}
 } 
 void delete_first()
 {
 	node * temp = new node;
 	temp=head;
 	head=head->next;
 	delete temp;
 }
 void delete_last()
 {
 	node *current = new node;
 	node *previous = new node;
 	current=head;
 	while(current->next!=NULL)
 	{
 		previous=current;
 		current=current->next;
	 }
	 tail=previous;
	 previous->next=NULL;
	 delete current;
 }
 void delete_position(int pos)
 {
 	node * current = new node;
 	node * previous = new node;
 	current=head;
 	for(int i=1 ; i<pos ; i++)
 	{
 		previous=current;
 		current=current->next;
	 }
	 previous->next=current->next;
	 delete current;
	 
 }
 int main()
 {
 	node* n1;
 	create_node(10);
	create_node(20);
	create_node(30);
	insert_start(5);
	insert_after(40);
	insert_position(2,7);
	delete_first();
	delete_last();
	delete_position(3);
 	display(n1);
 }


For learning, implementation click HERE