Doubly Linked List Assignment in windows Doubly Linked List is a data structure
ID: 3684240 • Letter: D
Question
Doubly Linked List Assignment in windows
Doubly Linked List is a data structure that holds a list of items with double links: previous and next. In this assignment, you need to implement all functions in the defined ListLinked class (prototype is provided by the instructor). Please read the comments and complete them using C++. You need to implement all of the ListLinked ADT functions in ListLinked.cpp file, and test them in main.cpp.
//--------------------------------------------------------------------
//
// Homework 3 ListLinked.h
//
// Class declaration for the Doubly linked implementation of the List ADT
//
//--------------------------------------------------------------------
#ifndef LISTLINKED_H
#define LISTLINKED_H
#include <iostream>
using namespace std;
template <typename DataType>
class ListNode { // doubly linked list node
public:
ListNode(const DataType& nodeData, ListNode* nextPtr, ListNode* prevPtr);
DataType dataItem;
ListNode* next;
ListNode* prev;
};
template <typename DataType>
class List { // a list implemented using doubly linked nodes
public:
List();
List(const List& other); // copy constructor
List& operator=(const List& other); // assignment operator
~List();
void insert(const DataType& newDataItem); // insert an item after cursor
void remove(); // remove the cursor node, and move the cursor to the next node. If the removed node is the last node, move the cursor to the beginning of the list
void replace(const DataType& newDataItem); // replace the cursor node value
void clear(); // clear the list, remove all nodes
bool isEmpty() const;
bool isFull() const;
void gotoBeginning(); // move cursor to the beginning of the list
void gotoEnd(); // move cursor to the end of the list
bool gotoNext(); // move cursor to the next node, return false if no next node is available
bool gotoPrior(); // move cursor to the prior node, return false if no prior node is available
DataType getCursor() const; // return the value of the cursor node
void moveToBeginning (); // move the cursor node to the beginning of the list
void insertBefore(const DataType& newDataItem); // insert a new item before the cursor
void print() const; // print the list, mark the cursor node
private: // Do not change them for this homework
ListNode<DataType>* head;
ListNode<DataType>* cursor;
};
#endif
//--------------------------------------------------------------------
template <typename DataType>
List<DataType>::List()
// Creates an empty list.
: head(0), cursor(0)
{
}
//--------------------------------------------------------------------
template <typename DataType>
List<DataType>::List(const List& other)
: head(0), cursor(0)
// Copy constructor. Creates a list which is equivalent in content
// to the "other" list.
{
operator=(other);
}
//--------------------------------------------------------------------
template <typename DataType>
List<DataType>& List<DataType>::operator=(const List& other)
// Overloaded assignment operator. Reinitializes the list to be
// equivalent in content to the "other" list.
// Note: we include self-assignment protection by checking whether
// "this" object is identical to the "other" object.
{
if( this != &other ) {
clear();
ListNode<DataType> *otherPtr = other.head;
ListNode<DataType> *holdCursor = NULL;
while( otherPtr != NULL ) {
insert(otherPtr->dataItem);
if(otherPtr == other.cursor) {
holdCursor = cursor;
}
otherPtr = otherPtr->next;
}
cursor = holdCursor;
}
return *this;
}
//--------------------------------------------------------------------
template <typename DataType>
List<DataType>::~List()
// Destructor. Frees the memory used by a list.
{
clear();
}
Explanation / Answer
main.cpp
#include <iostream>
#include "config.h"
#include "ListLinked.cpp"
using namespace std;
void print_help();
int main()
{
#if LAB5_TEST1
List<int> testList; // Test list
int testData; // List data item
#else
List<char> testList; // Test list
char testData; // List data item
#endif
char cmd; // Input command
print_help();
do
{
testList.showStructure(); // Output list
cout << endl << "Command: "; // Read command
cin >> cmd;
if ( cmd == '+' || cmd == '=' || cmd == '#' )
cin >> testData;
switch ( cmd )
{
case 'H' : case 'h':
print_help();
break;
case '+' : // insert
cout << "Insert " << testData << endl;
testList.insert(testData);
break;
case '-' : // remove
cout << "Remove the data item marked by the cursor"
<< endl;
testList.remove();
break;
case '=' : // replace
cout << "Replace the data item marked by the cursor "
<< "with " << testData << endl;
testList.replace(testData);
break;
case '@' : // getCursor
cout << "Element marked by the cursor is "
<< testList.getCursor() << endl;
break;
case '<' : // gotoBeginning
testList.gotoBeginning();
cout << "Go to the beginning of the list" << endl;
break;
case '>' : // gotoEnd
testList.gotoEnd();
cout << "Go to the end of the list" << endl;
break;
case 'N' : case 'n' : // gotoNext
if ( testList.gotoNext() )
cout << "Go to the next data item" << endl;
else
cout << "Failed -- either at the end of the list "
<< "or the list is empty" << endl;
break;
case 'P' : case 'p' : // gotoPrior
if ( testList.gotoPrior() )
cout << "Go to the prior data item" << endl;
else
cout << "Failed -- either at the beginning of the "
<< "list or the list is empty" << endl;
break;
case 'C' : case 'c' : // clear
cout << "Clear the list" << endl;
testList.clear();
break;
case 'E' : case 'e' : // empty
if ( testList.isEmpty() )
cout << "List is empty" << endl;
else
cout << "List is NOT empty" << endl;
break;
case 'F' : case 'f' : // full
if ( testList.isFull() )
cout << "List is full" << endl;
else
cout << "List is NOT full" << endl;
break;
#if LAB5_TEST2
case 'M' : case 'm' : // In-lab Exercise 2
cout << "Move the data item marked by the cursor to the "
<< "beginning of the list" << endl;
testList.moveToBeginning();
break;
#endif
#if LAB5_TEST3
case '#' : // In-lab Exercise 3
cout << "Insert " << testData << " before the "
<< "cursor" << endl;
testList.insertBefore(testData);
break;
#endif
case 'Q' : case 'q' : // Quit test program
break;
default : // Invalid command
cout << "Inactive or invalid command" << endl;
}
}
while ( cin && cmd != 'Q' && cmd != 'q' );
if( ! cin )
{
// This is useful if students are testing the list with ints, instead of
// chars, and accidentally enter a non-digit char.
cout << "cin read errror" << endl;
}
return 0;
}
void print_help()
{
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +x : Insert x after the cursor" << endl;
cout << " - : Remove the data item marked by the cursor" << endl;
cout << " =x : Replace the data item marked by the cursor with x"
<< endl;
cout << " @ : Display the data item marked by the cursor" << endl;
cout << " < : Go to the beginning of the list" << endl;
cout << " > : Go to the end of the list" << endl;
cout << " N : Go to the next data item" << endl;
cout << " P : Go to the prior data item" << endl;
cout << " C : Clear the list" << endl;
cout << " E : Empty list?" << endl;
cout << " F : Full list?" << endl;
cout << " M : Move data item marked by cursor to beginning "
<< "(" <<
#if LAB5_TEST2
" Active "
#else
"Inactive "
#endif
<< ": In-lab Ex. 2)" << endl;
cout << " #x : Insert x before the cursor "
<< " (" <<
#if LAB5_TEST3
" Active "
#else
"Inactive "
#endif
<< " : In-lab Ex. 3)" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
}
ListLinked.cpp
#include "ListLinked.h"
template <typename DataType>
List<DataType>::List(int ignored){
head=NULL;
cursor=NULL;
}
// Copy constructor. Creates a list which is equivalent in content
// to the "other" list.
template <typename DataType>
List<DataType>::List(const List& other)
: head(0), cursor(0)
{
operator=(other);
}
// Overloaded assignment operator. Reinitializes the list to be
// equivalent in content to the "other" list.
// Note: we include self-assignment protection by checking whether
// "this" object is identical to the "other" object.
template <typename DataType>
List<DataType>& List<DataType>::operator=(const List& other)
{
if( this != &other ) {
clear();
ListNode *otherPtr = other.head;
ListNode *holdCursor = 0;
while( otherPtr != 0 ) {
insert(otherPtr->dataItem);
if(otherPtr == other.cursor) {
holdCursor = cursor;
}
otherPtr = otherPtr->next;
}
cursor = holdCursor;
}
return *this;
}
// Destructor. Frees the memory used by a list.
template <typename DataType>
List<DataType>::~List()
{
clear();
}
template <typename DataType>
List<DataType>::ListNode::ListNode(const DataType& nodeData, ListNode* nextPtr){
dataItem=nodeData;
next=nextPtr;
}
template <typename DataType>
void List<DataType>::insert(const DataType& newDataItem) throw (logic_error){
if(!isEmpty()){
if(cursor->next==NULL){
cursor->next=new ListNode(newDataItem,NULL);
cursor=cursor->next;
}else{
cursor->next=new ListNode(newDataItem,cursor->next);
cursor=cursor->next;
}
}else{
head=new ListNode(newDataItem, NULL);
cursor=head;
}
}
template <typename DataType>
void List<DataType>::remove() throw (logic_error){
if(head==NULL)
throw logic_error("No data");
if(cursor==head){
ListNode* temp=head;
head=head->next;
cursor=head;
delete temp;
}else{
ListNode* temp=cursor->next;
ListNode* temp2=cursor;
this->gotoPrior();
cursor->next=temp;
if(temp==NULL)
cursor=head;
else
cursor=temp;
delete temp2;
}
}
template <typename DataType>
void List<DataType>::replace(const DataType& newDataItem) throw (logic_error){
if(head==NULL)
throw logic_error("No data");
cursor->dataItem=newDataItem;
}
template <typename DataType>
void List<DataType>::clear(){
cursor=head;
do{
delete cursor;
}while(this->gotoNext());
head=NULL;
cursor=NULL;
}
template <typename DataType>
bool List<DataType>::isEmpty() const{
return head==NULL;
}
template <typename DataType>
bool List<DataType>::isFull() const{
return false;
}
template <typename DataType>
void List<DataType>::gotoBeginning() throw (logic_error){
if(head==NULL)
throw logic_error("No data");
cursor=head;
}
template <typename DataType>
void List<DataType>::gotoEnd() throw (logic_error){
if(head==NULL)
throw logic_error("No data");
while(this->gotoNext()){}
}
template <typename DataType>
bool List<DataType>::gotoNext() throw (logic_error){
if(head==NULL)
throw logic_error("No data");
if(cursor->next==NULL)
return false;
else{
cursor=cursor->next;
return true;
}
}
template <typename DataType>
bool List<DataType>::gotoPrior() throw (logic_error){
if(head==NULL)
throw logic_error("No data");
if(cursor==head)
return false;
else if(head->next==cursor){
cursor=head;
return true;
}else{
ListNode* temp=cursor;
cursor=head;
while(this->gotoNext()&&cursor->next!=temp){}
return true;
}
}
template <typename DataType>
DataType List<DataType>::getCursor() const throw (logic_error){
if(head==NULL)
throw logic_error("No data");
return cursor->dataItem;
}
template <typename DataType>
void List<DataType>::showStructure() const
// Outputs the items in a list. If the list is empty, outputs
// "Empty list". This operation is intended for testing and
// debugging purposes only.
{
if ( isEmpty() )
{
cout << "Empty list" << endl;
}
else
{
for (ListNode* temp = head; temp != 0; temp = temp->next) {
if (temp == cursor) {
cout << "[";
}
// Assumes that dataItem can be printed via << because
// is is either primitive or operator<< is overloaded.
cout << temp->dataItem;
if (temp == cursor) {
cout << "]";
}
cout << " ";
}
cout << endl;
}
}
ListLinked.h
#ifndef LISTLINKED_H
#define LISTLINKED_H
#include <stdexcept>
#include <iostream>
using namespace std;
template <typename DataType>
class List {
public:
List(int ignored = 0);
List(const List& other);
List& operator=(const List& other);
~List();
void insert(const DataType& newDataItem) throw (logic_error);
void remove() throw (logic_error);
void replace(const DataType& newDataItem) throw (logic_error);
void clear();
bool isEmpty() const;
bool isFull() const;
void gotoBeginning() throw (logic_error);
void gotoEnd() throw (logic_error);
bool gotoNext() throw (logic_error);
bool gotoPrior() throw (logic_error);
DataType getCursor() const throw (logic_error);
// Programming exercise 2
void moveToBeginning () throw (logic_error);
// Programming exercise 3
void insertBefore(const DataType& newDataItem) throw (logic_error);
void showStructure() const;
private:
class ListNode {
public:
ListNode(const DataType& nodeData, ListNode* nextPtr);
DataType dataItem;
ListNode* next;
};
ListNode* head;
ListNode* cursor;
};
#endif
sample outputs
Commands:
H : Help (displays this message)
+x : Insert x after the cursor
- : Remove the data item marked by the cursor
=x : Replace the data item marked by the cursor with x
@ : Display the data item marked by the cursor
< : Go to the beginning of the list
> : Go to the end of the list
N : Go to the next data item
P : Go to the prior data item
C : Clear the list
E : Empty list?
F : Full list?
M : Move data item marked by cursor to beginning (Inactive : In-lab Ex. 2)
#x : Insert x before the cursor (Inactive : In-lab Ex. 3)
Q : Quit the test program
Empty List
Command:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.