Report Date: 01-01-2024
Assignment 2
CS-214- Data Structures & Algorithms
CS-214 - Fall 2023
Khawaja Humble Hassan
Assignment 2 (Total Marks: 10)
Name: Waleed Ahmad
Roll No: 211390010
Question 1 (10.00) CLO2
Analyze the following problem to implement it in C++. (C4)
A Doubly Linked List which has the functions to insert the data, delete a
particular node and print the complete Linked List. Make sure to solve this
problem using a
separate class for Node of a doubly linked list and a class for the list itself.
CODE:
#include <iostream>
using namespace std;
template <class T>
// Making a class Node
class Node
{
T data;
Node<T> *next;
Node<T> *previous;
public:
Node(T d);
void setData(T d);
T getData();
void setNext(Node<T> *ptr);
void setPrevious(Node<T> *ptr);
Node<T>* getNext();
Node<T>* getPrevious();
};
//Implementation of class Node
template <class T>
Node<T>::Node(T d)
{
data = d;
next = NULL;
previous = NULL;
}
template <class T>
void Node<T>::setData(T d)
{
data = d;
}
template <class T>
T Node<T>::getData()
{
return data;
}
template <class T>
void Node<T>::setNext(Node<T> *ptr)
{
next = ptr;
}
template <class T>
Node<T>* Node<T>::getNext()
{
return next;
}
template <class T>
void Node<T>::setPrevious(Node<T> *ptr)
{
previous = ptr;
}
template <class T>
Node<T>* Node<T>::getPrevious()
{
return previous;
}
// Making a class DList
template <class T>
class Dlist
{
Node<T> * first;
public:
Dlist();
void insertNode(Node<T> * pBefore, Node<T> * pNew);
void deleteNode(Node<T> * nodeTobeDeleted);
void printList()const;
};
// Implementation of class Dlist.
template <class T>
Dlist<T>::Dlist()
{
first = NULL;
}
template <class T>
void Dlist<T>::insertNode(Node<T> * pBefore, Node<T> * pNew)
{
if (first == NULL)
{
first = pNew;
}
else if (pBefore->getNext() == NULL && pBefore->getPrevious() != NULL)
{
pBefore->setNext(pNew);
pNew->setPrevious(pBefore);
pNew->setNext(NULL);
}
else if (pBefore->getNext() == NULL && pBefore->getPrevious() == NULL)
{
pNew->setPrevious(pBefore);
pBefore->setNext(pNew);
pNew->setNext(NULL);
}
else if (pBefore->getNext() != NULL && pBefore->getPrevious() == NULL)
{
pNew->setNext(first);
pNew->setPrevious(NULL);
first->setPrevious(pNew);
first = pNew;
}
else
{
pNew->setPrevious(pBefore);
pNew->setNext(pBefore->getNext());
pBefore->getNext()->setPrevious(pNew);
pBefore->setNext(pNew);
}
}
template <class T>
void Dlist<T>::deleteNode(Node<T> *nodeTobeDeleted)
{
if (nodeTobeDeleted == first)
{
first = first->getNext();
first->setPrevious(NULL);
delete nodeTobeDeleted;
}
else if (nodeTobeDeleted->getNext() == NULL)
{
nodeTobeDeleted->getPrevious()->setNext(NULL);
delete nodeTobeDeleted;
}
else
{
nodeTobeDeleted->getNext()->setPrevious(nodeTobeDeleted->getPrevious());
nodeTobeDeleted->getPrevious()->setNext(nodeTobeDeleted->getNext());
delete nodeTobeDeleted;
}
}
template <class T>
void Dlist<T>::printList()const
{
Node<T> * temp;
temp = first;
while (temp)
{
cout << temp->getData() << " ";
temp = temp->getNext();
}
cout << endl;
}
// Now, wriring the main program
int main()
{
// Declaring and Initializing different nodes.
Node<int> *n1, *n2, *n3, *n4, *n5, *n6, *n7, *n8;
n1 = new Node<int>(1);
n2 = new Node<int>(2);
n3 = new Node<int>(3);
n4 = new Node<int>(4);
n5 = new Node<int>(5);
n6 = new Node<int>(6);
n7 = new Node<int>(7);
n8 = new Node<int>(8);
Dlist<int> l;
[Link](NULL, n1);
[Link](n1, n2);
[Link](n2, n3);
[Link](n3, n4);
[Link](n4, n5);
cout << " Printing the Doubly Linked list:" << endl;
[Link]();
cout << " Insertion at the First of the List: " << endl;
[Link](n1, n7);
[Link]();
cout << " Insertion at the Last of the List: " << endl;
[Link](n5, n6);
[Link]();
cout << " Insertion in the Middle of the List: " << endl;
[Link](n4, n8);
[Link]();
cout << " Delteing node at the First of the List: " << endl;
[Link](n7);
[Link]();
cout << " Delteing node at the Last of the List: " << endl;
[Link](n6);
[Link]();
cout << " Delteing node in the Middle of the List: " << endl;
[Link](n8);
[Link]();
system("pause");
return 0;
}
Result:
CLOs
CLO2 The student has the ability to analyze and apply linear data structures in C4
programming language
