Question

In short, you’re going to implement a linked-list class for storing integers, using a provided main program to help you interact and test your work. You’ll want to build the linked-list class function by function, working in “Develop” mode to test out each function you write.

main.cpp is a read only file

linkedlist.h is the file to work on.

main.cpp

#include
#include

#include "linkedlist.h"

using namespace std;

int main()
{
linkedlist LL;
string cmd;
int value, key;

//
// user can enter commands to manipulate the LL:
//
// p w => push w onto the end
// i x y => insert x after y (y must exist in the list)
// r z => remove the first instance of z
// o => output the list
// q => quit
//

//cout << "Enter a command> ";
cin >> cmd;

while (cmd != "q")
{
if (cmd == "p")
{
// push:
cin >> value;

LL.push_back(value);
}
else if (cmd == "i")
{
// insert:
cin >> value;
cin >> key;

LL.insert(value, key);
}
else if (cmd == "r")
{
// remove:
cin >> value;

LL.remove(value);
}
else if (cmd == "o")
{
// output:

LL.output();
}
else
{
cout << "**Invalid command, try p, i, r, o or q" << endl;
cout << endl;
}

//cout << "Enter a command> ";
cin >> cmd;
}

return 0;
}

linkedlist.h

/*linkedlist.h*/

#pragma once

#include <iostream>

using namespace std;

class linkedlist
{
private:
struct NODE
{
int Data;
struct NODE* Next;
};

struct NODE* Head; // first node in list (or nullptr)
struct NODE* Tail; // last node in list (or nullptr)
int Size; // # of elements (i.e. nodes) in list

public:
//
// default constructor
//
// Creates an empty list.
//
linkedlist()
{
Head = nullptr;
Tail = nullptr;
Size = 0;
}

//
// size
//
// Returns the # of elements in the list.
//
int size()
{
return Size;
}

//
// push_back
//
// Pushes value onto the end of the list.
//
void push_back(int value)
{
struct NODE* newNode = new struct NODE();
newNode->Data = value;
newNode->Next = nullptr;

//
// TODO: a new node containing the value was created
// above. Add this new node to the end of the list.
//
  
//
// HINT #2: don't forget to increment size
//
}

//
// insert
//
// Inserts the given value in the list *after* the key. If
// the key cannot be found, nothing happens; if the key occurs
// multiple times, value will be inserted after the first
// instance.
//
void insert(int value, int key)
{
// allocate a new node to hold the value:
struct NODE* newNode = new struct NODE();
newNode->Data = value;
newNode->Next = nullptr;

//
// TODO: a new node containing the value was created
// above. Insert this new node after the node containing
// the given key (assume the key appears only once).
// If the key cannot be found (or the list is empty), do
// nothing and just return (or delete newNode and return).
//
t.
//
// HINT #2: don't forget to increment size
//
}

//
// remove
//
// Removes the first instance of value from the list; if
// the value cannot be found, nothing happens.
//
void remove(int value)
{
//
// TODO: remove the first node that contains value; if value
// is not found, do nothing. You'll need to search the list
// for the value, and then unlink that node from the list.
// Don't worry about freeing the memory, you can ignore that
// for now (or use delete ptrToNode; if you want to free).
//

//
// HINT #2: don't forget to decrement size
//
}

//
// output
//
// Outputs the size, followed by the elements one by one on
// the same line.
//
void output()
{
cout << "Size: " << Size << endl;
cout << "Elements: ";

//
// TODO: output elements with a space after each one
// (including a space after last element). Output all
// on the same line, save the end-of-line for after
// the traversal loop is over.
//
.
//

cout << endl;
}

};

Answer 1

Screenshot

Program

linkedlist.h

/*linkedlist.h*/
#pragma once
#include <iostream>
using namespace std;
class linkedlist{
private:
   struct NODE{
       int Data;
       struct NODE* Next;
   };
   struct NODE* Head; // first node in list (or nullptr)
   struct NODE* Tail; // last node in list (or nullptr)
   int Size; // # of elements (i.e. nodes) in list
public:
   //
   // default constructor
   //
   // Creates an empty list.
   //
   linkedlist(){
       Head = nullptr;
       Tail = nullptr;
       Size = 0;
   }
   //
   // size
   //
   // Returns the # of elements in the list.
   //
   int size(){
       return Size;
   }
   //
   // push_back
   //
   // Pushes value onto the end of the list.
   //
   void push_back(int value){
       struct NODE* newNode = new struct NODE();
       newNode->Data = value;
       newNode->Next = nullptr;
       //
       // TODO: a new node containing the value was created
       // above. Add this new node to the end of the list.
       //
       if (Head == nullptr) {
           Head = newNode;
           Tail = newNode;
       }
       else
       {
           Tail->Next = newNode;
           Tail = Tail->Next;
       }
       //
       // HINT #2: don't forget to increment size
       //
       Size++;
   }

   //
   // insert
   //
   // Inserts the given value in the list *after* the key. If
   // the key cannot be found, nothing happens; if the key occurs
   // multiple times, value will be inserted after the first
   // instance.
   //
   void insert(int value, int key)
   {
       // allocate a new node to hold the value:
       struct NODE* newNode = new struct NODE();
       newNode->Data = value;
       newNode->Next = nullptr;

       //
       // TODO: a new node containing the value was created
       // above. Insert this new node after the node containing
       // the given key (assume the key appears only once).
       // If the key cannot be found (or the list is empty), do
       // nothing and just return (or delete newNode and return).
       //
       struct NODE* current =Head;
       struct NODE* next = current->Next;
       bool flag = false;
       while(current)
       {
           if (current->Data==key) {
               flag = true;
               break;
           }
           current = current->Next;
           next = current->Next;
       }
       if (flag == true) {
           current->Next = newNode;
           newNode->Next =next;

             Size++;
       }
   }

   //
   // remove
   //
   // Removes the first instance of value from the list; if
   // the value cannot be found, nothing happens.
   //
   void remove(int value)
   {
       //
       // TODO: remove the first node that contains value; if value
       // is not found, do nothing. You'll need to search the list
       // for the value, and then unlink that node from the list.
       // Don't worry about freeing the memory, you can ignore that
       // for now (or use delete ptrToNode; if you want to free).
       //
       struct NODE* current =Head;
       struct NODE* previous =Head;
       bool flag = false;
       while(current)
       {
           if (current->Data == value) {
               flag = true;
               break;
           }
           previous = current;
           current = current->Next;
       }
       if (flag == true) {
           previous->Next = current->Next;
           Size--;
       }
      
       //
       // HINT #2: don't forget to decrement size
       //
   }

   //
   // output
   //
   // Outputs the size, followed by the elements one by one on
   // the same line.
   //
   void output()
   {
       cout << "Size: " << Size << endl;
       cout << "Elements: ";

       //
       // TODO: output elements with a space after each one
       // (including a space after last element). Output all
       // on the same line, save the end-of-line for after
       // the traversal loop is over.
       //
       struct NODE* temp = Head;
       while (temp)
       {
           cout << temp->Data << "\t";
           temp = temp->Next;
       }
           //

           cout << endl;
   }

};

main.cpp

#include<iostream>
#include<string>

#include "linkedlist.h"
using namespace std;
int main(){
   linkedlist LL;
   string cmd;
   int value, key;
   //
   // user can enter commands to manipulate the LL:
   //
   // p w => push w onto the end
   // i x y => insert x after y (y must exist in the list)
   // r z => remove the first instance of z
   // o => output the list
   // q => quit
   //
   //cout << "Enter a command> ";
   cin >> cmd;
   while (cmd != "q")
   {
       if (cmd == "p")
       {
           // push:
           cin >> value;

           LL.push_back(value);
       }
       else if (cmd == "i")
       {
           // insert:
           cin >> value;
           cin >> key;

           LL.insert(value, key);
       }
       else if (cmd == "r")
       {
           // remove:
           cin >> value;

           LL.remove(value);
       }
       else if (cmd == "o")
       {
           // output:

           LL.output();
       }
       else
       {
           cout << "**Invalid command, try p, i, r, o or q" << endl;
           cout << endl;
       }

       //cout << "Enter a command> ";
       cin >> cmd;
   }
   return 0;
}

--------------------------------------------------------

Output

p 2
p 5
p 6
p 8
o
Size: 4
Elements: 2     5       6       8
i 7 6
o
Size: 5
Elements: 2     5       6       7       8
r 7
o
Size: 4
Elements: 2     5       6       8
q