INJIBARA UNIVERSITY

College of Engineering and Technology

Department of Information Technology
Third year Section B
Data structure and Algorithm
Group-2 Assignment

Group members
No. Name Sex Id
1 Ermeyas Muluken M 0732
2 Engidayehu Mulat M 0728
3 Enyew Muluye M 0729
4 Enyew Welelaw M 0730
5 Estibel Mitku M 0734
6 Esubalew Yeshane M 0736
7 Esubalew Nega M 0735
8 Elsabet Asmare F 0720
9 Emebet Azale F 0722
10 Ephrem Abeje M 0731

Submitted to:- Agerie .(Msc.)

1|Page
I. Write full implementation for doubly linked list data structure using C++
program. Your implementation should support the following operations.
1. A. C++ implementation of a doubly linked list where nodes are added at the
beginning of the list.
#include <iostream>
using namespace std;
// Node structure for a doubly linked list
struct Node {
int data;
Node* next;
Node* prev;
Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head;
public:
// Constructor
DoublyLinkedList() : head(nullptr) {}
// Destructor
~DoublyLinkedList() {
Node* current = head;
Node* nextNode;
while (current != nullptr) {
nextNode = current->next;
delete current;
current = nextNode;
}
}
// Add node at the beginning
void addAtBeginning(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
// If list is empty, new node is the head
head = newNode;
} else {
// Insert new node at the beginning
newNode->next = head;
head->prev = newNode;
head = newNode;
2|Page
}
}
// Display the list from head to end
void displayForward() const {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Display the list from end to head
void displayBackward() const {
Node* temp = head;
if (temp == nullptr) {
cout << "List is empty." << endl;
return;
}
// Move to the end of the list
while (temp->next != nullptr) {
temp = temp->next;
}
// Traverse backward from the end
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
};
// Main function to test the doubly linked list implementation
int main() {
DoublyLinkedList dll;
dll.addAtBeginning(10);
dll.addAtBeginning(20);
dll.addAtBeginning(30);
cout << "List (Forward): ";
dll.displayForward();
cout << "List (Backward): ";
dll.displayBackward();
return 0;
3|Page
}
B. C++ implementation of a doubly linked list where nodes are added at the end of the list.
#include <iostream>
using namespace std;
// Node structure for a doubly linked list
struct Node {
int data;
Node* next;
Node* prev;
Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
// Constructor
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Destructor
~DoublyLinkedList() {
Node* current = head;
Node* nextNode;
while (current != nullptr) {
nextNode = current->next;
delete current;
current = nextNode;
}
}
// Add node at the end
void addAtEnd(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
// If list is empty, new node is both the head and tail
head = newNode;
tail = newNode;
} else {
// Insert new node at the end
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// Display the list from head to end
void displayForward() const {
Node* temp = head;

4|Page
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Display the list from end to head
void displayBackward() const {
Node* temp = tail;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
};
// Main function to test the doubly linked list implementation
int main() {
DoublyLinkedList dll;
dll.addAtEnd(10);
dll.addAtEnd(20);
dll.addAtEnd(30);
cout << "List (Forward): ";
dll.displayForward();
cout << "List (Backward): ";
dll.displayBackward();
return 0;
}
C. C++ implementation of a doubly linked list where nodes can be added at a specific location or in
the middle of the list.
#include <iostream>
using namespace std;
// Node structure for a doubly linked list
struct Node {
int data;
Node* next;
Node* prev;

Node(int data) : data(data), next(nullptr), prev(nullptr) {}

};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
// Constructor
5|Page
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Destructor
~DoublyLinkedList() {
Node* current = head;
Node* nextNode;
while (current != nullptr) {
nextNode = current->next;
delete current;
current = nextNode;
}
}
// Add node at the beginning
void addAtBeginning(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
// Add node at the end
void addAtEnd(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}

// Add node at a specific position (1-based index)

void addAtPosition(int data, int position) {
if (position < 1) {
cout << "Position must be greater than 0." << endl;
return;
}
Node* newNode = new Node(data);
if (position == 1) {
// Insert at the beginning
addAtBeginning(data);

6|Page
return;
}
Node* temp = head;
int currentPosition = 1;
while (temp != nullptr && currentPosition < position - 1) {
temp = temp->next;
currentPosition++;
}
if (temp == nullptr) {
// Position is beyond the end of the list, add at the end
addAtEnd(data);
} else {
// Insert new node at the given position
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != nullptr) {
temp->next->prev = newNode;
}
temp->next = newNode;
if (newNode->next == nullptr) {
// If inserted node is the new tail
tail = newNode;
}
}
}
// Display the list from head to end
void displayForward() const {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Display the list from end to head
void displayBackward() const {
Node* temp = tail;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
};

// Main function to test the doubly linked list implementation

7|Page
int main() {
DoublyLinkedList dll;
dll.addAtEnd(10);
dll.addAtEnd(20);
dll.addAtEnd(30);
cout << "List (Forward) before insertion: ";
dll.displayForward();
dll.addAtPosition(15, 2); // Add 15 at position 2
dll.addAtPosition(25, 4); // Add 25 at position 4 (which will be at the end here)
dll.addAtPosition(5, 1); // Add 5 at position 1 (beginning)
cout << "List (Forward) after insertion: ";
dll.displayForward();
cout << "List (Backward): ";
dll.displayBackward();
return 0;
}
2. A. Write full implementation for doubly linked list data structure using C++
program that deletes data/nodes from front.
#include <iostream>
using namespace std;
// Node structure for a doubly linked list
struct Node {
int data;
Node* next;
Node* prev;
Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
// Constructor
DoublyLinkedList() : head(nullptr), tail(nullptr) {}

// Destructor
~DoublyLinkedList() {
Node* current = head;
Node* nextNode;
while (current != nullptr) {
nextNode = current->next;
delete current;
current = nextNode;
}
}

8|Page
// Add node at the beginning
void addAtBeginning(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
// Delete node from the front
void deleteFromFront() {
if (head == nullptr) {
cout << "List is empty. Nothing to delete." << endl;
return;
}
Node* nodeToDelete = head;
head = head->next;

if (head != nullptr) {
head->prev = nullptr;
} else {
// If the list becomes empty, also update the tail
tail = nullptr;
}
delete nodeToDelete;
}
// Display the list from head to end
void displayForward() const {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Display the list from end to head
void displayBackward() const {
Node* temp = tail;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;

9|Page
}
};
// Main function to test the doubly linked list implementation
int main() {
DoublyLinkedList dll;
dll.addAtBeginning(10);
dll.addAtBeginning(20);
dll.addAtBeginning(30);
cout << "List (Forward) before deletion: ";
dll.displayForward();
dll.deleteFromFront();
dll.deleteFromFront();
cout << "List (Forward) after deletion: ";
dll.displayForward();
cout << "List (Backward): ";
dll.displayBackward();
return 0;
}
B. Write full implementation for doubly linked list data structure using C++ program that
deletes data/nodes from end.
#include <iostream>
using namespace std;
// Node structure for a doubly linked list
struct Node {
int data;
Node* next;
Node* prev;
Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
// Constructor
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Destructor
~DoublyLinkedList() {
Node* current = head;
Node* nextNode;
while (current != nullptr) {
nextNode = current->next;
delete current;
current = nextNode;
}

10 | P a g e
}
// Add node at the end
void addAtEnd(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// Delete node from the end
void deleteFromEnd() {
if (tail == nullptr) {
cout << "List is empty. Nothing to delete." << endl;
return;
}
Node* nodeToDelete = tail;
tail = tail->prev;
if (tail != nullptr) {
tail->next = nullptr;
} else {
// If the list becomes empty, also update the head
head = nullptr;
}
delete nodeToDelete;
}
// Display the list from head to end
void displayForward() const {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Display the list from end to head
void displayBackward() const {
Node* temp = tail;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;

11 | P a g e
}
};
// Main function to test the doubly linked list implementation
int main() {
DoublyLinkedList dll;
dll.addAtEnd(10);
dll.addAtEnd(20);
dll.addAtEnd(30);
cout << "List (Forward) before deletion: ";
dll.displayForward();
dll.deleteFromEnd();
dll.deleteFromEnd();
cout << "List (Forward) after deletion: ";
dll.displayForward();
cout << "List (Backward): ";
dll.displayBackward();
return 0;
}

C. Write full implementation for doubly linked list data structure using c++ program that
deletes data/nodes from middle.
#include <iostream>
using namespace std;
// Node structure for a doubly linked list
struct Node {
int data;
Node* next;
Node* prev;
Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head;
Node* tail;

public:
// Constructor
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Destructor
~DoublyLinkedList() {
Node* current = head;
Node* nextNode;
while (current != nullptr) {
nextNode = current->next;
delete current;

12 | P a g e
current = nextNode;
}
}
// Add node at the end
void addAtEnd(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// Delete node from a specific position (1-based index)
void deleteAtPosition(int position) {
if (position < 1) {
cout << "Position must be greater than 0." << endl;
return;
}
if (head == nullptr) {
cout << "List is empty. Nothing to delete." << endl;
return;
}
Node* temp = head;
if (position == 1) {
// Delete the head node
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
} else {
// If the list becomes empty, also update the tail
tail = nullptr;
}
delete temp;
return;
}
int currentPosition = 1;
while (temp != nullptr && currentPosition < position) {
temp = temp->next;
currentPosition++;
}
if (temp == nullptr) {
cout << "Position exceeds the length of the list." << endl;
return;

13 | P a g e
}
if (temp->next != nullptr) {
temp->next->prev = temp->prev;
} else {
// If the node to delete is the tail
tail = temp->prev;
}
if (temp->prev != nullptr) {
temp->prev->next = temp->next;
}
delete temp;
}
// Display the list from head to end
void displayForward() const {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Display the list from end to head
void displayBackward() const {
Node* temp = tail;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
};
// Main function to test the doubly linked list implementation
int main() {
DoublyLinkedList dll;
dll.addAtEnd(10);
dll.addAtEnd(20);
dll.addAtEnd(30);
dll.addAtEnd(40);
dll.addAtEnd(50);
cout << "List (Forward) before deletion: ";
dll.displayForward();
dll.deleteAtPosition(3); // Delete the node at position 3 (which is 30)
dll.deleteAtPosition(1); // Delete the node at position 1 (which is 10)
dll.deleteAtPosition(5); // Try to delete the node at position 5 (which is out of range)
cout << "List (Forward) after deletion: ";
dll.displayForward();

14 | P a g e
cout << "List (Backward): ";
dll.displayBackward();
return 0;
}
3. Write full implementation for doubly linked list data structure using C++ program
that displays the list of elements backward displays.
#include <iostream>
using namespace std;
// Node structure for a doubly linked list
struct Node {
int data;
Node* next;
Node* prev;
Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
// Doubly Linked List class
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
// Constructor
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Destructor
~DoublyLinkedList() {
Node* current = head;
Node* nextNode;
while (current != nullptr) {
nextNode = current->next;
delete current;
current = nextNode;
}
}
// Add node at the end
void addAtEnd(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// Display the list from end to head (backward)

15 | P a g e
void displayBackward() const {
Node* temp = tail;
if (temp == nullptr) {
cout << "List is empty." << endl;
return;
}
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
// Display the list from head to end
void displayForward() const {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
// Main function to test the doubly linked list implementation
int main() {
DoublyLinkedList dll;
dll.addAtEnd(10);
dll.addAtEnd(20);
dll.addAtEnd(30);
dll.addAtEnd(40);
dll.addAtEnd(50);
cout << "List (Forward): ";
dll.displayForward();
cout << "List (Backward): ";
dll.displayBackward();
return 0;
}

16 | P a g e