linked list based stack and queue implementations

Question

Created a linked-list based queue and stack. I was required to use my Dlist implementation when coding the queue and stack.

/*
 * Linkedlist.h
 *
 * Created on: Jul 12, 2022
 * Author: nick
 */
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <cstdlib>
#include <iostream>
using namespace std;
template <typename T>
class Node
{
public:
 T data;
 // introduce a 'next' node for doubly linked list
 Node<T>* next;
 Node<T>* prev;
 Node<T>() { prev = NULL; next = NULL; data = 0; }
 Node<T>(T t) { prev = NULL; next = NULL; data = t; }
};
// Convert Singly Linked List to Doubly Linked List
template <typename T>
class DList
{
public:
 Node<T>* head;
 Node<T>* tail;
 // introduce 'head' node for double link
 DList() { head = NULL; tail = NULL; } // default constructor
 // appends to tail of list
 void Append(T data)
 {
 Node<T>* pdata = new Node<T>(data);
 if (tail == NULL)
 {
 tail = pdata;
 head = pdata;
 }
 else
 {
 pdata->prev = tail;
 tail->next = pdata;
 tail = pdata;
 }
 }
 // prepends to head of list
 void Prepend(T data)
 {
 //
 Node<T>* pdata = new Node<T>(data);
 if (head == NULL)
 {
 head = pdata;
 tail = pdata;
 }
 else
 {
 pdata->next = head;
 head->prev = pdata;
 head = pdata;
 }
 }
 // inserts data after found data
 void InsertAfter(T find, T data)
 {
 //
 Node<T>* pdata = new Node<T>(data);
 Node<T>* temp = head;
 // traverse to find the location to insert data
 while( temp->next != NULL) {
 if (temp->data == find) {
 pdata->next = temp->next;
 temp->next = pdata;
 pdata->prev = temp;
 pdata->next->prev = pdata;
 return;
 }
 temp = temp->next;
 }
 if (temp->data == find) {
 temp->next = pdata;
 pdata->prev = temp;
 tail = pdata;
 return;
 }
 // If we cannot find the data
 cout << "Data not found" << endl;
 }
 // inserts data before found data
 void InsertBefore(T find, T data)
 {
 //
 Node<T>* pdata = new Node<T>(data);
 Node<T>* prev_node;
 Node<T>* temp = head;
 // traverse to find the location to insert data
 if (temp != NULL && temp->data == find){
 pdata->next = temp;
 temp->prev = pdata;
 head=pdata;
 }
 while( temp != NULL) {
 if (temp->data == find) {
 prev_node = temp->prev;
 pdata->next = temp;
 prev_node->next = pdata;
 pdata->prev = prev_node;
 temp->prev = pdata;
 return;
 }
 temp = temp->next;
 }
 // If we cannot find the data
 cout << "Data not found" << endl;
 }
 // finds data node and returns it
 Node<T>* Search(T data)
 {
 //
 Node<T>* temp = head;
 // traverse to find the location to insert data
 while( temp != NULL) {
 if (temp->data == data) {
 cout << "Found the node with data: " << temp->data << "\n";
 return temp;
 }
 temp = temp->next;
 }
 // If we cannot find the data
 cout << "Data not found" << endl;
 return NULL;
 }
 // deletes a node from the list
 void Delete(T data)
 {
 //
 Node<T>* temp = head;
 Node<T>* prev_node;
 if (temp != NULL && temp->data == data){
 head = temp->next;
 free(temp);
 return;
 }
 // traverse to find the location to insert data
 while( temp != NULL) {
 if (temp->data == data) {
 prev_node = temp->prev;
 prev_node->next = temp->next;
 if (temp != tail){
 (temp->next)->prev = prev_node;
 }
 else {
 tail = prev_node;
 }
 free(temp);
 return;
 }
 temp = temp->next;
 }
 // If we cannot find the data
 cout << "Data not found" << endl;
 }
 // remove tail
 void DeleteTail(){
 if (tail != NULL & tail != head) {
 Node<T>* temp = tail;
 Node<T>* prev_node;
 prev_node = temp->prev;
 prev_node->next = temp->next;
 tail = prev_node;
 free(temp);
 return;
 }
 if (tail == head){
 head = NULL;
 tail = NULL;
 return;
 }
 }
 // remove head
 void DeleteHead(){
 if (head != NULL & head != tail) {
 Node<T>* temp = head;
 head = temp->next;
 free(temp);
 return;
 }
 if (head==tail){
 head=NULL;
 tail=NULL;
 return;
 }
 }
 // retrieve head
 T RetrieveHead(){
 if (head != NULL) {
 return head->data;
 }
 // return 0 if empty
 return 0;
 }
 // retrieve tail
 T RetrieveTail(){
 if (tail != NULL){
 return tail->data;
 }
 // return 0 if empty
 return 0;
 }
 // returns number of nodes in list
 int Count()
 {
 //
 int index = 0;
 Node<T>* temp = head;
 // traverse to find the location to insert data
 while( temp != NULL) {
 temp = temp->next;
 index++;
 }
 return index;
 }
 // returns true if list is empty
 bool IsEmpty()
 {
 //
 if (head==NULL) {
 return true;
 }
 return false;
 }
 // prints list from tail of list
 void Output()
 {
 Node<T>* rover = tail;
 while (rover != NULL)
 {
 cout << rover->data << '\t';
 rover = rover->prev;
 }
 cout << endl;
 }
 // prints list from head
 void OutputFromHead()
 {
 Node<T>* rover = head;
 while (rover != NULL)
 {
 cout << rover->data << '\t';
 rover = rover->next;
 }
 cout << endl;
 }
 void PrintListRecursively(Node<T>* curr)
 {
 if (curr==NULL)
 {
 cout << "\t";
 return;
 }
 cout << curr->data << "\t";
 PrintListRecursively(curr->next);
 }
 void PrintRecursively(){
 PrintListRecursively(head);
 cout << endl;
 }
};
template<typename T>
class Stack : private DList<T> {
public:
 Stack() : DList<T>::DList() {
 }
 ~Stack() {
 }
 void Push(T data) {
 DList<T>::Prepend(data);
 }
 T Pop() {
 T temp = DList<T>::RetrieveHead();
 DList<T>::DeleteHead();
 return temp;
 }
 T Peek() {
 return DList<T>::RetrieveHead();
 }
 bool IsEmpty() {
 return DList<T>::IsEmpty();
 }
 int GetLength() {
 return DList<T>::Count();
 }
 void PrintStack(){
 DList<T>::OutputFromHead();
 }
};
template<typename T>
class Queue : private DList<T> {
public:
 Queue() : DList<T>::DList() {
 }
 ~Queue() {
 }
 void Push(T data) {
 DList<T>::Prepend(data);
 }
 T Pop() {
 T temp = DList<T>::RetrieveTail();
 DList<T>::DeleteTail();
 return temp;
 }
 T Peek() {
 return DList<T>::RetrieveTail();
 }
 bool IsEmpty() {
 return DList<T>::IsEmpty();
 }
 int GetLength() {
 return DList<T>::Count();
 }
 void PrintQueue(){
 DList<T>::OutputFromHead();
 }
};
//int main()
//{
// int count = 10;
// DList<int> list;
// for (int x = 0; x < count; x++)
// {
// int rnumber = rand() % 100 + 1;
// list.Append(rnumber);
// cout << rnumber << "\t";
// }
// cout << endl;
// list.Output();
//
// cout << list.Count() << "\n";
// list.InsertAfter(87, 111);
// list.InsertBefore(78,10);
// list.OutputFromHead();
// list.Search(11);
// cout << list.IsEmpty() << "\n";
// list.Delete(78);
// list.Prepend(271);
// list.OutputFromHead();
// list.DeleteHead();
// list.OutputFromHead();
// list.PrintRecursively();
//
// int count_stack = 5;
// Stack<int> stack;
// for (int x = 0; x < count_stack; x++)
// {
// int rnumber = rand() % 100 + 1;
// stack.Push(rnumber);
// cout << rnumber << "\t";
// }
// cout << endl;
// cout << stack.Peek() << "\n";
// cout << stack.GetLength() << "\n";
// cout << stack.Pop() << "\n";
// cout << stack.GetLength() << "\n";
// stack.PrintStack();
//
// int count_queue = 5;
// Queue<int> queue;
// for (int x = 0; x < count_queue; x++)
// {
// int rnumber = rand() % 100 + 1;
// queue.Push(rnumber);
// cout << rnumber << "\t";
// }
// cout << endl;
// cout << queue.Peek() << "\n";
// cout << queue.GetLength() << "\n";
// cout << queue.Pop() << "\n";
// cout << queue.GetLength() << "\n";
// queue.PrintQueue();
// return 0;
//}
#endif /* LINKEDLIST_H_ */

Curious to see if you have any suggestions on how to improve this. Also if there are any edge cases I missed, I'd like to know that too.

Answer 1

1. Never use using namespace std;.

   Fact is that std is simply not designed for importing. While including headers guarantees presence of specific symbols, there may be arbitrarily many more. Conflict is far too likely, and even if there is none on your system today, you might hit it when demonstrating.

2. Node<T> is an implementation-detail of DList<T>, and should thus be in there.

3. Learn to use in-class-initializers and mem-init-list. Assignment in the ctor-body is a poor substitute at best.

4. Respect the rule of 3/5/0. The implicit dtor, as well as copy-/move- ctor/assignment do the wrong thing for DList.

5. Minimize special cases. Packing the links into their own struct, having a member in DList and first in Node, allows you to always have a full loop, and only casting the link when you need the full Node, be it for accessing the value or deleting it.

6. You currently eschew move-semantics. That can be quite costly or even impossible, depending on the type.

7. As an aside, this is C++ not Java, thus a null pointer is false, and any non-null pointer is true.

8. Avoid NULL. nullptr is already a decade old, and much better for safety and overloading (thus also efficiency).

9. Add an iterator-interface so you can separate navigating nodes from adding / deleting / modifying / using them. This also allows you to keep all the details of your node-class to yourself, and opens up use of much generic code, like standard algorithms.

10. assert() (or abort() if the check should be retained) is for finding bugs, exceptions and error-codes for reporting errors. Library-code should not try to interact directly with the user, unless specifically requested.

11. Don't contribute to the std::endl fiasco. \n is the newline character, needless flushing flushes all pretense of performance down the drain.

12. Consider keeping the count handy instead of recounting when requested.

13. A comparison generally returns a perfectly servicable bool-value. It can be used directly, no need for cumbersome circumlocutions.

14. Give your test(s) their own file(s). No need to be stingy, or sabotage their use.

15. As an aside return 0; is implicit for main().