DSA ASSIGNMENT 1 MUEED HASSAN

CMS:347391

Yasir Faheem
 DSA ASSIGNMENT 1

Assignment 1: Implement Various Operations of Singly Linked Lists

Data Structures & Algorithms
Section: BSCS-10-A&B Session: Fall-2021
Instructor: Dr. Yasir Faheem Mapped to: CLO-1

start

1 2 3 4 5 6 7 /

1. Implement a function that prints all nodes of a linked list in the reverse order. A call to the
above function should print 7, 6, 5, 4, 3, 2, 1. Note that you are not allowed to copy the
contents of the list in any other structure.
Output:

2. Implement a function which reverses the order of a linked list. If the original list is 1-> 2->3-

1
 DSA ASSIGNMENT 1

>4->5 -> 6, the updated list should be 6 -> 5 -> 4 -> 3 -> 2 ->1. Note that this function should
only change the pointer field in all nodes of a list; you are not allowed to modify data field of
any node.
Output:

3. Implement a function that deletes all those nodes from a linked list which have odd numbered
value in their data part. For instance, if the original list is 1-> 2->3->5->6 -> 7, then, the updated
list should be 2 -> 6.
Note: Include all checks for various input cases like: a) all elements are odd numbers 1->3->5,
b) only the last element is odd numbered 2->4->5, c) the list has only value which is odd e.g.
1, d) both first and last values are odd 1->2->4->5 etc.
Output:

2
 DSA ASSIGNMENT 1

a)

3
 DSA ASSIGNMENT 1

b)

c)

4
 DSA ASSIGNMENT 1

d)

4. Write code of a function which rearranges the linked list by separately grouping nodes having
even numbered and odd numbered value in their data part. If the input list is 1-> 2->3->4->5
-> 6, the updated list may look like 1-> 3 -> 5->2-> 4-> 6 or 2-> 4-> 6 -> 1-> 3 -> 5.

5
 DSA ASSIGNMENT 1

5. Implement a function that rearranges a linked list by separating the odd positioned nodes and
even positioned nodes. Moreover, it should also reverse the sub-list of the even positioned
nodes and then append it at the end of odd positioned nodes sub-list. If the original list is 2-
>4->5->7->8->9 , the updated list should be 2->5->8 ->9->7->4.
Note: Include checks for all possible cases; the length of a list may be any number n >=0.
Output:

Code:

/*
Name: MUEED HASSAN
Copyright: SEECS
Author: MUEED HASSAN
Date: 09/10/21 00:31
Description:ASSIGNMENT 1(Q 1 TO 5)

*/

*//
//this program is combined from q 1 to q 5//

6
 DSA ASSIGNMENT 1

#include<iostream>

using namespace std;

class node//class node declared
{

public:

int data;

node *next;// link to the next node in the list

};
class LinkedList//class linked list declared
{

public:

node *start; // special variable which stores address of the head node.

node *last; // special variable which stores address of the last node.

node *ploc; //to be used by Search(value) method to store address of logical predecessor of
value in a list.

node *loc;//to be used by Search(value) method to store address of the node containing the
searched value in a list. If it is not found it contains NULL. void SLL();

node *sloc;//store successor node in reverese function

int length;

bool isEmpty();//function to check if list is empty or not

void Search(int keyvalue);//function to search a specific value on its position

7
 DSA ASSIGNMENT 1

void insertAtfront(int value);// to insert value at the head node

void insertAtlast(int value);//to insert value at the end node

void insertAtmiddle(int value);//insert value at any position in the list

void PrintList();//print the list

void insertsorted(int value);//enter value at the logical position in the list

void sll();//this create s an empty single link list

void reverse();//reverse the list

void DestroyList();

void printreverse();//donot reverse the list just print it in reverse

void evenselector();//convrt the list into even list outcasting odd

void evenoddlist();//print even numbers than odd

void segerateevenodd();// the list into even odd than print combined list

void segeratereverseevenodd();//print odd numbers with even numbers in descendinng order

in the end
};
void LinkedList::sll()//sll function called from the class
{start=NULL;//all the pointer point to null
last=NULL;
ploc=NULL;
loc=NULL;
}

8
 DSA ASSIGNMENT 1

bool LinkedList::isEmpty() //this creates an empty list

{if(start==NULL)
{
return true;
}
else
return false;
}
void LinkedList::insertAtmiddle(int value)//insert the value in the middle of the list
{
node *newnode = new node();//creation of a memeory space that will be generated at run
time
newnode->data = value;
if (!isEmpty())
{while(loc!=NULL && loc->data<value)//run the list till the end or reguired value is reached or
just passed
{ ploc=loc;
loc=loc->next;
length++;
};
newnode->next=ploc->next;
cout<<newnode<<endl;
ploc->next=newnode;

}
else
start==newnode;
last==newnode;
cout<<"insertion at start succesfull"<<endl;
length++;
}
void LinkedList::insertAtfront(int value)//insert at the front node
{int length=0;
node *newnode = new node();//dynamic memory allocation

9
 DSA ASSIGNMENT 1

newnode->data = value;
if(!isEmpty())
{newnode->next=start;
start = newnode;
cout<<"insertion at start succesfull"<<endl;
}
else
{
start=newnode;
last = newnode;
newnode->next = NULL;
cout<<"insertion at start succesfull"<<endl;
}
length++;
}
void LinkedList::Search(int keyvalue)//search the specific value
{int lenght=0;
if (!isEmpty())
{
loc = start;
ploc = NULL;
while(loc!=NULL && loc->data<keyvalue)//to propagate the list till we are equal to or one
greater than desired value
{ploc=loc;
loc=loc->next;
length++;
};
if(loc!=NULL)
{
if (loc->data != keyvalue)
{
loc=NULL;
cout<<"the searched item is not in the list"<<endl;
}

10
 DSA ASSIGNMENT 1

else
{
cout<<"yes this exist in the list on "<<length<<"number"<<endl;
}
}
else
{cout<<"the searched item is not in the list"<<endl;
}
}
else
{
cout << "list is empty. cannot perform search." << endl;
}
}
void LinkedList::insertAtlast(int keyvalue)//insert at the last node
{
node *newnode = new node();//dynamic aloocation
newnode->data = keyvalue;
if (!isEmpty())
{ last->next=newnode;
last=newnode;
cout<<"insertion at last successfull"<<endl;
}
else
{
start=newnode;
last=newnode;
cout<<"insertion at last succesfull"<<endl;
length++;
}
newnode->next = NULL;
}

void LinkedList::PrintList()//print the list

11
 DSA ASSIGNMENT 1

{cout<<"****list ****"<<endl;
if(!isEmpty())
{ node *temp=start;
while(temp!=NULL)
{
cout<<temp->data<<endl;
temp=temp->next;

};
}else
cout<<"list is empty,nothing to print"<<endl;
}
void LinkedList::printreverse()//print the reverse list not reverse the list
{ cout<<"****reverse list ****"<<endl;
if(!isEmpty())
{ node *temp = last;
while(temp!=NULL)
{
cout<<temp->data<<endl;
loc = start;
ploc = NULL;
while(loc!=temp)
{
ploc=loc;
loc=loc->next;
}
temp = ploc;
};
}
else
cout<<"list is empty,nothing to print"<<endl;
}
void LinkedList::DestroyList()
{

12
 DSA ASSIGNMENT 1

if (!isEmpty()) //Checking if there is any data in the list to delete

{
loc = start; //Initializing traversing pointer to start of the list
ploc = NULL;
while(loc != NULL) //Traversing list until reaching last node
{
ploc = loc;
loc = loc->next;
delete ploc; //Freeing memory allocated to each node sequentially
}
start = last = NULL; //Setting start and last pointers to null to define list as empty
}
}

void LinkedList::reverse()//reverse the list

{
node *preloc=NULL;
node *presentloc=start;
node *nextloc=start;
if(!isEmpty())
{ while(nextloc!=NULL)
{ nextloc=nextloc->next;
presentloc->next=preloc;
preloc = presentloc;
presentloc = nextloc;
};
start=preloc;
PrintList();//print comamand called

}else
cout<<"list is empty,nothing to print"<<endl;

13
 DSA ASSIGNMENT 1

}
void LinkedList::insertsorted(int value)//inert value at the sorted position in the list
{ int lenght=0;

Search(value);//check value is already there or not

if(loc==NULL)
{ if(ploc==NULL)
{
insertAtfront(value);
}
else
{ node *newnode = new node();//dynamic alllocation

newnode->data = value;

newnode->next=ploc->next;

ploc->next=newnode;
if(ploc=last)
{
last=newnode;
}

}
lenght++;
}
else
cout<<"value is duplicated,can not be inserted"<<endl;

void LinkedList::evenselector()//reduce the list to even entries

{ if(!isEmpty())
{

14
 DSA ASSIGNMENT 1

ploc=NULL;
loc=start;
while(loc!=NULL)
{
if((loc->data)%2==0)//mod function used
{
ploc=loc;
loc=loc->next;

}
else
{ if(ploc!=NULL)
{
ploc->next=loc->next;
loc=loc->next;
}
else
{ploc=NULL;
start=loc->next;
loc=loc->next;
}

}
};

if(!isEmpty())
{
cout<<"****even list****"<<endl;
PrintList();

15
 DSA ASSIGNMENT 1

}
else
{ cout<<"****even list****"<<endl;
PrintList();
cout<<"there is no even entry in the list"<<endl;

}
}

}
else
cout<<"list is empty"<<endl;
}

void LinkedList::segerateevenodd()//even odd list together first even than odd

{
node *evenstart=NULL;//new nodes createdS
node *evenlast=NULL;//nodes created
node *oddstart=NULL;
node *oddlast=NULL;
if(!isEmpty())
{
ploc=NULL;
loc=start;
while(loc!=NULL)
{ int value=0;
value=loc->data;
if(value % 2 !=0)//mod function used to seperate odd
{ if(oddstart==NULL)
{ oddstart=loc;
oddlast=oddstart;

16
 DSA ASSIGNMENT 1

}
else
{
oddlast->next=loc;
oddlast=oddlast->next;

}
else
{
if(evenstart==NULL)//this means insertion in an emty list
{
evenstart=loc;
evenlast=evenstart;
}
else
{
evenlast->next=loc;
evenlast=evenlast->next;
}
}
ploc=loc;
loc=loc->next;

};
if(oddstart==NULL && evenstart==NULL)
{
cout<<"list is empty"<<endl;

17
 DSA ASSIGNMENT 1

oddlast->next=evenstart;
evenlast->next=NULL;
start=oddstart;

PrintList();
}

else
cout<<"list is empty"<<endl;
}
void LinkedList::segeratereverseevenodd()//print odd numbers + even numbers in descending
orders
{
node *evenstart=NULL;
node *evenlast=NULL;
node *oddstart=NULL;
node *oddlast=NULL;
if(!isEmpty())
{
ploc=NULL;
loc=start;
while(loc!=NULL)
{ int value=0;
value=loc->data;
if(value % 2 !=0)
{ if(oddstart==NULL)
{ oddstart=loc;
oddlast=oddstart;
}
else
{
oddlast->next=loc;

18
 DSA ASSIGNMENT 1

oddlast=oddlast->next;

}
}
else
{
if(evenstart==NULL)
{
evenstart=loc;
evenlast=evenstart;
}
else
{
evenlast->next=loc;
evenlast=evenlast->next;

}
}

loc=loc->next;

};

if(oddstart==NULL && evenstart==NULL)

{
cout<<"list is empty"<<endl;

}
evenlast=NULL;
reverse();

19
 DSA ASSIGNMENT 1

oddlast->next=evenstart;
start=oddstart;
last=evenlast;

PrintList();
}

}
else
cout<<"list is empty"<<endl;
}

int main()
{int value=0;//initializing variabel
LinkedList list;//object of class declared
int x=0;
cout<<"************MENU*****************"<<endl;
cout<<"THIS PROGRAM CONTAIN ALL THE ANSWER FROM Q 1 TO Q5"<<endl;
while(x!=12)//command regarding the termination og program
{

cout<<"press 1 to create an empty list"<<endl;

cout<<"press 2 to insert value at first node in list"<<endl;
cout<<"press 3 to insert value at last node in list"<<endl;

20
 DSA ASSIGNMENT 1

cout<<"press 4 to insert value at logical sorted node in list"<<endl;

cout<<"press 5 to print list"<<endl;
cout<<"press 6 to print the list in reverse order(Q1)"<<endl;
cout<<"press 7 to print reverse list(Q2)"<<endl;
cout<<"press 8 to print even list(Q3)"<<endl;
cout<<"press 9 to print segerated even and odd list(Q4)"<<endl;
cout<<"press 10 to print segerated reverse even and odd list(Q5)"<<endl;
cout<<"press 11 to destroy list"<<endl;
cout<<"press 12 to exit program"<<endl;

cin>>x;
switch(x)
{ case 1 :
{

list.sll();//linked list created here

break;
}
case 2:
{ cout<<"insert a value need to to entered at the start of the node"<<endl;

cin>>value;

list.insertAtfront(value);

break;
}
case 3:
{ cout<<"insert a value need to to entered at the end of the node"<<endl;
cin>>value;

21
 DSA ASSIGNMENT 1

list.insertAtlast(value);//function called here

break;
}
case 4:
{
cout<<"insert a value need to to entered at the sorted position in the
list"<<endl;

cin>>value;

list.insertsorted(value);//sorted function
break;
}
case 5:

{
list.PrintList();//function print called

break;
}
case 6:

{
list.printreverse();
break;
}
case 7:
{ list.reverse();//reverses the list

break;

22
 DSA ASSIGNMENT 1

case 8:
{ list.evenselector();//function called to print even list

break;

}
case 9:
{
list.segerateevenodd();//function to called even + odd list
}
case 10:
{
list.segeratereverseevenodd();//function to to print
odd+reverse even list
}
case 11:
{ list.DestroyList();//destroy the the list and free the memory
break;
}
}
};

return 0;
}//program ends here
6. Implement a function which takes two values as input from the user and searches them in the
list. If both the values are found, your task is to swap both the nodes in which these values are
found. Note, that you are not supposed to swap values. You are supposed to 1change next
pointer fields in the concerned nodes. Your function should handle all possible cases:
• The two nodes are not adjacent and none of them is the first or the last node.
• The two nodes are not adjacent to each other and one of them is the first/last node.
• Both nodes are adjacent and none of them is the first or the last one.
• Both nodes are adjacent and one of them is the first node.
• Both are adjacent, one is first and the other is last. This is the case in which the length
of a list is two.

23
DSA ASSIGNMENT 1

24
DSA ASSIGNMENT 1

25
 DSA ASSIGNMENT 1

OUTPUT

//Mueed Hassan 347391:

#include<iostream>

using namespace std;

class node//class node declared

public:

int data;

node *next;// link to the next node in the list

};

class LinkedList//class linked list declared

public:

node *start; // special variable which stores address of the head node.

node *last; // special variable which stores address of the last node.

26
 DSA ASSIGNMENT 1

node *ploc; //to be used by Search(value) method to store address of logical predecessor of value in
a list.

node *loc;//to be used by Search(value) method to store address of the node containing the searched
value in a list. If it is not found it contains NULL. void SLL();

int length;

bool isEmpty();//function to check if list is empty or not

bool Search(int keyvalue);//function to search a specific value on its position

void insertAtfront(int value);// to insert value at the head node

void insertAtlast(int value);//to insert value at the end node

void insertAtmiddle(int value);//insert value at any position in the list

void PrintList();//print the list

void insertsorted(int value);//enter value at the logical position in the list

void sll();//this create s an empty single link listvoid

void swap(int a,int b);

void DestroyList();

27
 DSA ASSIGNMENT 1

};

void LinkedList::sll()//sll function called from the class

{start=NULL;//all the pointer point to null

last=NULL;

ploc=NULL;

loc=NULL;

bool LinkedList::isEmpty() //this creates an empty list

{if(start==NULL)

return true;

else

return false;

void LinkedList::insertAtmiddle(int value)//insert the value in the middle of the list

node *newnode = new node();//creation of a memeory space that will be generated at run time

newnode->data = value;

if (!isEmpty())

{while(loc!=NULL && loc->data<value)

{ ploc=loc;

loc=loc->next;

length++;

};

newnode->next=ploc->next;

cout<<newnode<<endl;

28
 DSA ASSIGNMENT 1

ploc->next=newnode;

else

start==newnode;

last==newnode;

cout<<"insertion at start succesfull"<<endl;

length++;

void LinkedList::insertAtfront(int value)//insert at the front node

{int length=0;

node *newnode = new node();

newnode->data = value;

if(!isEmpty())

{newnode->next=start;

start = newnode;

cout<<"insertion at start succesfull"<<endl<<newnode->data<<endl;

else

start=newnode;

last = newnode;

newnode->next = NULL;

cout<<"insertion at start succesfull"<<endl<<newnode->data<<endl;

length++;

29
 DSA ASSIGNMENT 1

bool LinkedList::Search(int keyvalue)//searchthe specific value

{int lenght=0;

if (!isEmpty())

loc = start;

ploc = NULL;

while(loc!=NULL && loc->data<keyvalue)

{ploc=loc;

loc=loc->next;

length++;

};

if(loc!=NULL)

if (loc->data != keyvalue)

loc=NULL;

cout<<"the searched item is not in the list"<<endl;

return false;

else

return true;

else

{cout<<"the searched item is not in the list"<<endl;

30
 DSA ASSIGNMENT 1

return false;

else

{cout << "list is empty. cannot perform search." << endl;

void LinkedList::insertAtlast(int keyvalue)//isert at the last node

node *newnode = new node();

newnode->data = keyvalue;

if (!isEmpty())

{last->next=newnode;

last=newnode;

cout<<"insertion at last successfull"<<endl;

else

start=newnode;

last=newnode;

cout<<"insertion at last succesfull"<<endl;

length++;

newnode->next = NULL;

void LinkedList::PrintList()//print the list

31
 DSA ASSIGNMENT 1

if(!isEmpty())

{ node *temp=start;

cout<<"**********LIST***********"<<endl;

while(temp!=NULL)

cout<<temp->data<<endl;

temp=temp->next;

};

}else

cout<<"list is empty,nothing to print"<<endl;

void LinkedList::insertsorted(int value)//inert value at the sorted position in the list

{ int lenght=0;

Search(value);

if(loc==NULL)

{ if(ploc==NULL)

insertAtfront(value);

else

{ node *newnode = new node();

newnode->data = value;

newnode->next=ploc->next;

32
 DSA ASSIGNMENT 1

ploc->next=newnode;

if(ploc=last)

last=newnode;

lenght++;

else

cout<<"value is duplicated,can not be inserted"<<endl;

void LinkedList::swap(int a,int b)

node *ploc1=NULL;

node *loc1=NULL;

node *ploc2=NULL;

node *loc2=NULL;

if(!isEmpty())

{ if(start->next!=NULL)

33
 DSA ASSIGNMENT 1

Search(a);

ploc1=ploc;//to store exact positon of value in a exist in the list

loc1=loc;

Search(b);

ploc2=ploc;//to store exact positon of value in a exist in the list

loc2=loc;

if(Search(a)==true && Search(b)==true)//checking condition that both are available

or not in the list

{ if(start->next==loc2 )//checks both are adjacent and in the start

if( loc2->next==NULL)//checks only two values are there in the list

{ loc1->next=NULL;

loc2->next=loc1;

start=loc2;

last=loc1;

ploc1=loc2;

ploc2=NULL;

PrintList();

else if(start==loc2 || (start==loc1)) //

start=loc2;

loc1->next=loc2->next;

loc2->next=loc1;

PrintList();

34
 DSA ASSIGNMENT 1

else if(loc1->next=loc2)//check condition that nodes are adjacent

if(loc!=NULL && ploc!=NULL) //checks value not in the start or end

{ cout<<"im in<<endl"<<endl;

ploc1->next=loc2;

loc1->next=loc2->next;

loc2->next=loc1;

PrintList();

else

cout<<""<<endl;

else //when nodes are un adjacent

{ if(start==loc2 || start==loc1)//one of the value is in start

ploc2->next=loc1;

loc1->next=loc2->next;

loc2->next=ploc2;

35
 DSA ASSIGNMENT 1

start=loc2;

PrintList();

else if(last==loc2 or last==loc1)//check on eof the value is last

ploc1->next=loc2;

loc2->next=loc1->next;

ploc2->next=loc1;

loc1->next=NULL;

last=loc1;

PrintList();

else if(loc!=NULL && ploc!=NULL)//check values are not in the last

or first

{ node *temp=new node;

ploc1->next=loc2;

temp->next=loc2->next;

loc2->next=loc1->next;

ploc2->next=loc1;

loc1->next=temp->next;

PrintList();

36
 DSA ASSIGNMENT 1

else

cout<<"one or both the value you entered ,are not in the list"<<endl;

else

cout<<"single number in the list"<<endl;

else

cout<<"list is empty"<<endl;

void LinkedList::DestroyList()

if (!isEmpty()) //Checking if there is any data in the list to delete

loc = start; //Initializing traversing pointer to start of the list

ploc = NULL;

while(loc != NULL) //Traversing list until reaching last node

ploc = loc;

loc = loc->next;

delete ploc; //Freeing memory allocated to each node sequentially

37
 DSA ASSIGNMENT 1

start = last = NULL; //Setting start and last pointers to null to define list as empty

int main()

{int value=0;LinkedList list;

int x=0;

cout<<"----------------------MENU----------------------------"<<endl;

while(x!=8)

{ cout<<"press 1 to create an empty list"<<endl;

cout<<"press 2 to insert value at first node in list"<<endl;

cout<<"press 3 to insert value at last node in list"<<endl;

cout<<"press 4 to insert value at logical sorted node in list"<<endl;

cout<<"press 5 to print list"<<endl;

cout<<"press 6 to search for an item in the list"<<endl;

cout<<"pree 7 to swap value"<<endl;

cout<<"press 8 to delete list"<<endl;

cout<<"press 9 to exit the program"<<endl;

cin>>x;

switch(x)

{ case 1 :

38
 DSA ASSIGNMENT 1

list.sll();//linked list created here

break;

case 2:

{ cout<<"insert a value need to to entered at the start of the node"<<endl;

cin>>value;

list.insertAtfront(value);

break;

case 3:

{ cout<<"insert a value need to to entered at the end of the node"<<endl;

cin>>value;

list.insertAtlast(value);//function called here

break;

case 4:

39
 DSA ASSIGNMENT 1

cout<<"insert a value need to to entered at the sorted position in the list"<<endl;

cin>>value;

list.insertsorted(value);//sorted function

break;

case 5:

list.PrintList();//function print called

break;

case 6:

{ int keyvalue;//search function called

cout<<"insert the value to search"<<endl;

cin>>keyvalue;

list.Search(keyvalue);

break;

case 7:

{ cout <<"enter the value you want to swap"<<endl;

int a;

cin>>a;

cout<<"enter the value you want to swap with"<<endl;

int b;

40
 DSA ASSIGNMENT 1

cin>>b;

list.swap(a,b);

case 8:

{ cout<<"list destroyed"<<endl;

list.DestroyList();//freeing up the memory

};

return 0;

Deliverables:

• You should include screenshots of the outputs of all the implemented functions in this file.
• Moreover, you should upload your source code in a separate .cpp file.

41