Is a data structure that makes it easy to rearrange data without having to move data in memory.
A linear collection of specially designed data elements, called nodes, linked to one another by means of pointers.
Parts of node
1. Contains the information of the element (data).
2. Contains the address of the next node in the linked list (next).
Linked list advantages
- Linked list are dynamic data structure. That is, they can grow or shrink during the execution of a program.
- Efficient memory utilization: In linked list (or dynamic)representation, memory is not pre-allocated. Memory is allocated whenever it is required. And it is deallocated (or removed) when it is not needed.
- Insertion and deletion are easier and efficient. Linked list provides flexibility in inserting a data item at a specified position and deletion of a data item from the given position.
- Many complex applications can be easily carried out with linked list.
Linked list disadvantages
- More memory: to store an integer number, a node with integer data and address field is allocated. That is more memory space is needed.
- Access to an arbitrary data item is little bit cumbersome and also time consuming.
Linked List Operations
Creation
Create a linked list. Once a linked list is created with one node, insertion operation can be used to add more elements in a node.
Insertion
Insert a new node at any specified location in the linked list (beginning, end, or specified position between linked list).
Deletion
Delete an item (or node) from the linked list (beginning, end, specified location of the linked list)
Traversing
Process of going through all the nodes from one end to another end of the linked list. In singly linked list we can visit from left to right, forward traversing is nodes only. In doubly linked list forward and backward traversing is possible.
Searching
Search values from the linked list.
Concatenation
Appending the second list to the end of the first list.
Types of linked list
Singly Linked List
Enables a program to move through the list in one direction, which is usually from the front of the list moving to the end of the list.
Linked list sample program
#include <iostream>
using namespace std;
struct node{
int data;
node *next;
};
node *start;
void createList(int d);
void AddBegin(int d);
void display();
int main()
{
start = NULL;
int n,m;
cout << "\n\nHow many nodes you want: ";
cin >> n;
for(int i=0;i<n;i++) {
cout << "\nEnter the element: ";
cin >> m;
createList(m);
}
display();
AddBegin(100);
display();
cin.ignore().get();
return 0;
}
void AddBegin(int d)
{
node *tmp;
tmp = new node;
tmp -> data = d;
tmp -> next = start;
start = tmp;
}
void display()
{
node *q;
if(start==NULL){
cout << "\n\nList is empty";
return;
}
q=start;
cout << "\n\nList is: ";
while(q!=NULL){
cout << q->data << " ";
q=q->next;
}
cout << "\n";
}
void createList(int d)
{
node *q, *tmp;
tmp = new node;
tmp -> data = d;
tmp -> next = NULL;
if(start==NULL) {
start = tmp;
} else {
q = start;
while(q->next!=NULL)
q = q->next;
q->next = tmp;
}
}
Singly Linked List
/*
Program: Singly Linked Queue
*/
#include <iostream>
#include <iomanip>
using namespace std;
struct node{
int data;
node *next;
}*head;
void createlist(int);
void addbegin(int);
void addafter(int,int);
void display();
void del(int);
void delfirstelem();
void count();
void reverse();
void search(int);
int main()
{
while(1)
{
int choice;
system("cls");
cout << "[1] - Create a list\n";
cout << "[2] - Add at the beginning\n";
cout << "[3] - Add after\n";
cout << "[4] - Delete\n";
cout << "[5] - Display\n";
cout << "[6] - Count\n";
cout << "[7] - Reverse\n";
cout << "[8] - Search\n";
cout << "[9] - Exit\n";
cout << "===================\n";
cout << "Enter your choice: ";
cin >> choice;
int n, num, pos;
switch(choice){
case 1:
cout << "\nHow many node you want: ";
cin >> n;
cout << "\nEnter " << n << " element(s)\n";
for(int i=0;i<n;i++)
{
cin >> num;
createlist(num);
}
display();
break;
case 2:
cout << "\nEnter a number (add at beginning)";
cin >> num;
addbegin(num);
display();
break;
case 3:
cout << "\nEnter the value and position of your element: ";
cin >> num >> pos;
addafter(num,pos);
display();
break;
case 4:
cout << "\nEnter the value to be deleted from the list: ";
cin >> num;
del(num);
//cout << "delete first element ";
//delfirstelem();
system("pause>0");
display();
break;
case 5:
display();
break;
case 6:
count();
break;
case 7:
reverse();
display();
break;
case 8:
cout << "\nEnter the value to search: ";
cin >> num;
search(num);
break;
case 9:
exit(1);
default:
cout << "\nWrong choice!\n";
}
cout << endl;
system("pause");
}
return 0;
}
void delfirstelem()
{
node *tmp;
tmp=head;
head=tmp->next;
delete tmp;
}
//creation
void createlist(int n)
{
node *p, *tail;
tail = new node;
tail->data = n;
tail->next = NULL;
if(head==NULL)
head=tail;
else
{
p=head;
while(p->next!=NULL)
p=p->next;
p->next = tail;
}
}
//add begin
void addbegin(int n)
{
node *tmp;
tmp = new node;
tmp->data = n;
tmp->next = head;
head=tmp;
}
//add after
void addafter(int n,int pos)
{
node *tmp, *p;
if(head==NULL)
{
cout << "You have to create first the linked list\n";
return;
}
p=head;
for(int i=0;i<pos-1;i++)
{
p=p->next;
if(p==NULL)
{
cout << "There are less than "<<pos<<" elements";
return;
}
}
tmp = new node;
tmp->next = p ->next;
tmp->data = n;
p->next = tmp;
}
void del(int n)
{
node *tmp,*p;
//delete at the beginning
if(head==NULL)
{
cout << "You have to create first the linked list\n";
return;
}
if(head->data == n)
{
tmp = head;
head = head->next;
delete tmp;
return;
}
p=head;
//delete in between
while(p->next->next!=NULL)
{
if(p->next->data == n)
{
tmp = p->next;
p->next = tmp->next;
delete tmp;
return;
}
p=p->next;
}
if(p->next->data == n)
{
tmp = p->next;
delete tmp;
p->next=NULL;
return;
}
cout << "\nElement " << n << " not found\n";
}
//count
void count()
{
node *p;
p=head;
int cnt=0;
while(p!=NULL)
{
p=p->next;
cnt++;
}
cout << "There are " << cnt <<" elements is the list\n";
}
void reverse()
{
node *p1, *p2, *p3;
//for one element only
if(head->next==NULL)
return;
p1=head;
p2=p1->next;
p3=p2->next;
p2->next=p1;
p1->next=NULL;
while(p3!=NULL)
{
p1=p2;
p2=p3;
p3=p3->next;
p2->next=p1;
}
head=p2;
}
void search(int n)
{
node *p;
p=head;
int pos=1;
while(p!=NULL)
{
if(p->data==n)
{
cout << "The element value "<<n<<" found at position "<< pos;
return;
}
pos++;
p=p->next;
}
cout << "The element value "<<n<<" is not found\n";
}
//display
void display()
{
node *p;
if(head==NULL)
{
cout << "List is empty!\n";
return;
}
p=head;
cout << endl;
cout << setw(20) << "POINTER" << setw(20) << "DATA" << setw(20) << "NEXT" << endl;
while(p!=NULL)
{
cout << setw(20) << p << setw(20) << p->data << setw(20) << p->next << endl;
p = p->next;
}
cout << endl;
}
Doubly Linked list
#include <iostream>
#include <iomanip>
using namespace std;
struct node{
int data;
node *next;
node *prev;
}*start;
//typedef node *NODE;
void display()
{
node *p;
if(start==NULL)
{
cout << "List is empty!\n";
return;
}
p=start;
cout << endl;
cout << setw(10) << "ADDRESS" << setw(15) << "PREV" <<setw(15) << "DATA" << setw(20) << "NEXT" << endl;
while(p!=NULL)
{
cout << setw(10) << p << setw(15) << p->prev <<setw(15) << p->data << setw(20) << p->next << endl;
p = p->next;
}
cout << endl;
}
void createlist(int n)
{
node *p, *end;
end = new node;
end->data = n;
end->next = NULL;
if(start==NULL)
{
end->prev=NULL;
start=end;
}
else
{
p=start;
while(p->next!=NULL)
p=p->next;
p->next = end;
end->prev = p;
}
}
void reverse()
{
node *p1, *p2;
p1=start;
p2=p1->next;
p1->next=NULL;
p1->prev = p2;
while(p2!=NULL)
{
p2->prev=p2->next;
p2->next=p1;
p1=p2;
p2=p2->prev;
}
start=p1;
}
int main()
{
while(1)
{
int choice;
system("clear");
//system("cls");
cout << "[1] - Create a list\n";
cout << "[2] - Display\n";
cout << "[3] - Reverse\n";
cout << "[4] - Exit\n";
cout << "===================\n";
cout << "Enter your choice: ";
cin >> choice;
int n, num, pos;
switch(choice){
case 1:
cout << "\nHow many node you want: ";
cin >> n;
cout << "\nEnter " << n << " element(s)\n";
for(int i=0;i<n;i++)
{
cin >> num;
createlist(num);
}
display();
break;
case 2:
display();
break;
case 3:
reverse();
display();
break;
case 4:
exit(1);
default:
cout << "\nWrong choice!\n";
}
cout << endl;
cin.ignore().get();
system("pause");
}
return 0;
}