CSL-210: Data Structures and Algorithms Lab

BS(AI)3-A Semester
03(Fall 2022)

Exercise 1

Run the linked list implementation, discussed in the class. Call all the functions in the driver
program and check the output.

Exercise 2

Write 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 change next pointer fields
in the concerned nodes. Your function should handle all possible cases:

a. The two nodes are not adjacent and none of them is the first node.

b. The two nodes are not adjacent to each other and one of them is the first node.

c. Both nodes are adjacent and none of them is the first node.

d. Both nodes are adjacent and one of them is the first node

Exercise 3

Write a function which reverses the order of the linked list. If the original list is 1-> 2->3-
>4>5 -> 6, the updated list should be 6 -> 5 -> 4 -> 3 -> 2 ->1. Note that this function should
only change pointer fields in the nodes, you are not allowed to modify data field of any node

-------------------------------Class------------------------

#include <iostream>
#include <stdlib.h>
 CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A Semester
03(Fall 2022)

using namespace std;

class NumberList
{ private
:
struct ListNode
{
double value;
struct ListNode *next;
};

ListNode *head;

public :
NumberList()
{
head = NULL;
}

//~NumberList();

void appendNode(double num)

{
ListNode *newNode;//to point a new node
ListNode *nodePtr;//to move through the list

//Alocate a new node and store num there

newNode = new ListNode; newNode->value = num;
newNode->next = NULL;

//if there are no nodes in the list

//make newNode the first node.
if(!head)
{
head = newNode;
}
else //Otherwise, insert newNode at end
{
//initialize node ptr at the end of the list
 CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A Semester
03(Fall 2022)

nodePtr = head;

//Find the last node in the list

while(nodePtr->next)
{
nodePtr = nodePtr->next;
}

//insert newNode as the last node nodePtr-

>next = newNode;
}
}

void insertNode(double num)

{
ListNode *newNode; //A new node
ListNode *nodePtr; //To traverse the list
ListNode *previousNode = NULL; //The previous node

//Alocate a new Node and store num there

newNode = new ListNode;
newNode->value = num;

//If there are no nodes in the list

//make newNode the first node
if(!head)
{
head = newNode;
newNode->next = NULL;
}
else //Otherwise, insert newNode
{
//Position nodePtr at the head of list
nodePtr = head;
//initialize previous node to null
previousNode = NULL;
}
//skip all the nodes whose value is less than num.
while(nodePtr!=NULL && nodePtr->value < num)
 CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A Semester
03(Fall 2022)

{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//if the new node is to be the 1st in the list
//insert it before all other nodes
if (previousNode == NULL)
{
head = newNode;
newNode->next=nodePtr;
}
else //otherwise insert after the previous node
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
//deleting a specific node
void deleteNode(double num)
{
ListNode *nodePtr; //To transverse the List
ListNode *previousNode;//To point to the previous Node

//If the list is empty, do nothing

if(!head)
{
return;
}

//Determine if the first node is the one if(head->value == num)

{
nodePtr = head->next;
delete head;
head =nodePtr;
}
else
{
//initialize nodePtr to head of list
nodePtr = head;
 CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A Semester
03(Fall 2022)

//skip all the nodes whose value member is not equal to num
while (nodePtr != NULL && nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}

//If nodePtr is not at the end of the list

//link the previous node to the node after
//nodePtr, then delete nodePtr
if(nodePtr)
{
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
}

//Display the data in the list

void displayList() const
{
ListNode *nodePtr; //To move through the list double
num;
nodePtr = head;

while(nodePtr!=NULL)
{
num = nodePtr->value;
nodePtr=nodePtr->next;
cout<<num<<endl;
}
}
//function to swap two nodes
void swap_nodes(double p,double q)
{
//struct ListNode *next = NULL;
//ListNode **head =NULL;
// struct node *prevNode1 = NULL, *prevNode2 = NULL, *node1 = head, *node2 = head;
 CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A Semester
03(Fall 2022)

struct ListNode *p_prev=NULL,*p_curr=head,*q_prev=NULL,*q_curr=head;

if(p==q){
return;
} //if p and q are same, break

//searching p and moving pointer to it

while(p_curr!=NULL&&p_curr->value!=p)
{
p_prev=p_curr;
p_curr=p_curr->next;
}

//searching q and moving pointer to it

while(q_curr!=NULL&&q_curr->value!=q)
{
q_prev=q_curr;
q_curr=q_curr->next;
}
//if either not present, break
if(p_curr==NULL || q_curr==NULL){
return;
}
//check if p is head of the list if(p_prev!
=NULL){
p_prev->next=q_curr;
}
else {
head=q_curr;
}
//check if q is head of the list
if(q_prev!=NULL){
q_prev->next=p_curr;
}
else{
head=p_curr;
}
 CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A Semester
03(Fall 2022)

//swapping remaining pointers accordingly

ListNode* pole=q_curr->next;
q_curr->next=p_curr->next; p_curr->next=pole;
}
void reverseList() {
//1. If head is not null create three nodes
// prevNode - pointing to head,
// tempNode - pointing to head, //
curNode - pointing to next of head
if(head != NULL) { ListNode*
prevNode = head;
ListNode* tempNode = head;
ListNode* curNode = head->next;

//2. assign next of prevNode as null to make the

// first node as last node of the reversed list prevNode-
>next = NULL;

while(curNode != NULL) {
//3. While the curNode is not null adjust links
// (unlink curNode and link it to the reversed list
// from front and modify curNode and prevNode)
tempNode = curNode->next; curNode->next =
prevNode; prevNode = curNode;
curNode = tempNode;
}

//4. Make prevNode (last node) as head

head = prevNode;
}
}

};
 CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A

----------------- Main ------------------ #include

<iostream>
#include "NumberList.h"

using namespace std; int

main(){
struct ListNode *start =NULL;

NumberList list;
list.appendNode(2.2);
list.insertNode(4.2);
list.insertNode(3.1);
list.insertNode(2.1);
list.insertNode(1.2);
list.displayList();

double num1,num2;
cout << "Enter Num1 : ";
cin >> num1; cout <<
"Enter Num2 : ";
cin >> num2;

cout << endl << "Swap Nodes on LinkedList" << endl;

list.swap_nodes(num1,num2);
list.displayList();

cout << endl << "Reversing a LinkedList" << endl;

list.reverseList();
list.displayList();
return 0;
}

Semester 03(Fall 2022)

CSL-210: Data Structures and Algorithms Lab
BS(AI)3-A Semester
03(Fall 2022)