Concept: A linked list is a sequence of data structures, which are connected together via links Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.
Following are the important terms to understand the concept of Linked List.
• Link − each link of a linked list can store a data called an element.
• Next − each link of a linked list contains a link to the next link called Next.
• Linked List − A Linked List contains the connection link to the first link called First. Linked list can be visualized as a chain of nodes, where every node points to the next node.
• Linked List contains a link element called first.
• Each link carries a data field(s) and a link field called next.
• Each link is linked with its next link using its next link.
• Last link carries a link as null to mark the end of the list.
Types of Linked List
Following are the various types of linked list.
• Simple Linked List − Item navigation is forward only.
• Doubly Linked List − Items can be navigated forward and backward.
• Circular Linked List − Last item contains link of the first element as next and
the first element has a link to the last element as previous.
Basic Operations
Following are the basic operations supported by a list.
• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.
#include<iostream.h>
#include<conio.h>
#include<lib.h>
#define TRUE 1
#define FALSE 0
class sll
{
private: struct node
{
int data;
struct node *next;
}
*head;
public: sll();
void create();
void display();
void search(int key);
void insert_head();
void insert_after();
void insert_last();
void dele();
~sll();
};
sll::sll()
{
head=NULL;
}
sll::~sll()
{
node *temp,*temp1;
temp=head->next;
delete head;
while(temp!=NULL)
{
temp1=temp->next;
delete temp;
temp=temp1;
}
}
void sll::create()
{
node *temp,*New;
int val,flag;
char ans='y';
flag=TRUE;
do
{
cout<<"\n\nEnter the data:";
cin>>val;
New=new node;
if(New==NULL)
cout<<"unable to allocate memory\n";
New->data=val;
New->next=NULL;
if(flag==TRUE)
//executed only for the first time
{
head=New;
temp=head;
flag=FALSE;
}
else
{
temp->next=New;
temp=New;
}
cout<<"\n do you want to enter more elements?(y/n)";
ans=getch();
}
while(ans=='y'||ans=='Y');
cout<<"\n the singly linked list is created\n";
getch();
}
void sll::display()
{
node *temp; temp=head;
if(temp==NULL)
{
cout<<"\n the list is empty\n";
getch();
clrscr();
return;
}
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
getch();
}
void sll::search(int key)
{
node *temp;
int found;
temp=head;
if(temp==NULL)
{
cout<<"linked list is empty\n";
getch();
clrscr();
}
found=FALSE;
while(temp!=NULL&&found==FALSE)
{
if(temp->data!=key)
temp=temp->next;
else
found=TRUE;
}
if(found==TRUE)
{
cout<<"\n the element is present in the list\n";
getch();
}
else
{
cout<<"\nThe element is not present in the list\n";
getch();
}
}
void sll::dele()
{
node *temp,*prev;
int key;
temp=head;
cout<<"\n Enter the data of the node you want to delete: ";
cin>>key;
while(temp!=NULL)
{
if (temp->data==key)
//traverse till required node to delete break;
//is found
prev=temp;
temp=temp->next;
}
if(temp==NULL)
cout<<"\n node not found";
else
{
if(temp==head)
//first node
head=temp->next;
else
prev->next=temp->next;
//intermediate or end node
delete temp;
cout<<"\n the element is deleted\n";
}
getch();
}
void sll::insert_last()
{
node *New,*temp;
cout<<"\n Enter the element which you want to insert: ";
cin>>New->data;
if(head==NULL)
head=New;
else
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=New;
New->next=NULL;
}
}
void sll::insert_after()
{
int key;
node *temp,*New;
New=new node;
cout<<"\n Enter the element which you want to insert: ";
cin>>New->data;
if(head==NULL)
{
head=New;
}
else
{
cout<<"\n Enter the element after which you want to insert the node: ";
cin>>key;
temp=head;
do
{
if(temp->data==key)
{
New->next=temp->next;
temp->next=New;
break;
}
else
temp=temp->next;
}
while(temp!=NULL);
}
}
void sll::insert_head()
{
node *New,*temp; New=new node;
cout<<"\n Enter the element which you want to insert: ";
cin>>New->data;
if(head==NULL)
head=New;
else
{
temp=head;
New->next=temp;
head=New;
}
}
void main()
{
sll s;
int choice,val, ch1;
char ans='y';
clrscr();
cout<<"\n\n\tProgram to perform various operations on linked list";
cout<<"\n1.Create";
cout<<"\n2.Display";
cout<<"\n3.Search";
cout<<"\n4.Insert an element in a list";
cout<<"\n5.Delete an element from list";
cout<<"\n6.Quit";
do
{
cout<<"\n\nEnter your choice(1-6): ";
cin>>choice;
switch(choice)
{
case 1: s.create();
break;
case 2:s.display();
break;
case 3:cout<<"enter the element you want to search";
cin>>val;
s.search(val);
break;
case 4: clrscr();
cout<<"\n the list is:\n";
s.display();
cout<<"\n menu";
cout<<"\n1.insert at beginning ";
cout<<"\n2.insert after";
cout<<"\n3.insert at end";
cout<<"\n enter your choice";
cin>>ch1;
switch(ch1)
{
case 1:s.insert_head();
break;
case 2:s.insert_after();
break; case
3:s.insert_last();
break;
default:cout<<"\n invalid choice";
}
break;
case 5:s.dele();
break;
case 6:exit(0);
default:cout<<"\n invalid choice";
}
cout<<"\nDo you want to continue? ";
cin>>ans;
}
while(ans=='y'||ans=='Y');
return;
}
