Data structure & Algorithms

Link list is a linear data structure. Unlike array link list elements or node is not stored in contiguous memory location.

1: What is a Link List?

Link list is linear data structure which node or elements are stored at different memory location. Two nodes of link list is connected with each other by a reference

In above image you can identify two type of variables i.e. first type of variable to store the data & second type of variable to is a pointer to store the next or previous node of link list.There are various type of link list i.e. single link list , doubly link list , circular link list. This section page describes about single link list.

2: How to declare and define a node of Link List

Let us learn this with example : i.e.
a: define a node of link list that can store an integer value

``````
{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

``````

3: Insert an element at beginning of Link List

This section provides code to do how to insert an element at beginning of an link list
Problem statement:
- allocate memory for a node of link list.
- Insert newly created node at beginning of link list.
A. Solution Steps:
- Create new node say 'A'
- Fill data in node 'A'
- Assign head node to next element of node 'A'.
- assign node 'A' to head

``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

{

}

void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert at Beginning";
cout<<"\n2: Print Link List";
cout<<"\n3: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
}
}
else if(index == 2)
{
display();
}
} while(index != 3);

return 0;
}
``````

4: Insert an element/node as a last node of link list

This insertion section describes how to insert an element as a last node of link list. This will explain 2 possible solution
Problem statement:
- Insert an element/node as end of link list.
A1. Solution steps: This is by traversing in link list from head node
- Hold head node in a temporary node
- traverse to next node utill next->next node is not null
- Assign the given node to next->next node
B1. Code is below

``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

{
else
{
while(tmp_node->next != NULL)
{
tmp_node = tmp_node->next;
}
tmp_node->next = node;
}
}
void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert at last";
cout<<"\n2: Print Link List";
cout<<"\n3: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
}
}
else if(index == 2)
{
display();
}
} while(index != 3);

return 0;
}

```
```
A2. Solution steps: Tis solution is by creating additional variable tail of link list
- Create pointer variable of type LinkList & name is tail
- Assign new node to tail next node
- Assign tail to tail next node
B2. Code is below
``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

LinkList *tail = NULL;
{

{
}

else
{
tail->next = node;
tail = tail->next;
}
}
void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert at last";
cout<<"\n2: Print Link List";
cout<<"\n3: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
}
}
else if(index == 2)
{
display();
}
} while(index != 3);

return 0;
}

``````

5: Insert an element in link list before an existing element

This section explains & provide code to how to insert an element in link list before an existing element in link List.
Problem statement:
- Insert an element at before an given element present in link list.
- if element if not present insert as last element of link list.
A. Solution Steps
- Before searching element hold previous element in pointer variable.
- Move to next node to search
- Do this until found
- If found insert to previous node next
- This step is left for you to understand, you can see the code below to understand also
B. See below the complete Code: Run below code & test on your pc

``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>

using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

LinkList *tail = NULL;
{

{
}
else
{
tail->next = node;
tail = tail->next;
}
}
{
else
{
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
if(tmpNode->data == data_to_find)
{
{
}
else
{
prev->next = node;
node->next = tmpNode;

}
}
else
{
}
}
}
void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert before a number";
cout<<"\n2: Print Link List";
cout<<"\n3: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
int data_to_find;
cout<<"\nEnter Data to Find: ";
cin>>data_to_find;
}
}
else if(index == 2)
{
display();
}
} while(index != 3);

return 0;
}

``````

6. Insert an element in link list after an element

This section is to explain how to insert an element in link list after an existing element of a list.
Problem statement:
- Insert an element after an given element present in link list.
- if element if not present insert as last element of link list.
A. Solution Steps
- Put head node in temporary node
- Move to next node to search
- Do this until found given element or data
- If found insert node to next node
B. See below the complete Code run to see result

``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

LinkList *tail = NULL;
{

{
}
else
{
tail->next = node;
tail = tail->next;
}
}

{
{
return;
}
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
tmpNode = tmpNode->next;
node->next =tmpNode->next;
tmpNode->next = node;
}
void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert after an element";
cout<<"\n2: Print Link List";
cout<<"\n3: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
int data_to_find;
cout<<"\nEnter Data to Find: ";
cin>>data_to_find;
}
}
else if(index == 2)
{
display();
}
} while(index != 3);

return 0;
}

``````

7. Delete an element in link list from beginning

Deletion of an element is another important operation. In this section we will describe how to delete an element or node from beginning in link list
Problem statement:
- Delete an element from beginning in link list.
A. Solution Steps
- Put next node from head to some temporary pointer variable
- delete head node.
- Assign temporary node to head of link list.
B. See below the complete Code

``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

LinkList *tail = NULL;
{

{
}
else
{
tail->next = node;
tail = tail->next;
}
}
{
else
{
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
if(tmpNode->data == data_to_find)
{
{
}
else
{
prev->next = node;
node->next = tmpNode;

}
}
else
{
}
}
}
{
{
return;
}
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
tmpNode = tmpNode->next;
node->next =tmpNode->next;
tmpNode->next = node;
}

{
return;
}

void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert after an element";
cout<<"\n2: Delete from beginning";
cout<<"\n3: Print Link List";
cout<<"\n4: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
int data_to_find;
cout<<"\nEnter Data to Find: ";
cin>>data_to_find;
}
}
else if(index == 2)
{
}
else if(index == 3)
{
display();
}
} while(index != 4);

return 0;
}

``````

8. Delete last node of link list

This section describe how to delete last element//node of link list
Problem statement:
- Delete last node of link list.
A. Solution Steps
- Check if head of link list NULL -> do nothing & return
- if head is not NULL but head->next is NULL delete head & return
- if above 2 statement is false then do following
- create 2 pointer variable i.e. prev & tmpNode of link list type & assign the head to both
- traverse in list while tmpNode->next is not null & keep assign prev to tmpNode
- Assign tail to prev & delete the tmpNode

``````
{
return;
{
tail = NULL;
}
while(tmpNode->next != NULL)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
tail = prev;
tail->next = NULL;
free(tmpNode);
}

``````
B. See below the complete Code
``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

LinkList *tail = NULL;

{
{
return;
}
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
tmpNode = tmpNode->next;
node->next =tmpNode->next;
tmpNode->next = node;
}

{
return;
{
tail = NULL;
}

while(tmpNode->next != NULL)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
tail = prev;
tail->next = NULL;
free(tmpNode);
}

void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert after an element";
cout<<"\n2: Delete from last";
cout<<"\n3: Print Link List";
cout<<"\n4: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
int data_to_find;
cout<<"\nEnter Data to Find: ";
cin>>data_to_find;
}
}
else if(index == 2)
{
}
else if(index == 3)
{
display();
}
} while(index != 4);

return 0;
}

``````

9. Delete an element in link list after an element

This section describe how to delete an element after any element
Problem statement:
- Delete an element from array that exist after given number.
- e.g. given an array of 5 element 1 ,2,3,4,5 delete an element after 3 i.e. 4
A. Solution Steps
- If head of link list is NULL return.

``````
return;
``````
- Traverse in link list until found the data or end of list
``````
while(tmpNode != NULL && tmpNode->data != data)
{
tmpNode = tmpNode->next;
}
``````
- if tmpNode is not NULL put tmpNode->next in tmp
- assign tempNode->next to tmpNode->next->next
- delete tmp node
``````
if(tmpNode != NULL)
{
LinkList *tmp = tmpNode->next;
if(tmp)
{
tmpNode->next = tmp->next;
if(tmp == tail)
tail = tmpNode;
free(tmp);
}
}							   ``````
- let us put all together
``````
{
return;

while(tmpNode != NULL && tmpNode->data != data)
{
tmpNode = tmpNode->next;
}
if(tmpNode != NULL)
{
LinkList *tmp = tmpNode->next;
if(tmp)
{
tmpNode->next = tmp->next;
if(tmp == tail)
tail = tmpNode;
free(tmp);
}
}
}

``````
B. See below the complete Code
``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

LinkList *tail = NULL;
{

{
}
else
{
tail->next = node;
tail = tail->next;
}
}
{
else
{
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
if(tmpNode->data == data_to_find)
{
{
}
else
{
prev->next = node;
node->next = tmpNode;

}
}
else
{
}
}
}
{
{
return;
}
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
tmpNode = tmpNode->next;
node->next =tmpNode->next;
tmpNode->next = node;
}

{
return;
}

{
return;
{
tail = NULL;
}
while(tmpNode->next != NULL)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
tail = prev;
tail->next = NULL;
free(tmpNode);
}
{
return;

while(tmpNode != NULL && tmpNode->data != data)
{
tmpNode = tmpNode->next;
}
if(tmpNode != NULL)
{
LinkList *tmp = tmpNode->next;
if(tmp)
{
tmpNode->next = tmp->next;
if(tmp == tail)
tail = tmpNode;
free(tmp);
}
}
}

void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert after an element";
cout<<"\n2: Delete after an element";
cout<<"\n3: Print Link List";
cout<<"\n4: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
int data_to_find;
cout<<"\nEnter Data to Find: ";
cin>>data_to_find;
}
}
else if(index == 2)
{
int data;
cout<<"Enter data:";
cin>>data;
}
else if(index == 3)
{
display();
}
} while(index != 4);

return 0;
}

``````

10. All link list operation as single program

this section provides the single program to do following operation in link list
list of operation & index:

``````

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert at beginning";
cout<<"\n2: Insert at last";
cout<<"\n3: Insert before an element";
cout<<"\n4: Insert after an element";
cout<<"\n5: Delete from beginning";
cout<<"\n6: Delete from last";
cout<<"\n7: Delete after an element";
cout<<"\n8: Print Link List";
cout<<"\n9: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

``````
``````
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

{
int data;
struct _SingleLinkList *next;// pointer variable to store address next element of linklist

LinkList *tail = NULL;

{

}

{
else
{
while(tmp_node->next != NULL)
{
tmp_node = tmp_node->next;
}
tmp_node->next = node;
}
}
{
else
{
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
if(tmpNode->data == data_to_find)
{
{
}
else
{
prev->next = node;
node->next = tmpNode;

}
}
else
{
}
}
}
{
{
return;
}
while(tmpNode->next != NULL && tmpNode->data != data_to_find)
tmpNode = tmpNode->next;
node->next =tmpNode->next;
tmpNode->next = node;
}

{
return;
}

{
return;
{
tail = NULL;
}
while(tmpNode->next != NULL)
{
prev = tmpNode;
tmpNode = tmpNode->next;
}
tail = prev;
tail->next = NULL;
free(tmpNode);
}
{
return;

while(tmpNode != NULL && tmpNode->data != data)
{
tmpNode = tmpNode->next;
}
if(tmpNode != NULL)
{
LinkList *tmp = tmpNode->next;
if(tmp)
{
tmpNode->next = tmp->next;
if(tmp == tail)
tail = tmpNode;
free(tmp);
}
}
}

void display()
{
int index =1;
cout<<"\ndata in link list present is : \n";
while(node != NULL)
{
cout<data<<" " ;
node = node->next;
index++;
}
}

{
int index = 0;
cout<<"\n==============================\n";
cout<<"\n1: Insert at beginning";
cout<<"\n2: Insert at last";
cout<<"\n3: Insert before an element";
cout<<"\n4: Insert after an element";
cout<<"\n5: Delete from beginning";
cout<<"\n6: Delete from last";
cout<<"\n7: Delete after an element";
cout<<"\n8: Print Link List";
cout<<"\n9: Exit";
cout<<"\n==============================\n";
cout<<"\nEnter Your Input: ";
cin>>index;
return index;
}

int main()
{
int index = 0;
do{

if(index == 1)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
}
}
else if(index == 2)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
}
}
else if(index == 3)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
int data_to_find;
cout<<"\nEnter Data to Find: ";
cin>>data_to_find;
}
}
else if(index == 4)
{
if(node != NULL)
{
cout<<"\nEnter name : ";
cin>>node->data;
node->next = NULL;
int data_to_find;
cout<<"\nEnter Data to Find: ";
cin>>data_to_find;
}
}
else if(index == 5)
{
}
else if(index == 6)
{
}
else if(index == 7)
{
int data;
cout<<"Enter data:";
cin>>data;