Doubly Linked List
#include "DoublyLinkedList.h"
int main() {
DoublyLL list;
list.insert(1);
list.insert(2);
list.insertAtHead(3);
list.insertAtHead(4);
list.insertAtHead(5);
cout << "Main List: " << list << endl;
cout << "Given Node Data Present: " << boolalpha << list.search(1) << endl << endl;
int temp;
cout << "Head Removed: " << boolalpha << list.removeHead(temp) << endl;
cout << "Deleted Head Node Element: " << temp << endl;
cout << list << endl;
cout << "Tail Node Removed: " << boolalpha << list.remove(2) << endl;
cout << list << endl;
cout << "Random Node Removed: " << boolalpha << list.remove(3) << endl;
cout << list << endl;
// --> There are some bugs in clear functions
// list.clear();
// cout << "List is Empty: " << boolalpha << list.isEmpty() << endl;
// --> checking assignment & copy constructor
// DoublyLL list1;
// list1.insert(1);
// list1.insert(2);
// list1.insertAtHead(3);
// list1.insertAtHead(4);
// cout << list1 << endl;
// DoublyLL list2;
// list2.insert(5);
// list2.insert(6);
// list2.insertAtHead(7);
// list2.insertAtHead(8);
// list2.insertAtHead(9);
// list1.Swap(list2);
// cout << "List1: " << list1 << endl << "List2: " << list2 << endl;
// DoublyLL list(list1);
// list1.insertAtHead(10);
// cout << "Values of list1 copied into list using copy constructor! \n" << list << endl;
// DoublyLL assignmentList1, assignmentList2;
// assignmentList1 = assignmentList2 = list1;
// list2.insertAtHead(20);
// cout << "Values of list2 copied into assignmentList1 & assignmentList2 using Assignment operator! \n" << assignmentList1 << endl << assignmentList2;
}#include <iostream>
#pragma once
using namespace std;
class Node{
public:
int data;
Node* next;
Node* prev;
Node(const int data) {
this -> data = data;
next = nullptr;
prev = nullptr;
}
// important
~Node () {
next = nullptr;
prev = nullptr;
delete next;
delete prev;
}
};
class DoublyLL {
Node* head;
Node* tail;
int elements;
public:
DoublyLL() : head(nullptr), tail(nullptr), elements(0) {};
DoublyLL(const DoublyLL& list);
DoublyLL& operator= (const DoublyLL& list);
void insert(const int val);
void insertAtHead(const int val);
bool search(const int val);
bool remove(const int val);
bool removeHead(int& headData);
void clear();
bool isEmpty() {
return elements == 0;
}
void Swap(DoublyLL& list2);
friend ostream& operator<< (ostream& os, const DoublyLL& list);
};
DoublyLL :: DoublyLL(const DoublyLL& list) {
Node* listHead = list.head;
Node* listTail = list.tail;
Node* newNode = new Node(listHead->data);
listHead = listHead -> next;
head = tail = newNode;
while (listHead != nullptr) {
Node* temp = new Node (listHead -> data);
listHead = listHead -> next;
tail -> next = temp;
temp -> prev = tail;
tail = temp;
}
elements = list.elements;
}
DoublyLL& DoublyLL :: operator= (const DoublyLL& list) {
if(this == &list) return *this;
delete head;
delete tail;
Node* listHead = list.head;
Node* lsitTail = list.tail;
Node* newNode = new Node(listHead -> data);
listHead = listHead -> next;
head = tail = newNode;
while(listHead != nullptr) {
Node* temp = new Node(listHead -> data);
tail -> next = temp;
temp -> prev = tail;
tail = temp;
listHead = listHead -> next;
}
elements = list.elements;
return *this;
}
ostream& operator<< (ostream& os, const DoublyLL& list) {
Node* cur = list.head;
while (cur != nullptr) {
os << cur -> data << " ";
cur = cur -> next;
} os << endl;
os << "Head Data: " << list.head -> data << endl;
cout << "Tail Data: " << list.tail -> data << endl;
cout << "Size: " << list.elements << endl;
return os;
}
void DoublyLL :: insert(const int val) {
if(head == nullptr) {
insertAtHead(val);
return;
}
Node* newNode = new Node(val);
tail -> next = newNode;
newNode -> prev = tail;
tail = newNode;
elements++;
}
void DoublyLL :: insertAtHead(const int val) {
if(head == nullptr) {
Node* newNode = new Node(val);
head = tail = newNode;
}
else {
Node* newNode = new Node(val);
newNode -> next = head;
head -> prev = newNode;
head = newNode;
}
elements++;
}
bool DoublyLL :: search(const int val) {
Node* cur = head;
while (cur != nullptr) {
if(cur -> data == val) return true;
cur = cur -> next;
}
return false;
}
bool DoublyLL :: remove(const int val) {
Node* pre = nullptr;
Node* cur = head;
// if the given val is equal to the head node data then do removeHead.
if(head -> data == val) {
head = head -> next;
head -> prev = nullptr;
cur -> next = nullptr;
delete cur;
elements--;
return true;
}
// condition for other Node's data
else{
// iterate till 2nd last node
while (cur -> next != nullptr) {
if(cur -> data == val) {
pre -> next = cur -> next;
cur -> next -> prev = pre;
elements--;
delete cur;
return true;
}
pre = cur;
cur = cur -> next;
}
//Condition for deleting tail Node
// imp --> cur is at tail node
tail = pre;
tail -> next = nullptr; // or tail -> next = cur -> next;
elements--;
delete cur;
return true;
}
return false;
}
bool DoublyLL :: removeHead(int& headData) {
if(head == nullptr) {
headData = -1;
return false;
}
Node* cur = head;
headData = head -> data;
head = head -> next;
elements--;
delete cur;
return true;
}
void DoublyLL :: clear() {
if(head == nullptr) {
tail -> prev = nullptr;
return;
}
Node* cur = head;
head = head -> next;
head -> prev = nullptr;
clear();
delete cur;
// while (head != nullptr) {
// Node* cur = head;
// head = head -> next;
// head -> prev = nullptr;
// // condition for when head -> next equal to the next of tail Node which is nullptr;
// if(head -> next == tail -> next) {
// tail -> next = nullptr;
// tail -> prev = nullptr;
// }
// // Destructor of cur will automatically done this
// // cur -> next = nullptr;
// // cur -> prev = nullptr;
// elements--;
// delete cur;
// }
}
void DoublyLL :: Swap(DoublyLL& list2) {
// store the head and tail of list1 in tempHead & tempTail
Node* tempHead = head;
Node* tempTail = tail;
// Pointing the head & tail of list 1 to list 2 head & tail
head = list2.head;
tail = list2.tail;
list2.head = tempHead;
list2.tail = tempTail;
int temp = elements;
elements = list2.elements;
list2.elements = temp;
}Last updated
Was this helpful?