Department of Software Engineering

Data Structures & Algorithms Lab

Lab # 8

SUBMITTED TO:
Sir Rehan Ahmed Siddiqui
SUBMITTED BY:
Mahnoor Mustafa
(2020-BSE-051)
CLASS:
BSE III B
 Task 1:
1. Consider the following doubly linked list

Write C++ statements to: 

a. Print the value 26 using the pointer ‘last’: 
cout<<last->prev->data;
b. Print the value 17 using the pointer ‘first: 
cout<<first->next->data;
c. Print the address of the node containing value 9 using the pointer ‘last’: 
cout<<last->prev-> prev-> prev-> prev->&;
2. Given the following linked list, state what does each of the following statements refer to?

first->data;
5

last->next;
NULL

first->next->prev;
5

first->next->next->data;
15

last->prev->data; 20
 3. Redraw the following list after the given instructions are executed:

ptr->next->prev = ptr->prev;
ptr->next->prev = ptr->prev;
ptr->prev->next = ptr->next;
delete ptr;

ptr

20

15
Code Exercise 1:
Implement the class Doubly Linked List to create a list of integers. You need
to provide the implementation of the member functions as described in the
following.
#include <iostream>
using namespace std;
class DList
{
private:
struct node
{
int data;
node* next;
node* prev;
} *head;
public:
DList() {
head = NULL;
}
~DList() {}
bool emptyList() {
if (head == NULL)
return true;
else
return false;

}// Checks if the list is empty or not

void insertafter(int oldV, int newV) {
node* ptr;
ptr = head;
while (ptr->data != oldV)
{
ptr = ptr->next;
}
node* p;
p = new node;
p->data = newV;
p->prev = ptr;
p->next = ptr->next;
ptr->next = p;
p->next->prev = p;

// Inserts a new node with value ‘newV’ after the node containing value ‘oldV’. If a
node with value ‘oldV’ does not exist, inserts the new node at the end.
void deleteNode(int value) {
node* ptr;
int flag = 0;
ptr = head;
if ((ptr->next == NULL) && (ptr->prev == NULL))
{
 head = NULL;
delete ptr;
}
else if (ptr->data == value)
{
head = head->next;
ptr->next = NULL;
head->prev = NULL;
delete ptr;
}
else
{
while (ptr->next != NULL)
{
if (ptr->data == value)
{
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
ptr->next = NULL;
ptr->prev = NULL;
delete ptr;
flag++;
break;
}
ptr = ptr->next;
}
if (flag == 0)
{
ptr->prev->next = NULL;
ptr->prev = NULL;
delete ptr;
}
}

// Deletes the node containing the specified value

void insert_begin(int value) {
node* temp;
temp = new node;
temp->data = value;
temp->next = head;
temp->prev = NULL;
if (head != NULL)
head->prev = temp;
head = temp;
}
// Inserts a new node at the start of the list
void insert_end(int value) {
node* temp;
temp = new node;
temp->data = value;
temp->next = NULL;
if (head == NULL)
{
head = temp;
temp->prev = NULL;
 }

else
{
node* p;
p = head;
while (p->next != NULL)
{
p = p->next;
}
p->next = temp;
temp->prev = p;
}
}

// Inserts a new node at the end of the list

void traverse() {
node* p;
p = head;
while (p != NULL) {
cout << p->data << "->";
p = p->next;
}
}
// Displays the values stored in the list
void traverse2() {
node* temp;
temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
while (temp != NULL)
{
cout << temp->data << "->";
temp = temp->prev;
}

}
// Displays the values stored in the list in reverse order
};
int main()
{
DList l1;
cout << "Link list" << endl << endl;
l1.insert_begin(5);
l1.insert_begin(10);
l1.insert_begin(15);
l1.insert_begin(20);
l1.insert_begin(25);
l1.traverse();
cout << endl << endl;
cout << "Link list after in between insertion" << endl << endl;
l1.insertafter(20, 25);
l1.traverse();
cout << endl << endl;
cout << "Link list after insertion at end" << endl << endl;
l1.insert_end(50);
 l1.traverse();
cout << endl << endl;
cout << "Link list after deleting a node" << endl << endl;
l1.deleteNode(20);
l1.traverse();
cout << endl << endl;
cout << "LInked list in reverse order " << endl << endl;
l1.traverse2();
system("pause");
return 0;
}

Code Exercise 2:
A stack can be implemented using a doubly linked list. The first node can
serve as the ‘top’ of Stack and ‘push’ and ‘pop’ operations can be
implemented by adding and removing nodes at the head of the linked list.
Implement the Stack class using a linked list (Doubly) and provide all the
standard member functions.
#include <iostream>
using namespace std;
class DList
{
private:
struct Node {

struct Node* prev;

int data;
struct Node* next;

}*head;
public:
DList() {
head = NULL;
}
 ~DList() {}
bool isempty() {
if (head == NULL)
return true;
else
return false;
}

void push(int data) {

struct Node* newnode;

newnode = new Node();

if (!newnode) {
cout << "Stack Overflow" << endl;
}

newnode->prev = head;
newnode->data = data;
newnode->next = NULL;

head = newnode;
}

void pop() {

if (isempty()) {
cout << "Stack Underflow";
exit(1);
}

Node* tmp;
tmp = new Node();

tmp->next = NULL;
tmp->data = head->prev->data;
tmp->prev = head->prev->prev;

delete head;
head = tmp;

void display() {

Node* ptr;
ptr = head;

cout << ptr->data << "->";

while (ptr->prev != NULL) {
cout << ptr->prev->data << "->";
ptr = ptr->prev;
}
cout << endl;
}
};

int main ()
{
DList l1;
cout << "Implementation of stack using doubly linked list" << endl << endl;
cout << "Adding nodes to the stack" << endl << endl;
l1.push(10);
l1.push(20);
l1.push(30);
l1.push(40);
l1.push(50);
l1.display();
cout << endl << endl;
cout << "Link list after deleting node from the stack" << endl << endl;
l1.pop();
l1.display();
cout << endl << endl;
system("pause");
return 0;
}

Code Exercise 3:
Implement simple Queue through Doubly linked list.
#include <iostream>
using namespace std;

class Queue
{
private:
struct node
{
int data;
node* next;
node* prev;
};
public:
node* front;
node* rear;

Queue()
{
front = NULL;
rear = NULL;
 }
void enqueue(int value);
void dequeue();
void traverse();
};
void Queue::enqueue(int value)
{
node* ptr;
ptr = new node;
ptr->data = value;
ptr->next = NULL;
ptr->prev = NULL;
if ((front == NULL))
{
front = ptr;
rear = ptr;
ptr->next = NULL;
ptr->prev = NULL;
}
else
{
ptr->next = front;
ptr->next->prev = ptr;
front = ptr;
ptr->prev = NULL;
}
}
void Queue::dequeue()
{
int n;
node* p;
if ((front == NULL) && (rear == NULL))
{
cout << " Empty Queue " << endl;
}
else
{

p = rear;
rear = p->prev;
p->prev = NULL;
rear->next - NULL;
n = p->data;
delete p;
cout << " Deleted value : " << n << endl;
}

}
void Queue::traverse()
{
node* pn;
pn = front;
if (pn == NULL)
{
cout << " Empty Queue " << endl;
}
else
{
 while (pn != rear->next)
{
cout << pn->data << "->";
pn = pn->next;
}
}
}

int main ()
{
Queue q1;
cout << "Implementation of queue using doubly linked list" << endl << endl;
q1.enqueue(20);
q1.enqueue(30);
q1.enqueue(40);
q1.enqueue(50);
cout << "Adding nodes to the queue" << endl << endl;
q1.traverse();
cout << endl << endl;
cout << "Front = " << (q1.front)->data << endl;
cout << "Rear = " << (q1.rear)->data << endl;
cout << endl;
cout << "Deleting nodes from the queue" << endl << endl;
q1.dequeue();
cout << endl;
cout << "Linked list after deletion from the queue:" << endl << endl;
q1.traverse();
cout << endl << endl;
cout << "Front = " << (q1.front)->data << endl;
cout << "Rear = " << (q1.rear)->data << endl << endl;
return 0;
}