National Textile University

Department of Computer
Science
Subject:
DSA
Submitted to:
Sir ARSAL
Submitted by:
Maha Ather

Reg number:
23-NTU-CS-1170
Lab no.:
3
 Semester:3
Exercise 1:
Code:

class node{
private:
int data; //data
node* next; //pointer which points to next node
public:
//set data
void setdata(int data){
this->data=data;
}
//set next
void setnext(node* next){
this->next=next;
}
//get data
int getdata(){
return data;
}
//get next
node* getnext(){
return next;
}
};
list class:
class list{
private:
node* first;
node* last;
public:
list(){
first=nullptr;
last=nullptr;
}

Exercise -2:
1. Insert at start:
Code:
void insertATFirst(int value){
node* newnode=new node();
newnode->setdata(value);
if(first==NULL){
first=newnode;
last=newnode;
}else{
newnode->setnext(first);
first=newnode;
}
}
2. Insert at end
Code:
void InsertATEnd(int value){
node* newnode=new node();
newnode->setdata(value);
if(first==NULL){
first=newnode;
last=newnode;
}else{
 last->setnext(newnode);
last=newnode;
}
}
3. Insert at middle
Code:
void InsertATMiddle(int value){
node* newnode=new node();
newnode->setdata(value);
newnode->setnext(nullptr);
//check if list is empty
if(first==NULL){
first=newnode;
last=newnode;
}
//count node to check middle
int count=0;
node* temp=first;
while(temp!=0){
temp=temp->getnext();
count++;
}
//find middle
int middle=count/2;
//traverse list
temp=first;
for(int i=0;i<middle-1;i++){
temp=temp->getnext();
}
//insert newnode at middle
newnode->setnext(temp->getnext());
temp->setnext(newnode);
}

4. Delete:
Code:
 void deletelist(int value){
if(first==NULL){
cout<<"list is empty"<<endl;
}
node* temp=first;
node* prev=NULL;
if(temp->getdata()==value){
first=first->getnext();
if(first==NULL)
last=NULL;
delete temp;
}
else{
temp=temp->getnext();
}
//specific node
if(temp!=NULL && temp->getdata()!=value){
prev=temp;
temp=temp->getnext();
}
//value not found
if(temp==NULL){
cout<<"value not found"<<endl;
}
prev->setnext(temp->getnext());
//delete at end
if(temp==last){
last=prev;
delete temp;
}
}
5. Addbetween:
Code:
void addbetween(int val1, int val2, int newdata) {
if (first == NULL) {
cout << "List is empty. Cannot insert." << endl;
return;
}

node* temp = first;

node* prev = NULL;
 // Find val1
while (temp != NULL && temp->getdata() != val1) {
prev = temp;
temp = temp->getnext();
}

// val1 not found

if (temp == NULL) {
cout << "Value " << val1 << " not found." << endl;
return;
}

// Find val2 after val1

node* temp2 = temp->getnext();
while (temp2 != NULL && temp2->getdata() != val2) {
temp2 = temp2->getnext();
}

// val2 not found after val1

if (temp2 == NULL) {
cout << "Value " << val2 << " not found after " << val1 << "."
<< endl;
return;
}

// Insert new node between val1 and val2

node* newNode = new node;
newNode->setdata(newdata);
newNode->setnext(temp2);
temp->setnext(newNode);
}
// Insert into sorted list
void insertSorted(int value) {
node* newNode = new node;
newNode->setdata(value);

// List is empty or value is smaller than first node

if (first == NULL || value <= first->getdata()) {
newNode->setnext(first);
first = newNode;
if (last == NULL) {
last = newNode;
 }
return;
}

// Traverse list to find correct position

node* temp = first;
while (temp->getnext() != NULL && temp->getnext()->getdata()
< value) {
temp = temp->getnext();
}

// Insert newNode
newNode->setnext(temp->getnext());
temp->setnext(newNode);

// Update last node if necessary

if (newNode->getnext() == NULL) {
last = newNode;
}
}

Exercise-4:
1) Finding Minimum
Code:
int min(){
if(first==NULL){
cout<<"list is empty"<<endl;
}
node* temp=first->getnext();
int min=first->getdata();
while(temp!=0){
if(temp->getdata()<min){
min=temp->getdata();
}
temp=temp->getnext();
}
return min;
}
2) Finding Maximum
 Code:
int maxno(){
if(first==NULL){
cout<<"list is empty"<<endl;
return -1;
}
int max=first->getdata();
node* temp=first->getnext();
while(temp!=NULL){
if(temp->getdata()>max){
max=temp->getdata();
}
temp=temp->getnext();
}
return max;

}
3) Searching
Code:
int search(int key){
if(first==NULL){
cout<<"list is empty"<<endl;
}
node* temp=first;
while(temp!=NULL){
if(key==temp->getdata()){
cout<<"element found"<<endl;
return key;
break;
}
else{
temp=temp->getnext();
}
}
cout<<"elemet not found"<<endl;
}
 4) Inserting Item at desired location (take location
from user)
Code:
void InsertAtLocation(int value,int location){
node* newnode=new node();
newnode->setdata(value);
newnode->setnext(nullptr);
//check if null
if(first==NULL){
first=newnode;
last=newnode;
}
//count list
int count=0;
node* temp=first;
while(temp!=0){
temp=temp->getnext();
count++;
}
//invalid location
if(location>count){
cout<<"invalid location"<<endl;
}
//at start
if(location==0){
newnode->setnext(first);
first=newnode;
}
//at end
if(location==count){
last->setnext(newnode);
last=newnode;
}
//at specific location
temp=first;
for(int i=0;i<location-1;i++){
temp=temp->getnext();
}
//insert
newnode->setnext(temp->getnext());
temp->setnext(newnode);
}

5) Swapping two elements in the linked list

Code:
void swapnode(int key1,int key2){
node* node1=NULL;
node* node2=NULL;
if(key1==key2){
cout<<"both key are same no need to sort"<<endl;
}
node* temp=first;
while(temp!=0){
if(temp->getdata()==key1){
node1=temp;
}
temp=temp->getnext();
}
temp=first;
while(temp!=0){
if(temp->getdata()==key2){
node2=temp;
}
temp=temp->getnext();
}
int swap=node1->getdata();
node1->setdata(node2->getdata());
node2->setdata(swap);
}
6) Inserting an element in sorted list g. Sorting the
list
Code:
void insertSorted(int value) {
node* newNode = new node;
newNode->setdata(value);

// List is empty or value is smaller than first node

if (first == NULL || value <= first->getdata()) {
newNode->setnext(first);
first = newNode;
if (last == NULL) {
last = newNode;
}
return;
}

// Traverse list to find correct position

node* temp = first;
while (temp->getnext() != NULL && temp->getnext()-
>getdata() < value) {
temp = temp->getnext();
}

// Insert newNode
newNode->setnext(temp->getnext());
temp->setnext(newNode);

// Update last node if necessary

if (newNode->getnext() == NULL) {
last = newNode;
}
}
7) Display:
Code:
void display(){
if(first==NULL){
cout<<"given linked list is empty"<<endl;
}
node* temp=first;
while(temp!=0){
cout<<temp->getdata()<<"->";
temp=temp->getnext();
}
 cout<<"NULL";
}
Exercise-3:
Display in main:
Code:
int main(){
list* newlist=new list();
//display list
newlist->insertATFirst(12);
newlist->insertATFirst(67);
newlist->insertATFirst(14);
newlist->insertATFirst(78);
newlist->InsertATEnd(57);
newlist->InsertATEnd(92);
newlist->InsertATEnd(46);
newlist->InsertATEnd(16);
newlist->InsertATMiddle(83);
newlist->InsertATMiddle(29);
newlist->InsertATMiddle(22);
newlist->InsertATMiddle(74);
newlist->display();
//search in linked list
cout<<endl;
int key;
cout<<"enter key to serach in list: "<<endl;
cin>>key;
int result=newlist->search(key);
cout<<result<<endl;
//insert at specific location
int value;
int location;
cout<<"enter value to insert"<<endl;
cin>>value;
cout<<"enter location to insert: "<<endl;
cin>>location;
newlist->InsertAtLocation(value,location);
newlist->display();
cout<<endl;
//delete
newlist->deletelist(78);
newlist->deletelist(22);
newlist->deletelist(83);
newlist->deletelist(57);
cout<<"list after first node deletion"<<endl;
newlist->display();
cout<<endl;
//max number
cout<<endl;
int max=newlist->maxno();
cout<<"max number is: "<<max<<endl;
//min num
cout<<endl;
int min=newlist->min();
cout<<"min number is: "<<min<<endl;
//sort list
cout<<endl;
newlist->sortlist();
cout<<"sorted list is: "<<endl;
newlist->display();
cout<<endl;
//insert in sorted array
cout<<"list after inserting into sorted array"<<endl;
newlist->insertSorted(55);
newlist->display();
cout<<endl;
//swap two nodes
cout<<endl;
int key1,key2;
cout<<"enter number 1: "<<endl;
cin>>key1;
cout<<"enter number 2: "<<endl;
cin>>key2;
newlist->swapnode(key1,key2);
newlist->display();
cout<<endl;
//insert between nodes
cout<<"list after add between function"<<endl;
newlist->addbetween(57,92,71);
newlist->display();
return 0;
}
Whole code of assignment:
#include<iostream>
using namespace std;
class node{
private:
int data; //data
node* next; //pointer which points to next node
public:
//set data
void setdata(int data){
this->data=data;
}
//set next
void setnext(node* next){
this->next=next;
}
//get data
int getdata(){
return data;
}
//get next
node* getnext(){
return next;
}

};
class list{
private:
node* first;
node* last;
public:
list(){
first=nullptr;
last=nullptr;
}
void insertATFirst(int value){
node* newnode=new node();
newnode->setdata(value);
if(first==NULL){
first=newnode;
last=newnode;
}else{
newnode->setnext(first);
first=newnode;
}
}
void InsertATEnd(int value){
node* newnode=new node();
newnode->setdata(value);
if(first==NULL){
first=newnode;
last=newnode;
}else{
last->setnext(newnode);
last=newnode;
}
}
void InsertATMiddle(int value){
node* newnode=new node();
newnode->setdata(value);
newnode->setnext(nullptr);
//check if list is empty
if(first==NULL){
first=newnode;
last=newnode;
}
//count node to check middle
int count=0;
node* temp=first;
while(temp!=0){
temp=temp->getnext();
count++;
}
//find middle
int middle=count/2;
//traverse list
temp=first;
for(int i=0;i<middle-1;i++){
temp=temp->getnext();
}
//insert newnode at middle
newnode->setnext(temp->getnext());
temp->setnext(newnode);
}
void InsertAtLocation(int value,int location){
node* newnode=new node();
newnode->setdata(value);
newnode->setnext(nullptr);
//check if null
if(first==NULL){
first=newnode;
last=newnode;
}
//count list
int count=0;
node* temp=first;
while(temp!=0){
temp=temp->getnext();
count++;
}
//invalid location
if(location>count){
cout<<"invalid location"<<endl;
}
//at start
if(location==0){
newnode->setnext(first);
first=newnode;
}
//at end
if(location==count){
last->setnext(newnode);
last=newnode;
}
//at specific location
temp=first;
for(int i=0;i<location-1;i++){
temp=temp->getnext();
}
//insert
newnode->setnext(temp->getnext());
temp->setnext(newnode);
}
void deletelist(int value){
if(first==NULL){
cout<<"list is empty"<<endl;
}
node* temp=first;
node* prev=NULL;
if(temp->getdata()==value){
first=first->getnext();
if(first==NULL)
last=NULL;
delete temp;
}
else{
temp=temp->getnext();
}
//specific node
if(temp!=NULL && temp->getdata()!=value){
prev=temp;
temp=temp->getnext();
}
//value not found
if(temp==NULL){
cout<<"value not found"<<endl;
}
prev->setnext(temp->getnext());
//delete at end
if(temp==last){
last=prev;
delete temp;
}

}
int search(int key){
if(first==NULL){
cout<<"list is empty"<<endl;
}
node* temp=first;

while(temp!=NULL){
if(key==temp->getdata()){
cout<<"element found"<<endl;
return key;
break;
}
else{
temp=temp->getnext();
}
}
cout<<"elemet not found"<<endl;
}
int maxno(){
if(first==NULL){
cout<<"list is empty"<<endl;
return -1;
}
int max=first->getdata();
node* temp=first->getnext();
while(temp!=NULL){
if(temp->getdata()>max){
max=temp->getdata();
}
temp=temp->getnext();
}
return max;

}
int min(){
if(first==NULL){
cout<<"list is empty"<<endl;
}
node* temp=first->getnext();
int min=first->getdata();
while(temp!=0){
if(temp->getdata()<min){
min=temp->getdata();
}
temp=temp->getnext();
}
return min;
}
//bubble sort
void sortlist(){
if(first==NULL){
cout<<"linked list is empty no need to sort"<<endl;
}
node* temp=first;
while(temp!=0){
node* currentnode=temp->getnext();
while(currentnode!=0){
if(currentnode->getdata()<temp->getdata()){
int swap = temp->getdata();
temp->setdata(currentnode->getdata());
currentnode->setdata(swap);
}
currentnode=currentnode->getnext();
}
temp=temp->getnext();
}
}
//swap two nodes
void swapnode(int key1,int key2){
node* node1=NULL;
node* node2=NULL;
if(key1==key2){
cout<<"both key are same no need to sort"<<endl;
}
node* temp=first;
while(temp!=0){
if(temp->getdata()==key1){
node1=temp;
}
temp=temp->getnext();
}
temp=first;
while(temp!=0){
if(temp->getdata()==key2){
node2=temp;
}
temp=temp->getnext();
}
int swap=node1->getdata();
node1->setdata(node2->getdata());
node2->setdata(swap);
}
//add between
void addbetween(int val1, int val2, int newdata) {
if (first == NULL) {
cout << "List is empty. Cannot insert." << endl;
return;
}

node* temp = first;

node* prev = NULL;

// Find val1
while (temp != NULL && temp->getdata() != val1) {
prev = temp;
temp = temp->getnext();
}

// val1 not found

if (temp == NULL) {
cout << "Value " << val1 << " not found." << endl;
return;
}
// Find val2 after val1
node* temp2 = temp->getnext();
while (temp2 != NULL && temp2->getdata() != val2) {
temp2 = temp2->getnext();
}

// val2 not found after val1

if (temp2 == NULL) {
cout << "Value " << val2 << " not found after " << val1 << "."
<< endl;
return;
}

// Insert new node between val1 and val2

node* newNode = new node;
newNode->setdata(newdata);
newNode->setnext(temp2);
temp->setnext(newNode);
}
// Insert into sorted list
void insertSorted(int value) {
node* newNode = new node;
newNode->setdata(value);
// List is empty or value is smaller than first node
if (first == NULL || value <= first->getdata()) {
newNode->setnext(first);
first = newNode;
if (last == NULL) {
last = newNode;
}
return;
}

// Traverse list to find correct position

node* temp = first;
while (temp->getnext() != NULL && temp->getnext()->getdata()
< value) {
temp = temp->getnext();
}

// Insert newNode
newNode->setnext(temp->getnext());
temp->setnext(newNode);

// Update last node if necessary

if (newNode->getnext() == NULL) {
last = newNode;
}
}
void display(){
if(first==NULL){
cout<<"given linked list is empty"<<endl;
}
node* temp=first;
while(temp!=0){
cout<<temp->getdata()<<"->";
temp=temp->getnext();
}
cout<<"NULL";
}
};
int main(){
list* newlist=new list();
//display list
newlist->insertATFirst(12);
newlist->insertATFirst(67);
newlist->insertATFirst(14);
newlist->insertATFirst(78);
newlist->InsertATEnd(57);
newlist->InsertATEnd(92);
newlist->InsertATEnd(46);
newlist->InsertATEnd(16);
newlist->InsertATMiddle(83);
newlist->InsertATMiddle(29);
newlist->InsertATMiddle(22);
newlist->InsertATMiddle(74);
newlist->display();
//search in linked list
cout<<endl;
int key;
cout<<"enter key to serach in list: "<<endl;
cin>>key;
int result=newlist->search(key);
cout<<result<<endl;
//insert at specific location
int value;
int location;
cout<<"enter value to insert"<<endl;
cin>>value;
cout<<"enter location to insert: "<<endl;
cin>>location;
newlist->InsertAtLocation(value,location);
newlist->display();
cout<<endl;
//delete
newlist->deletelist(78);
newlist->deletelist(22);
newlist->deletelist(83);
newlist->deletelist(57);
cout<<"list after first node deletion"<<endl;
newlist->display();
cout<<endl;
//max number
cout<<endl;
int max=newlist->maxno();
cout<<"max number is: "<<max<<endl;
//min num
cout<<endl;
int min=newlist->min();
cout<<"min number is: "<<min<<endl;
//sort list
cout<<endl;
newlist->sortlist();
cout<<"sorted list is: "<<endl;
newlist->display();
cout<<endl;
//insert in sorted array
cout<<"list after inserting into sorted array"<<endl;
newlist->insertSorted(55);
newlist->display();
cout<<endl;
//swap two nodes
cout<<endl;
int key1,key2;
cout<<"enter number 1: "<<endl;
cin>>key1;
cout<<"enter number 2: "<<endl;
cin>>key2;
newlist->swapnode(key1,key2);
newlist->display();
cout<<endl;
//insert between nodes
cout<<"list after add between function"<<endl;
newlist->addbetween(57,92,71);
newlist->display();
return 0;
}
Output of all whole assignment: