BSCE 4th Semester Data Structure & Algorithms
Data Structures and Algorithm
LAB REPORT # 3
Submitted by
Name: Mahnoor Inam
Reg. No. 18-CE-009
Department of Computer Science and Engineering
HITEC University Taxila
Presentation Conclusion/theory Code result Total
/
/Format
Objective/title
Total
5 5 5
obtained
1
BSCE 4th Semester Data Structure & Algorithms
Experiment # 03
Operations on a Single Linked List
Objectives:
The objective of this lab is to understand the various operations on Singly linked list in C++.
Creation of a singly link list
Displaying a link list.
Insertion of nodes in the linked list.
Deletion of nodes from the linked list.
Software Tools:
1. Microsoft Visual Studio/Code Blocks.
Theory:
A Singly-linked list is a collection of nodes linked together in a sequential way where each node of
the singly linked list contains a data field and an address field that contains the reference of the
next node. The nodes are connected to each other in this form where the value of the next variable
of the last node is NULL i.e. next = NULL, which indicates the end of the linked list.
Basic Operations on Linked List
Traversal: To traverse all the nodes one after another.
Insertion: To add a node at the given position.
Deletion: To delete a node.
Searching: To search an element(s) by value.
Updating: To update a node.
Sorting: To arrange nodes in a linked list in a specific order.
Lab Task
1. Run all the above programs and then make the following main menu to perform
different tasks.
2
BSCE 4th Semester Data Structure & Algorithms
Input
#include<iostream>
using namespace std;
struct node{
int x;
node *next;
};
class linklist
{
private:
node *head;
node *tail;
public:
linklist(){
head=NULL;
tail=NULL;
}
void insert_start(int a)
{
node *temp=new node;
temp->x=a;
temp->next=head;
head=temp;
}
void display()
{
node *temp = new node;
temp = head;
while(temp != NULL)
{
3
BSCE 4th Semester Data Structure & Algorithms
cout<<temp->x<<"\t";
temp = temp->next;
}
}
void insert_position(int pos,int a){
node *pre=new node;
node *cur=new node;
node *temp=new node;
cur=head;
for(int i=1;i<pos;i++)
{
pre=cur;
cur=cur->next;
}
temp->x=a;
pre->next=temp;
temp->next=cur;}
void insert_end(int a)
{
node *temp;
temp=head;
while(temp->next!=NULL){
temp=temp->next;
}
temp->x=a;
temp->next=NULL;
}
void delete_first()
{
node*temp=new node;
temp=head;
head=head->next;
delete temp;
}
void delete_last()
{
node*cur=new node;
4
BSCE 4th Semester Data Structure & Algorithms
node *pre=new node;
cur=head;
while(cur->next!=NULL)
{
pre=cur;
cur=cur->next;
}
tail=pre;
pre->next=NULL;
delete cur;
}
void delete_pos(int pos){
node *cur=new node;
node *pre=new node;
cur=head;
for(int i=0;i<pos;i++){
pre=cur;
cur=cur->next;}
pre->next = cur->next;
}
~linklist()
{
node *Ptr;
node *nextNode;
Ptr = head;
while (Ptr != NULL)
{
nextNode = Ptr->next;
delete Ptr;
Ptr = nextNode;
}
cout<<endl<<"link list deleted";
}};
int main(){
linklist jj;
jj.insert_start(3);
jj.insert_start(4);
jj.insert_start(5);
jj.insert_start(6);
5
BSCE 4th Semester Data Structure & Algorithms
cout<<"Insertion at the starting is: ";
jj.display();
jj.insert_position(3,4);
cout<<endl<<"Insertion at the middle is: ";
jj.display();
jj.insert_end(7);
cout<<endl<<"Insertion at the end is: ";
jj.display();
jj.delete_first();
cout<<endl<<"Deletion at the fist is: ";
jj.display();
jj.delete_last();
cout<<endl<<"Deletion at the end is: ";
jj.display();
cout<<endl<<"Deletion at the middle is: ";
jj.delete_pos(1);
jj.display();
return 0;
Output
6
BSCE 4th Semester Data Structure & Algorithms
Conclusion
In this lab report we studied about singly link list and perform different operations on it such as
insertion, deletion and updation.
