Description
In this project, you will implement a linked list class that includes a member func-tion to reverse the encapsulated list in-place. The in-place constraint means that you are prohibited from copying the encapsulated list into any additional storage containers, such as a stack, during the course of the function’s run. Although using additional stor-age containers can help simplify the reversal process, they unnecessarily waste space. Instead, you will use pointer manipulation to reorder the existing list. Consequently, the overall space complexity of your reversal algorithm will be constant O(1).
The header for both the linked list class and the list node structure is outlined below.
template <typename T>
class LinkedList {
public:
LinkedList() : head(NULL) {}
~LinkedList();
void push_front(const T data);
void pop_front();
void reverse();
void print() const;
private:
struct ListNode {
ListNode(const T data) : data(data), next(NULL) {}
-
data; ListNode* next;
};
ListNode* head;
};
You must write the de nitions for the functions push front, pop front, reverse, print, and ~LinkedList. The linked list constructor is already written as an initializer list. For those of you not familiar with initializer lists, head(NULL) is equivalent to writing head = NULL inside the brackets of the constructor de nition. An initializer list is also used for the ListNode struct to set the member variable data to a user de ned input and the next pointer to NULL. An example of its use is shown in the following code snippet:
ListNode* node = new ListNode(2);
cout << node->data << “, ” << node->next << endl; delete node;
The new command calls the ListNode constructor, which initializes data to the integer 2 (assuming the template type T is set to int) and next to NULL. Thus, the output of the code above will be:
2, 0
Input
Input commands are read from the keyboard. Your program must continue to check for input until the quit command is issued. The accepted input commands are listed as follows:
-
i : Add the integer i to the front of the list. (push front)
d : Delete the rst element of the list. (pop front)
r : Reverse the list.
p : Print the data value of each node in the list.
q : Quit the program.
Although your linked list class will be templated, your program will only be tested on integer data. The test suite used for grading will not contain data of any other type, so it is not necessary for you to verify the type of the input data.
Output
Print the results of the p command on one line using space as a delimiter. If the list is empty when issuing any of the commands d, p, or r, output the message Empty. Do not worry about verifying the input format.
Sample Test Case
Use input redirection to redirect commands written in a le to the standard input, e.g.
$ ./a.out < input1.dat.
Input 1
-
1
-
2
-
3
p r d
p
q
Output 1
3 2 1
2 3
Turn In
Email your source code to yy471014@ohio.edu with the subject \CS3610 Project 1″. Please make sure to use this exact wording, otherwise your email/submission may be overlooked. If you have multiple les, package them into a zip le.
An Implementation Issue
The LinkedList class is declared in linked list.h. You may ask \should I put the de ni-tions of the functions into a separate source le, say, linked list.cc?” The answer would be complicated when a template class is involved, as in this project. Some explanations
can be found in https://www.codeproject.com/Articles/48575/How-to-define-a-template-cla and https://www.experts-exchange.com/articles/1199/Separating-C-template-declaration html. An easy solution would be just putting your implementations in the same header le linked list.h.
Grading
Total: 100 pts.
10/100 – Code style, commenting, general readability. 05/100 – Compiles.
05/100 – Follows provided input and output format.
80/100 – Successful implementation of the 5 requested linked list functions.
3
