blog
blog copied to clipboard
Published
20 hours ago •
Qingquan-Li
Qingquan-Li
Doubly Linked List Demo Program
Another demonstration: https://github.com/Qingquan-Li/DoublyLinkedListDemo
Reference: Book: Data Structures Using C++ (Second Edition, D.S. Malik)
A doubly linked list is a linked list in which every node has a next pointer and a back pointer. In other words, every node contains the address of the next node (except the last node), and every node contains the address of the previous node (except the first node).
A doubly linked list can be traversed in either direction. That is, we can traverse the list starting at the first node or, if a pointer to the last node is given, we can traverse the list starting at the last node.
The typical operations on a doubly linked list are as follows: Initialize the list, destroy the list, determine whether the list is empty, search the list for a given item, insert an item, delete an item, and so on.
DoublyLinkedListDemo.h
#include <iostream>
using namespace std;
#ifndef DOUBLYLINKEDLISTDEMO_H
#define DOUBLYLINKEDLISTDEMO_H
// Definition of the node
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *next; //pointer to the next node of the doubly linked list
nodeType<Type> *back; //pointer to the previous node of the doubly linked list
};
//*********************************************************
// This class specifies the members to implement the basic
// properties of an ordered doubly linked list.
//*********************************************************
template <class Type>
class DoublyLinkedList
{
public:
DoublyLinkedList();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
DoublyLinkedList(const DoublyLinkedList<Type>& otherList);
//copy constructor
~DoublyLinkedList();
//destructor
//Postcondition: The list object is destroyed.
const DoublyLinkedList<Type>& operator=
(const DoublyLinkedList<Type>& otherList);
//Overload the assignment operator.
bool isEmptyList() const;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty,
// otherwise it returns false.
void destroy();
//Function to delete all the nodes from the list.
//Postcondition: first = NULL, last = NULL, count = 0;
void initializeList();
//Function to initialize the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
void print() const;
//Function to output the info contained in each node.
void reversePrint() const;
//Function to output the info contained in each node in reverse order.
int length() const;
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
Type front() const;
//Function to return the first element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program terminates;
// otherwise, the first element of the list is returned.
Type back() const;
//Function to return the last element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program terminates;
// otherwise, the last element of the list is returned.
bool search(const Type& searchItem) const;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found in the
// list, otherwise it returns false.
void insert(const Type& insertItem);
//Function to insert insertItem in the list.
//Precondition: If the list is nonempty, it must be in order.
//Postcondition: insertItem is inserted at the proper place
// in the list, first points to the first node,
// last points to the last node of the new list,
// and count is incremented by 1.
void deleteNode(const Type& deleteItem);
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing deleteItem is
// deleted from the list; first points to the
// first node of the new list, last points to
// the last node of the new list, and count is
// decremented by 1; otherwise an appropriate
// message is printed.
protected:
int count;
nodeType<Type> *first; //pointer to the first node
nodeType<Type> *last; //pointer to the last node
private:
void copyList(const DoublyLinkedList<Type>& otherList);
//Function to make a copy of otherList.
//It is used only to implement the copy constructor
//and overload the assignment operator.
//Postcondition: A copy of otherList is created and assigned
// to this list.
};
#endif
DoublyLinkedListDemo.cpp
#include "DoublyLinkedListDemo.h"
/**
* Default constructor
* Initializes the list to an empty state.
* It sets the first and last pointers to NULL and the count to 0.
* @tparam Type
*/
template <class Type>
DoublyLinkedList<Type>::DoublyLinkedList()
{
first = NULL;
last = NULL;
count = 0;
}
/**
* Copy constructor
* Initializes the list to a copy of the otherList.
* @tparam Type
* @param otherList
*/
template <class Type>
DoublyLinkedList<Type>::DoublyLinkedList(const DoublyLinkedList<Type>& otherList)
{
first = NULL;
copyList(otherList);
}
/**
* Destructor
* Deletes all the nodes from the list.
* @tparam Type
*/
template <class Type>
DoublyLinkedList<Type>::~DoublyLinkedList()
{
destroy();
}
/**
* Overload the assignment operator.
* @tparam Type
* @param otherList
* @return a reference to the current object of type DoublyLinkedList.
* @postcondition: After the assignment, the list becomes a copy of otherList.
*/
template <class Type>
const DoublyLinkedList<Type>& DoublyLinkedList<Type>::operator=
(const DoublyLinkedList<Type>& otherList)
{
if (this != &otherList) //avoid self-copy.
//checks if the current object's address (this) is
//different from the address of otherList.
//this is a special pointer that points to the
//object for which a member function is called.
{
//destroy(); //if the list is not empty, destroy it
copyList(otherList);
}
//Return a reference to the current object.
//The `this` pointer points to the object on which the member function is called.
//When you dereference a pointer, you get the actual value or object that it's pointing to.
//When you dereference `this` using `*this`, you get the current object itself.
//Objects (like *this) can be used to initialize or assign to references.
return *this;
}
/**
* Function to determine whether the list is empty.
* @tparam Type
* @return true if the list is empty, otherwise it returns false.
*/
template <class Type>
bool DoublyLinkedList<Type>::isEmptyList() const
{
return (first == NULL);
}
/**
* Function to destroy all the nodes in the list,
* leaves the list in an empty state.
* Traverse the list starting at the first node and
* delete each node. Furthermore, count is set to 0.
* @tparam Type
* @return void
*/
template <class Type>
void DoublyLinkedList<Type>::destroy()
{
nodeType<Type> *temp; //pointer to delete the node
while (first != NULL) //while there are nodes in the list
{
temp = first; //set temp to the current node
first = first->next; //advance first to the next node
delete temp; //deallocate the memory occupied by temp
}
last = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
/**
* Function to initialize the list to an empty state.
* It can be done by calling the operation destroy.
* @tparam Type
* @return void
*/
template <class Type>
void DoublyLinkedList<Type>::initializeList()
{
destroy();
}
/**
* Function to output the info contained in each node.
* @tparam Type
* @return void
*/
template <class Type>
void DoublyLinkedList<Type>::print() const
{
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current to point to the first node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->next;
}
}
/**
* Function to output the info contained in each node in reverse order.
* @tparam Type
* @return void
*/
template <class Type>
void DoublyLinkedList<Type>::reversePrint() const
{
nodeType<Type> *current; //pointer to traverse the list
current = last; //set current to point to the last node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->back;
}
}
/**
* Function to return the number of nodes in the list.
* The length of the list is stored in the member variable count.
* @tparam Type
* @return int
*/
template <class Type>
int DoublyLinkedList<Type>::length() const
{
return count;
}
/**
* Function to return the first element of the list.
* @tparam Type
* @return Type
*/
template <class Type>
Type DoublyLinkedList<Type>::front() const
{
assert(first != NULL); //if the list is not empty, assert does nothing
//if the list is empty, terminate the program
return first->info; //return the info of the first node
}
/**
* Function to return the last element of the list.
* @tparam Type
* @return Type
*/
template <class Type>
Type DoublyLinkedList<Type>::back() const
{
assert(last != NULL); //if the list is not empty, assert does nothing
//if the list is empty, terminate the program
return last->info; //return the info of the last node
}
/**
* Function to determine whether searchItem is in the list.
* @tparam Type
* @param searchItem
* @return true if searchItem is found in the list, otherwise it returns false.
*/
template <class Type>
bool DoublyLinkedList<Type>::search(const Type& searchItem) const
{
bool found = false;
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current to point to the first node
while (current != NULL && !found) //search the list
if (current->info == searchItem) //searchItem is found
found = true;
else
current = current->next; //make current point to
//the next node
return found;
}
/**
* Function to insert insertItem in the list.
* Case 1: Insertion in an empty list.
* Case 2: Insertion at the beginning of a nonempty list.
* Case 3: Insertion at the end of a nonempty list.
* Case 4: Insertion in the middle of a nonempty list.
* Both cases 1 and 2 require to change the value of the pointer first.
* Cases 3 and 4 are similar.
* @tparam Type
* @param insertItem
* @return void
*/
template <class Type>
void DoublyLinkedList<Type>::insert(const Type& insertItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
nodeType<Type> *newNode; //pointer to create a node
bool found;
newNode = new nodeType<Type>; //create the node
newNode->info = insertItem; //store the new item in the node
newNode->next = NULL; //set the next field of the node to NULL
newNode->back = NULL; //set the back field of the node to NULL
if (first == NULL) //Case 1
{
first = newNode;
last = newNode;
count++;
}
else
{
found = false;
current = first;
while (current != NULL && !found) //search the list to find the
//insertion point
{
if (current->info >= insertItem) //the list is sorted in ascending order
found = true;
else
{
trailCurrent = current;
current = current->next; //advance current pointer
}
}
if (current == first) //Case 2
{
first->back = newNode;
newNode->next = first;
first = newNode;
count++;
}
else //Case 3 and 4
{
if (current != NULL) //Case 4
{
// insert newNode between trailCurrent and current
trailCurrent->next = newNode; //insert newNode before current
newNode->back = trailCurrent; //set back link of newNode
newNode->next = current; //set next link of newNode
current->back = newNode; //set back link of current
}
else //Case 3
{
trailCurrent->next = newNode;
newNode->back = trailCurrent;
last = newNode;
}
count++;
} //end else
} //end else
} //end insert
/**
* Function to delete deleteItem from the list.
* Case 1: The list is empty.
* Case 2: The node to be deleted is the first node, which would require
* us to change the value of the pointer first.
* Case 3: The node to be deleted is somewhere in the list, could be the
* last node, or somewhere in the middle.
* Case 4: The node to be deleted is not in the list.
* @tparam Type
* @param deleteItem
* @return void
*/
template <class Type>
void DoublyLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1
cout << "Cannot delete from an empty list." << endl;
else if (first->info == deleteItem) //Case 2
{
current = first;
first = first->next;
if (first != NULL)
first->back = NULL;
else
last = NULL;
count--; //decrement the count (length of the list)
delete current; //delete the node
}
else //Case 3 and 4
{
found = false;
current = first; //set current to point to the first node
while (current != NULL && !found) //search the list to find the node
{
if (current->info >= deleteItem)
found = true;
else
current = current->next;
}
if (current == NULL) //Case4. current->info > last->info
cout << "The item to be deleted is not in the list." << endl;
else if (current->info == deleteItem) //Case 3
{
trailCurrent = current->back; //set trailCurrent to point
//to the node before current
trailCurrent->next = current->next; //link the previous node with the node
//following current
if (current->next != NULL)
current->next->back = trailCurrent; //link the node following current
//with the node before current
if (current == last)
last = trailCurrent; //set last to point to the new last node (trailCurrent)
count--; //decrement the count (length of the list)
delete current; //delete the node from the list
}
else //Case 4. current->info > deleteItem, but current->info != deleteItem
cout << "The item to be deleted is not in the list." << endl;
} //end else
} //end deleteNode
/**
* Function to make a copy of otherList.
*/
template <class Type>
void DoublyLinkedList<Type>::copyList(const DoublyLinkedList<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if (first != NULL) //if the list is nonempty, make it empty
destroy();
if (otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType<Type>; //create the node
first->info = current->info; //copy the info
first->next = NULL; //set the link field of
//the node to NULL
first->back = NULL; //set the back field of
//the node to NULL
last = first; //make last point to the
//first node
current = current->next; //make current point to
//the next node
//copy the remaining list
while (current != NULL)
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info; //copy the info
newNode->next = NULL; //set the link of
//newNode to NULL
newNode->back = last; //set the back of
//newNode to last
last->next = newNode; //attach newNode after last
last = newNode; //make last point to
//the actual last node
current = current->next; //make current point
//to the next node
} //end while
} //end else
} //end copyList
main.cpp
#include "DoublyLinkedListDemo.cpp"
//=====================================================================================
// Write a menu-driven program to test all the functions of the DoublyLinkedList class.
// The program should have the following menu:
// Welcome to the Doubly Linked List Demo Program!
// 1. Create a list
// 2. Print the list
// 3. Reverse print the list
// 4. Search the list
// 5. Insert an item into the list
// 6. Delete an item from the list
// 7. Destroy the list
// 8. Exit
// Enter your choice:
//=====================================================================================
int main()
{
DoublyLinkedList<int> list; //Instantiate a DoublyLinkedList object (list)
//of type int using the default constructor
int choice;
int num;
int item;
cout << "Welcome to the Doubly Linked List Demo Program!" << endl;
do
{
cout << "1. Create a list" << endl;
cout << "2. Print the list" << endl;
cout << "3. Reverse print the list" << endl;
cout << "4. Search the list" << endl;
cout << "5. Insert an item into the list" << endl;
cout << "6. Delete an item from the list" << endl;
cout << "7. Destroy the list" << endl;
cout << "8. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;
cout << endl;
switch (choice)
{
case 1:
cout << "How many integers do you want to add to the list: ";
cin >> num;
cout << endl;
for (int i = 0; i < num; i++)
{
cout << "Enter #" << i + 1 << " integer: ";
cin >> item;
list.insert(item);
}
break;
case 2:
cout << "The list is: ";
list.print();
cout << endl;
break;
case 3:
cout << "The list in reverse order is: ";
list.reversePrint();
cout << endl;
break;
case 4:
cout << "Enter an integer to be searched in the list: ";
cin >> item;
cout << endl;
if (list.search(item))
cout << item << " is found in the list." << endl;
else
cout << item << " is not found in the list." << endl;
break;
case 5:
cout << "Enter an integer to be inserted into the list: ";
cin >> item;
cout << endl;
list.insert(item);
break;
case 6:
cout << "Enter an integer to be deleted from the list: ";
cin >> item;
cout << endl;
list.deleteNode(item);
break;
case 7:
list.destroy();
break;
case 8:
cout << "Exiting the program..." << endl;
break;
default:
cout << "Invalid choice." << endl;
}
} while (choice != 8);
return 0;
}
Compile, Run and Output
path/to/DoublyLinkedListDemo $ g++ -std=c++11 main.cpp -o DoublyLinkedListDemo
path/to/DoublyLinkedListDemo $ ./DoublyLinkedListDemo
Welcome to the Doubly Linked List Demo Program!
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 1
How many integers do you want to add to the list: 3
Enter #1 integer: 10
Enter #2 integer: 30
Enter #3 integer: 20
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 2
The list is: 10 20 30
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 3
The list in reverse order is: 30 20 10
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 4
Enter an integer to be searched in the list: 10
10 is found in the list.
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 5
Enter an integer to be inserted into the list: 25
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 2
The list is: 10 20 25 30
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 6
Enter an integer to be deleted from the list: 20
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 2
The list is: 10 25 30
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 7
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 2
The list is:
1. Create a list
2. Print the list
3. Reverse print the list
4. Search the list
5. Insert an item into the list
6. Delete an item from the list
7. Destroy the list
8. Exit
Enter your choice: 8
Exiting the program...
