06.DOUBLY LINKED LIST
SYNTAX
template <class Type>
struct Node
{
Type info;
Node<Type> *prev, *next
};
DEFINITIONS
DOUBLY LINKED LIST
this is a linked list in which every node has a next pointer and a previous pointer
IMPLEMENTATION
UML
VISUALIZATION
SOURCE CODE
HEADER FILE: doublyLinkedList.h
template<class Type>
struct Node
{
Type info;
Node<Type> *prev, *next;
};
class DoublyLinkedList
{
int selfLength;
Node<Type> *selfFirst;
Node<Type> *selfLast;
public:
DoublyLinkedList(); //constructor
bool isEmpty();
int listSize();
const void print();
const void printReverse();
Type front();
Type back();
void insertFirst(const Type&);
void insertLast(const Type&);
bool search(const Type&);
void deleteNode(const Type&);
DoublyLinkedList(const DoublyLinkedList<Type>&);
void destroyList();
~DoublyLinkedList();
};HEADER FILE: doublyLinkedListImplementation.h
#include <assert.h>
#include "doublyLinkedList.h"
template<class Type>
DoublyLinkedList(){ //constructor
selfLength = 0; //represents the number of nodes
selfFirst = NULL; //points to the first node
selfLast = NULL; //points to the last node
}
template<class Type>
bool DoublyLinkedList<Type>::isEmpty(){
return selfLength == 0;
//return selfFirst == NULL; or return selfLast == NULL;
}
template<class Type>
int DoublyLinkedList<Type>::listSize(){
return selfLength;
}
template<class Type>
const void DoublyLinkedList<Type>::print(){
if (isEmpty())
cout << "The list is empty, nothing to print\n";
else{
Node<Type> *current = selfFirst;
while (current != NULL){
cout << current->info << " ";
current = current->next;
}
cout << "\n";
}
}
template<class Type>
const void DoublyLinkedList<Type>::printReverse(){
if (isEmpty())
cout << "The list is empty, nothing to print\n";
else{
Node<Type> *current = selfLast;
while (current != NULL){
cout << current->info << " ";
current = current->prev;
}
cout << "\n";
}
}
template<class Type>
Type DoublyLinkedList<Type>::front(){
assert(selfFirst != NULL);
return selfFirst->info;
}
template<class Type>
Type DoublyLinkedList<Type>::back(){
assert(selfFirst != NULL);
return selfLast->info;
}
template<class Type>
void DoublyLinkedList<Type>::insertFirst(const Type& varX){
Node<Type> *newNode;
newNode = new Node<Type>;
assert(newNode != NULL);
newNode->info = varX;
newNode->prev = NULL;
if (selfFirst == NULL){ //empty list
selfFirst = newNode;
selfLast = newNode;
newNode->next = NULL;
}
else{
newNode->next = selfFirst;
selfFirst->prev = newNode;
selfFirst = newNode;
}
selfLength++;
}
template<class Type>
void DoublyLinkedList<Type>::insertLast(const Type& varX){
Node<Type> *newNode;
newNode = new Node<Type>;
assert(newNode != NULL);
newNode->info = varX;
newNode-> = NULL;
if (selfLast == NULL){ //empty list
selfFirst = newNode;
selfLast = newNode;
newNode->prev = NULL;
}
else{
newNode->prev = selfLast;
selfLast->next = newNode;
selfLast = newNode;
}
selfLength++;
}
template<class Type>
bool DoublyLinkedList<Type>::search(const Type& varX){
Node<Type> *current;
current = selfFirst;
while (current != NULL)
if (current->info == varX)
return true;
else
current = current->next;
return false;
}
template<class Type>
void DoublyLinkedList<Type>::deleteNode(const Type& varX){
if (isEmpty())
cout << "Empty list. No node to be deleted\n";
else{
Node<Type> *current, *prevCurrent;
current = selfFirst;
prevCurrent = NULL;
while (current != NULL && current->info != varX){
prevCurrent = current;
current = current->next;
}
if (current == NULL)
cout << varX << " was not found in the linked list\n";
else{ //the linked list is not empty & x was found.
//linked list with only one node with info = varX
if (selfFirst == selfLast){
delete current;
selfFirst = NULL;
selfLast = NULL;
}
//a list w/ more than one node & the first node has info = varX
else if (current == selfFirst){
selfFirst = selfFirst->next;
selfFirst->prev = NULL;
delete current;
}
//a list w/ more than one node & only the last node has info = varX
else if (current == selfLast){
selfLast = prevCurrent;
selfLast->next = NULL;
delete current;
}
//The node to be deleted is after first & before last
else{
prevCurrent->next = current->next;
current-next->prev = prevCurrent;
delete current;
}
selfLength++;
}
}
}
//this is the copy constructor
template<class Type>
DoublyLinkedList<Type>::DoublyLinkedList(const DoublyLinkedList<Type>& otherList){
Node<Type> *current; //pointer to traverse the otherList
if (selfFirst != NULL)
destroyList();
current = otherList.selfFirst; //current points to the first node of otherList
while (current != NULL){
insertLast(current->info);
current = current->next;
}
selfLength = otherList.selfLength;
}
//removes all the nodes in the DoublyLinkedList
template<class Type>
void DoublyLinkedList<Type>::destroyList(){
Node<Type> *current;
while (selfFirst != NULL){
current = selfFirst;
selfFirst = selfFirst->next;
delete current;
}
selfLast = NULL;
selfLength = 0;
}
template<class Type>
DoublyLinkedList<Type>::~DoublyLinkedList(){
cout << "The list was destroyed\n";
destroyList();
}SOURCE FILE: doublyLinkedList.cpp
#include <iostream>
#include "doublyLinkedListImplementation.h"
using namespace std;
int main()
{
DoublyLinkedList<float> list;
list.insertLast(5.1);
list.insertLast(10.2);
list.insertLast(15.6);
list.insertLast(12.3);
list.insertLast(30.8);
list.insertLast(35.1);
list.insertLast(4.7);
list.insertLast(50.9);
list.insertLast(60.6);
list.print();
cout << "Is list sorted? " << list.isSortedList() << endl;
list.reverseNodes();
list.print();
//palindrome is a word, sentence, verse, or numbers that reads the same backward or forward
//examples noon, civic, racecar, level, and mom
cout << "Is the list a palindrome? " << list.isPalindrome() << endl;
cout << "Number of big nodes: " << list.bigNodes() << endl;
/*
LinkedList<int> list; //create a list w/ default values as set by the constructor
list.insertFirst(10);
list.print();//10
list.deleteNode(10);
list.print();//Empty list
list.insertFirst(10);
list.insertFirst(20);
list.insertFirst(30);
list.insertFirst(40);
list.print();//40 30 20 10
list.deleteNode(40);
list.print();//30 20 10
LinkedList<int> list2(list);
list2.print();
cout << list2.search(20)<<"\n";
*/
/*
//cout << list.front() << "\n";//40
cout << list.isEmpty() << "\n"; //0
cout << list.listSize() << "\n";//4
list.print();//40 30 20 10
list.insertLast(-1);
list.print();//40 30 20 10 -1
cout << list.search(100) << "\n"; //0
list.destroyList();
*/
return 0;
}Last updated