C++: Create a Template Linked List Base Class and a Set of Specific Classes that Inherit from it

  1. Home
  2. Homework Library
  3. Computer Science
  4. C-Family Programming
  5. C++: Create a Template Linked List Base Class and a Set of Specific Classes that Inherit from it
Subject Computer Science C-Family Programming

Question

Your task is to create a template Linked List base class and a set of specific classes that inherit from it.
In addition to the classes, you will implement a set of tests in your main to prove the functionality of the classes.
Each class should be implemented as a header .h file and a source code .cpp file (e.g. Stack.h and Stack.cpp).
You also need a test program main.cpp for testing.
Task 1
In this task you will implement the template LinkedListNode class with:
A pointer to a generic data member.
A next pointer to the next node in the linked list.
Any needed accessors and functions.

Task 2
In this task you will implement the template Linked List class.
This class will implement all of the Linked List parsing, inserting, deleting, etc.
1. Implement the LinkedList class with at least the following private fields and functions:
A pointer to the head of the list.
It will be a LinkedListNode pointer.
A count of the total nodes in the list.

2. Implement the following protected functions:
An ‘int insert(T* pItem, int pos = -1)’ function for adding to the list.
The function should add ‘pItem’ to the list at position ‘pos’.
The position intidicates where in the list the item is.
A position of 0 indicates the item is at the head of the list.
If a negative position, or a position greater than the current list size, is passed into the function, then the item should be placed at the end of the list.
The function will always return the position of the added item.
An ‘LinkedListNode* at(int pos)’ function for retrieving a node at a specific position.
A ‘T* removeAt(int pos)’ function for removing a node at a specific position.
The function will find the node, delete the node , and return the generic data it stored.
A ‘LinkedListNode* find(T* pItem)’ function for finding a specific item in the list.
It should search the list and return the node if found.
A ‘clear()’ function for emptying the list.
The function must use recursion.
This function must properly delete all memory.

Implement the following public functions:
The ‘getSize()’ function for obtaining the number of nodes in the list.
The ‘begin()’ function for getting a pointer to the head of the list.
A T* at(int pos)’ function for retrieving a node at a specific position.
A ‘operator++’ function for iteration.
This function will update the node pointer to the ‘next’ variable.

3. Implement a destructor that will properly clean up all memory when the structure is destructed.
You may also add other functions and variables as needed.

Task 3
In this task you will implement the template Queue class which inherits from the LinkedList class.
A Queue is a First In First Out container (Think of the line a grocery store. The first item in should be the first item removed.)
The Queue class has the following public functions:
A ‘T* pop()’ function.
It will remove the first item in the list and return it.
A virtual ‘void push(T* pItem)’ function.
It will add an element to the end of the list.
You may add other functions and variables as needed.

Task 4
In this task you will implement the template OrderedQueue class.
This class should inherit from the Queue class.
The class is similar to a Queue except that items are inserted in order and removed in order.
For example, if 1, 2, then 3 were inserted, then the removal process would result in 1, 2, then 3.
If 1, 3, then 2 was inserted the removal process would result in 1, 2, then 3 because 2 would have been inserted before 3.
The OrderedQueue class has a 'void push(T* pItem)' function.
It will push the newly added item into the appropriate location in the queue.
It will use the < operator for comparison.
You may add any other functions and variable as needed.

Task 5
In this task you will implement a template Stack class.
This class should inherit from the LinkedList class.
You will remember from the previous assignment that a Stack is a First In Last Out container.
For example, if 1, 2, then 3 were inserted then the removal process would result in 3, 2, then 1.
The Stack class has the following public functions:
A 'void push(T* pItem)’ function. It will push an item onto the top of the stack.
A 'T* pop()' function. It will remove an item from the top of the stack.
A ‘T* top()’ function. It will return a pointer to the item at the top of the list, but will NOT remove it from the list.

Task 6
You need to write a test program which creates an instance of each class type and tests all functions of those classes.
Extra Credit
For the extra credit you must implement all of the tasks above, add a previous pointer to the node class, and update all classes to support backwards parsing.
The detailed tasks are:
Update the LinkedListNode class by adding a private previous pointer.
Update the LinkedList class by:
1) adding a private tail pointer for reverse iteration,
2) adding an ‘end’ function for getting the last node in the list,
3) modifying the 'insert' function to use the tail pointer for insertion at the end of the list.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include <cstdlib>
#include <iostream>

#include "LinkedListNode.h"
#include "LinkedList.h"
#include "Queue.h"
#include "OrderedQueue.h"
#include "Stack.h"
using namespace std;

/*
*
*/
int main(int argc, char** argv) {

    cout<<"Test Queue\n";
    Queue<int> * queue = new Queue<int>();   
    cout<<"Enter number: ";
    for (int i = 0; i < 10; i++) {
       int * t = new int;
       *t = i;
       queue->push(t);
       cout<<i<<" ";
    }
    int * num;
    cout<<"\n Content of queue: ";
    for (int i = 0; i < 10; i++) {
       num = queue->at(i);
       cout<<*num<<" ";
    }

    cout<<"\nDequeue: ";
    while (!queue->empty()) {
       num = queue->pop();
       cout<<*num<<" ";
    }

   
    cout<<"\n\nTest OrderedQueue\n";
    OrderedQueue<int> * oQueue = new OrderedQueue<int>();   
    cout<<"Enter number: ";
    for (int i = 10; i > 0; i--) {
       int * t = new int;
       *t = i;
       oQueue->push(t);
       cout<<i<<" ";
    }
    cout<<"\n Content of ordered queue: ";
    for (int i = 0; i < 10; i++) {
       num = oQueue->at(i);
       cout<<*num<<" ";
    }
    cout<<"\nDequeue: ";
    while (!oQueue->empty()) {
       num = oQueue->pop();
       cout<<*num<<" ";
    }
   
    cout<<"\n\nTest Stack\n";
    Stack<int> * stack = new Stack<int>();   
    cout<<"Enter number: ";
    for (int i = 10; i > 0; i--) {
       int * t = new int;
       *t = i;
       stack->push(t);
       cout<<i<<" ";
    }
    cout<<"\n Content of stack: ";
    for (int i = 0; i < 10; i++) {
       num = stack->at(i);
       cout<<*num<<" ";
    }
    cout<<"\nPop: ";
    while (!stack->empty()) {
       num = stack->top();
       stack->pop();
       cout<<*num<<" ";
    }
   
    return 0;
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

$60.00

or $1 if you
register a new account!

Assisting Tutor

Related Homework Solutions

Get help from a qualified tutor
Live Chats