Submitted To: Sir Adeel.

Submitted by: Tayyaba Riaz

Roll No. 2020-BSCS-039
Subject: DSA

Lab # 06: Tasks

Task 1: Write a program to insert a node at first, last and at specified position of double
linked list
Program:
#include<iostream>
using namespace std;
struct node {
int data;
 node* next = NULL;
node* prev = NULL;
};
class DoublyLinkedList {
node* first;
node* last;
public:
DoublyLinkedList () {first = last = NULL;} //constructor
void insert (int a) {
node* n = new node ();
n->data = a;
first->prev = n;
n->next = first;
n->prev = NULL;
first = n;
}
void insertAtEnd (int a) {
node* n = new node ();
n->data = a;
n->next = NULL;
if (first == NULL) {first = n;}
else {
last->next = n;
n->prev = last;
}
last = n;
}
void insertAtLoc (int a, int loc) {
node* n = new node ();
n->data = a;
node* temp = first;
int l = 1;
while (l! = loc) {
temp = temp->next;
l++;
}
n->next = temp;
n->prev = temp->prev;
(temp->prev)->next = n;
temp->prev = n;
}
void display () {
node* temp = first;
while (temp! = NULL) {
cout << temp->data << " ";
temp = temp->next;
 }
}
};
int main () {
int i, c, l;
DoublyLinkedList d;
cout << "Insert in a Doubly Linked List." << endl << "1) Insert at beginning." << endl;
cout << "2) Insert at a Location." << endl << "3) Insert at the end." << endl;
cout << "4) Display the Doubly Linked List." << endl << "0) Exit." << endl;
a:
cout << "Enter choice:" << endl;
cin >> i;
switch (i) {
case 1:
cout << "Enter the number you want to insert." << endl;
cin >> c;
d. insert(c);
break;
case 2:
cout << "Enter the number and the location where you want to insert." << endl;
cin >> c >> l;
d. insertAtLoc (c, l);
break;
case 3:
cout << "Enter the number you want to insert." << endl;
cin >> c;
d. insertAtEnd(c);
break;
case 4:
d. display ();
case 0:
return 0;
default:
cout << "Invalid expression." << endl;
}
goto a;
return 0;
}
Output:
Task 2: Write a program to eliminate duplicates from double linked list.
Program:
#include<iostream>
using namespace std;
struct node {
int data;
node* next = NULL;
node* prev = NULL;
};
class DoublyLinkedList {
node* first;
node* last;
public:
DoublyLinkedList () {first = last = NULL;} //constructor
void insertAtEnd (int a) {
node* n = new node ();
n->data = a;
n->next = NULL;
if (first == NULL) {first = n;}
else {
last->next = n;
n->prev = last; }
last = n;
}
void deleteNode (node* x) {
if (x->next == NULL) {
(x->prev)->next = NULL;
}
else {
(x->prev)->next = x->next;
 (x->next)->prev = x->prev;
}
delete x;
}
void removeDuplicates () {
node* temp = first;
node* n = first;
int a;
node* p = NULL;
while (temp! = NULL) {
a = temp->data;
n = temp->next;
while (n! = NULL) {
if (n->data == a) {
node* p = n;
n = n->next;
deleteNode(p);
}
else {n = n->next;}
}
temp = temp->next;
}
}
void display () {
node* temp = first;
while (temp! = NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}
};
int main () {
int arr [5];
DoublyLinkedList d;
cout << "Insert 5 values to the Linked List." << endl;
for (int i = 0; i < 5; i++) {
cin >> arr[i];
d. insertAtEnd (arr[i]);
}
cout << "After removing duplicates: " << endl;
d. removeDuplicates ();
d. display ();
return 0;
}
Output:
Task 3: Write a program to delete a node from first, last and at specified position of double
linked list.
Program:
#include<iostream>
using namespace std;
struct node {
int data;
node* next = NULL;
node* prev = NULL;
};
class DoublyLinkedList {
node* first;
node* last;
public:
DoublyLinkedList () {first = last = NULL;} //constructor
void insertAtEnd (int a) {
node* n = new node ();
n->data = a;
n->next = NULL;
if (first == NULL) {first = n;}
else {
last->next = n;
n->prev = last;}
last = n;
}
void deleteFirstNode () {
node* temp = first;
first = temp->next;
first->prev = NULL;
delete temp;
}
void deleteAtEnd () {
node* temp = last->prev;
delete last;
last = temp;
}
void deleteAtLoc (int loc) {
node* temp = first;
int l = 1;
 while (l! = loc) {
temp = temp->next;
l++;}
(temp ->next)->prev = temp->prev;
(temp ->prev)->next = temp->next;
delete temp;
}
void display () {
node* temp = first;
while (temp! = NULL) {
cout << temp->data << " ";
temp = temp->next;}
cout << "\n";
}
};
int main () {
int i, c, l;
DoublyLinkedList d;
cout << "Delete from a Doubly Linked List." << endl << "1) Delete from the beginning."
<< endl;
cout << "2) Delete from a Location." << endl << "3) Delete from the end." << endl;
cout << "4) Display the Doubly Linked List." << endl << "5) Insert to the list." << endl;
cout << "0) to Exit" << endl;
a:
cout << "Enter choice:" << endl;
cin >> i;
switch (i) {
case 1:
d. deleteFirstNode ();
break;
case 2:
cout << "Enter the location from where you want to delete." << endl;
cin >> l;
d. deleteAtLoc (l);
break;
case 3:
d. deleteAtEnd ();
break;
case 4:
d. display ();
break;
case 5:
cout << "Enter the number you want to insert" << endl;
cin >> c;
d. insertAtEnd (c);
break;
 case 0:
return 0;
default:
cout << "Invalid expression." << endl;
}
goto a;
return 0;
}
Output:

Task 4: Implement the queue using linkedlist.

Program:
#include<iostream>
using namespace std;
struct node {
int data;
node* next = NULL;
node* prev = NULL;
};
class Queue {
node* front;
node* rear;
public:
Queue () {front = NULL; rear = NULL;}
int dequeue () {
int d = rear->data;
node* p = rear->prev;
delete rear;
 p->next = NULL;
rear = p;
return d;
}
void enqueue (int x) {
node* n = new node ();
n->data = x;
n->prev = NULL;
if (front == NULL) {
n->next = NULL;
front = n;
rear = n;}
else {
front->prev = n;
n->next = front;
front = n;}
}
void display () {
cout << "Queue elements: ";
node* p = front;
while (p! = NULL) {
cout << p->data << " ";
p = p->next;
}
cout << "\n";
}

void peek () {
cout << "Top element: " << front->data << endl;}

bool isEmpty () {return (front == NULL);}

};
int main () {
int i, c;
Queue s;
cout << "Implementing queue using Linked List." << endl << "1) Enqueue to queue." <<
endl;
cout << "2) Dequeue from queue." << endl << "3) Display queue." << endl;
cout << "4) Peek from queue." << endl << "0) Exit." << endl;
a:
cout << "Enter choice:" << endl;
cin >> i;
switch (i) {
case 1:
cout << "Enter the character you want to enqueue." << endl;
cin >> c;
 s. enqueue (c);
break;
case 2:
if (s. isEmpty ()) {cout << "Stack is empty.";}
else {
int p = s. dequeue ();
cout << p << " is dequeued." << endl;
}
break;
case 3:
if (s. isEmpty ()) {cout << "Queue is empty.";}
else {s. display ();}
break;
case 4:
if (s. isEmpty ()) {cout << "Queue is empty.";}
else {s. peek ();}
break;
case 0:
return 0;
default:
cout << "Invalid expression." << endl;
}
goto a;
return 0;
}
Output: