Please use this header file to build the doubly linked list. Use the header file
ID: 3685198 • Letter: P
Question
Please use this header file to build the doubly linked list. Use the header file that is provided in the question, don't change it
//--------------------------------------------------------------------
//
// 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
Doubly Linked List is a data structure that holds a list of items with double links: previous and next. In this homework, you need to implement all functions in the defined ListLinked class (prototype is provided by the instructor). Please download the header file (ListLinked.h) from ecourses, 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.
You need to make the following of the source code using the header file provided above: main.cpp, ListLinked.cpp.
Explanation / Answer
#include<iostream>
using namespace std;
class List {
public:
/* Function for create/insert node */
void insert(int val){
list *addEnd = new list;
addEnd->data=val;
if(first == NULL) {
addEnd->prev = NULL;
addEnd->next = NULL;
first = addEnd;
last = addEnd;
cout << "Linked list Created!" << endl;
}
else {
addEnd->next = NULL;
last->next = addEnd;
addEnd->prev = last;
last = addEnd;
cout << "Data Inserted at the end of the Linked list!" << endl;
}
}
/* Function for Display Linked list */
void print() {
node = first;
cout << "List of data in Linked list in Ascending order!" << endl;
while(node != NULL) {
cout << node->data << endl;
node = node->next;
}
node = last;
cout << "List of data in Linked list in Descending order!" << endl;
while(node != NULL) {
cout << node->data << endl;
node = node->prev;
}
}
/* Function for delete node from Linked list */
void remove(){
int count = 0, number, i;
node = node1 = node2 = first;
for(node = first; node != NULL; node = node->next)
cout << "Enter value for the node:" << endl;
count++;
display();
cout << count << " nodes available here!" << endl;
cout << "Enter the node number which you want to delete:" << endl;
cin >> number;
if(number != 1) {
if(number < count && number > 0) {
for(i = 2; i <= number; i++)
node = node->next;
for(i = 2; i <= number-1; i++)
node1 = node1->next;
for(i = 2; i <= number+1; i++)
node2 = node2->next;
node2->prev = node1;
node1->next = node2;
node->prev = NULL;
node->next = NULL;
node = NULL;
}
else if(number == count) {
node = last;
last = node->prev;
last->next = NULL;
node = NULL;
}
else
cout << "Invalid node number!" << endl;
}
else {
node = first;
first = node->next;
first->prev = NULL;
node = NULL;
}
cout << "Node has been deleted successfully!" << endl;
}
/* Function for clear Linked list */
void clear()
{
struct ListNode *tmp, *q;
tmp = start;
start = start->next;
start->prev = NULL;
free(tmp);
q = start;
while (q->next->next != NULL)
{
/*Element deleted in between*/
tmp = q->next;
q->next = tmp->next;
tmp->next->prev = q;
free(tmp);
}
q = q->next;
}
/*last element deleted*/
tmp = q->next;
free(tmp);
q->next = NULL;
return;
}
bool isFull()
{
return false;
}
bool isEmpty()
{
return (start == NULL);
}
void gotoBeginning()
{
struct ListNode *tmp;
tmp = start;
}
void gotoEnd()
{
node = first;
while(node != NULL) {
node = node->next;
}
}
bool gotoNext()
{
if(node->next == NULL)
return false;
node= node->next;
return true;
}
void InsertBefore(ListNode node)
{
cout<< "enter value";
cin >> value;
struct ListNode *tmp;
if(!gotoPrior())
cout << "no prior element";
else
{
tmp = node->prev->prev;
tmp->next ->data = value;
tmp->next->next = node;
}
}
bool gotoPrior()
{
if(node=node->prev == NULL)
return false;
node=node->prev;
return true;
}
int main() {
int op = 0,value;
linkedlist llist = linkedlist();
while(op != 4) {
cout << "1. Insert 2. remove 3.replace 4. print 5. clear 6.insertBefore" << endl;
cout << "Enter your choice:" << endl;
cin >> op;
switch(op) {
case 1:
cout << "enter value to be inserted ";
cin >> value;
llist.insert(value);
break;
case 2:
llist.remove();
break;
case 3:cout << "enter value to be replaced ";
cin >> value;
llist.replace(value);
break;
case 4:
llist.print();
break;
case 5:
llist.clear();
break;
case 6:
llist.insertBefore(node);
break;
case 7: return 0;
break;
default:
cout << "Invalid choice!" << endl;
}
}
return 0;
}