Lab #12, Friday 11/16

The purpose of this lab is to give you practice with pointers and linked lists.

The following C++ code implements a linked list of names. Put these files into Visual Studio or on a Unix system (must be compiled with -std=c++11)

Node.h:

#pragma once
#include <string>
using namespace std;

class Node
{
  private:
        string name;
        Node* next;
  public:
        Node();
        Node(string theName, Node* nextNode);
        string getName();
        void setName(string newName);
        Node* getNext();
        void setNext(Node *newNext);
};

#include <string>
#include "Node.h"
using namespace std;

Node::Node() : name(""), next(nullptr)
{
}

Node::Node(string theName, Node* nextNode) :
        name(theName), next(nextNode)
{
}
string Node::getName()
{
        return name;
}
void Node::setName(string newName)
{
        name = newName;
}
Node* Node::getNext()
{
        return next;
}
void Node::setNext(Node *newNext)
{
        next = newNext;
}

#pragma once
#include "Node.h"
#include <string>
using namespace std;

class LinkedList
{
  private:
        Node* head;             // Points to the first thing in the list
  public:
        LinkedList();
        ~LinkedList();
        void add(string s); // Adds to front of list
        void remove(string s); // Deletes first occurrence of s in the list
        void output();  // Output everything in the list
};

#include "LinkedList.h"
#include <iostream>

using namespace std;

LinkedList::LinkedList()
{
        head = nullptr;
}
LinkedList::~LinkedList()
{
        Node *temp = head;
        while (temp != nullptr)
        {
                Node *next = temp->getNext();
                delete temp;
                temp = next;
        }
}

// Output everything in the list
void LinkedList::output()
{
        Node *temp = head;
        while (temp != nullptr)
        {
                cout << temp->getName() << endl;
                temp = temp->getNext();
        }
        cout << endl;
}

// Adds a new node with this string to the front of the linked list
void LinkedList::add(string s)
{
        if (head == nullptr)
        {
                // New list, make head point to it
                head = new Node(s, nullptr);
        }
        else
        {
                // Make a new node that points to head
                Node *temp = new Node(s, head);
                // Set head to the new node
                head = temp;
        }
}

// Deletes first occurrence of s in the list
void LinkedList::remove(string s)
{
        Node *temp = head;
        Node *previous = nullptr;  // You might want to use this variable
        while (temp != nullptr)
        {
                if (temp->getName() == s)
                {
                        // If we are deleting the head of the list
                        if (temp == head)
                        {
                                head = head->getNext();
                                delete temp;
                        }
                        else
                        // We are deleting something that is not the head
                        {
                                previous->setNext(temp->getNext());
                        }

                        break;
                }
                previous = temp;
                temp = temp->getNext();
        }
}

#include "LinkedList.h"
#include <iostream>

using namespace std;

int main()
{
  LinkedList mylist;

  mylist.add("Armando");
  mylist.add("Bobo");
  mylist.add("Carlo");
  mylist.add("Drogo");
  mylist.add("Cyrano");
  mylist.add("Frodo");

  cout << "Output entire list" << endl;
  mylist.output();

  cout << "Output after removing Carlo" << endl;
  mylist.remove("Carlo");
  mylist.output();

  cout << "Output after removing Frodo" << endl;
  mylist.remove("Frodo");
  mylist.output();

  cout << "Output after removing Armando" << endl;
  mylist.remove("Armando");
  mylist.output();

  return 0;
}

1. Add and implement a Node* contains(string target) method in the LinkedList class that takes a string as input. If the linked list contains the string then return a pointer to the Node with the string. If the linked list doesn't contain the string return nullptr. With the pointer that is returned you can invoke ptrVar->getName() to output the name or ptrVar->setName(newName) to change the name.
2. The add method always adds to the front of the linked list. Create an addTail method that adds a new string to the tail or end of the list.
3. Add some code in main to test the new methods.

Show your working code to the instructor or lab assistant for credit, or email your solution by midnight.