Linked Lists
A Linked list is a linear data structure, where the linear order is given by means of pointers. Each element of the linked list is known as nodes.
Each node is divided into two parts:
- The first part contains the data of the element.
- The second part contains the address of the next node in the list (next).
Traversing a Linked List in C++
Traversing is the process of displaying all the elements of the linked list. Here, we have traversed the elements of the linked list using functions.
#include <iostream>
using namespace std;
struct node{
int data;
struct node*next;
};
void traversal(struct node*ptr);
int main()
{
struct node*head,*second,*third;
head=new node();
second=new node();
third=new node();
head->data=7;
head->next=second;
second->data=14;
second->next=third;
third->data=21;
third->next=NULL;
node *newnode;
newnode=new node();
traversal(head);
cout<<"\n Insert element:";
cin>>newnode->data;
newnode->next=head;
head=newnode;
traversal(head);
return 0;
}
void traversal(struct node*ptr)
{ while(ptr!=NULL)
{
cout<<ptr->data<<" ";
ptr=ptr->next;
}
}
Algorithm for traversing a Linked List
The variable ptr points to the node currently being processed. The variable head contains the address of the head node of the LIST.void traversal(struct node*ptr)
1.ptr=head (Initialize pointers)
2. Repeat steps 3 and 4 while PTR!= NULL
3. Apply the PROCESS to data[PTR].
4. Set ptr=next[PTR]
5. Exit
Insertion in a Linked List in C++
Insertion is the process of inserting an element in a linked list. In this program, we are inserting elements into the linked list from the end.
Output:
Enter data:56
Do you want to insert another number? (y/n)y
Enter data:23
Do you want to insert another number? (y/n)y
Enter data:96
Do you want to insert another number? (y/n)n
Elements in Linked list: 56 23 96
Insertion into a Linked List in C++
#include<iostream>
using namespace std;
struct node{
int data;
node*next;
};
int main()
{
char ch;
node *head,*newnode,*temp;
head = NULL;
do
{
newnode=new node();
cout<<"\n Enter data:";
cin>>newnode->data;
newnode->next=NULL;
if(head==NULL)
head=temp=newnode;
else
{
temp->next=newnode;
temp=newnode;
}
cout<<"\n Do you want to insert another number? (y/n)";
cin>>ch;
}while(ch=='y');
temp=head;
cout<<"\n Elements in Linked list: ";
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
return 0;
}
Deletion from a Linked List
Deletion is the process of deleting an element from the linked list.
Output:
Elements of linked list: 7 14 21
After Deletion
Elements of linked list:14 21
#include <iostream>
using namespace std;
struct node{
int data;
struct node*next;
};
void traversal(struct node*ptr);
int main()
{
struct node*head,*second,*third;
head=new node();
second=new node();
third=new node();
head->data=7;
head->next=second;
second->data=14;
second->next=third;
third->data=21;
third->next=NULL;
cout<<”\n Elements of linked list:”;
traversal(head);
cout<<"\n After Deletion\n";
cout<<”\n Elements of linked list:”;
struct node*temp;
temp=head;
head=head->next;
free(temp);
traversal(head);
return 0;
}
void traversal(struct node*ptr)
{ while(ptr!=NULL)
{
cout<<ptr->data<<" ";
ptr=ptr->next;
}
}