Question

You will create a program that runs in one of two modes, interactive mode and test mode. The mode will determined by the command line, passing in a "-i" flag for interactive or "-t" for test mode. Require the user to pass in a flag.

$> ./lab02 -i
Make a selection:
1) Insert value at position
2) Remove at position
3) Replace value at position
4) Print length
5) Print list
6) Exit
Choice: 

$> ./lab02 -t
<output from your test class automatically prints>

LinkedList Header File

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include "Node.h" //Gone over in class
#include <stdexcept> //For runtime_error
class LinkedList
{
     private:
     Node* m_front;
     int m_length;
    
     public:
     LinkedList();
     LinkedList(const LinkedList& original);
     ~LinkedList();
     LinkedList& operator=(const LinkedList& original);
     bool isEmpty() const;
     int getLength() const;
     void insert(int position, int entry); 
     void remove(int position); 
     void clear();
     int getEntry(int position) const;

     /** Here's an example of a doxygen comment block. Do this for all methods
     * @pre The position is between 1 and the list's length
     * @post The entry at the given position is replaced with the new entry
     * @param position:  1<= position <= length
     * @param newEntry: A new entry to put in the list
     * @throw std::runtime_error if the position is invalid.
     **/
     void replace(int position, int newEntry);
};
#endif

Method Descriptions

• LinkedList()
  • Creates an empty list
• Copy Constructor
  • Creates a deep copy
• ~LinkedList
  • deletes all nodes (note, this could just call clear...)
• isEmpty
  • Returns true if empty, false otherwise
• getLength
  • Returns the length
• insert
  • adds a node containing the entry at that position (so the number of nodes is increased by 1)
  • positions range from 1 to length+1
  • NOTE: The reason for length+1 is to insert at the back of the list
  • if the position is out of range, it throws an exception
• remove
  • deletes the node at that position (so the number of nodes is decreased by 1)
  • positions range from 1 to length
  • if the position is out of range, it throws an exception
• clear
  • deletes all nodes in the list
• getEntry
  • Returns the entry at a given position
  • positions range from 1 to length
  • if the position is out of range, it throws an exception
• replace
  • replaces the entry at a given position
  • The number of nodes is unchanged
  • positions range from 1 to length
  • if the position is out of range, it throws an exception

Notes

• You may add private helper functions as you see fit, but their responsibility should be in line with that of a List
• Never expose private member to other scopes
• LinkedLists ARE NOT in charge of printing themselves
• Note: you'll also need to make a Node implementation

LinkedListTester class

• Runs a battery of tests to verify that our Linked List is working
• Has a single entry point called runTests()
• Each test prints what test is currently running and if the List Passed or failed
• Each test method should work in a vacuum, meaning each test

Sample LinkedListTester.h

class LinkedListTester
{   
    public: 

    LinkedListTester();

    //This will call all your test methods
    void runTests();
     
    private:

    /**
    * @brief Creates an empty list and verifies isEmpty() returns true
    **/
    void test01();

    /**
    * @brief Creates an empty list adds 1 value, verifies isEmpty() returns false
    **/
    void test02();

    /**
    * @brief Creates an empty list and verifies getLength() returns 0
    **/
    void test03();

    //more test methods as needed
};

Tests

I am provided you with some starter tests that you must implement. You will also be required to add new tests for methods not mentioned here

Each test should be ran in isolation, meaning the tests could be run in any order and they don't share any objects/data.

Size tests

1. size of empty list is zero
2. size returns correct value after inserting at front of list
3. size returns correct value after inserting at back of list
4. size returns correct value after inserting in middle of list
5. size returns correct value after adds and removing from front of list
6. size returns correct value after adds and removing from back of list
7. size returns correct value after adds and removing from middle of list

Insert tests

1. insert throws exception if given an invalid position

Sample Test Output

$>./lab02 -t
Test #1: size of empty list is zero  PASSED
Test #2: size returns correct value after inserting at front of list addFront PASSED
Test #3: size returns correct value after inserting at back of list FAILED
$>

Answer 1

// LinkedList.h

#ifndef LINKED_LIST_H

#define LINKED_LIST_H

//#include "Node.h" //Gone over in class

#include <stdexcept> //For runtime_error

struct Node

{

int info;

struct Node *next;

};

class LinkedList

{

private:

Node* m_front;

int m_length;

  

  

public:

LinkedList();

LinkedList(const LinkedList& original);

~LinkedList();

LinkedList& operator=(LinkedList& original);

bool isEmpty() const;

int getLength() const;

void insert(int position, int entry);

void remove(int position);

void clear();

int getEntry(int position) const;

void AddTail(int Item);

  

/** Here's an example of a doxygen comment block. Do this for all methods

   * @pre The position is between 1 and the list's length

   * @post The entry at the given position is replaced with the new entry

   * @param position: 1<= position <= length

   * @param newEntry: A new entry to put in the list

   * @throw std::runtime_error if the position is invalid.

   **/

void replace(int position, int newEntry);

};

#endif

// LinkedList.cpp

using namespace std;

LinkedList::LinkedList()

{

m_front = NULL;

}

LinkedList::LinkedList(const LinkedList & src)

{

Node* node = src.m_front;

while (node != nullptr)

{

AddTail(node->info);

node = node->next;

}

}

LinkedList& LinkedList::operator=(LinkedList& src)

{

struct Node *temp = m_front;

m_front = src.m_front;

src.m_front = temp;

  

return *this;

}

LinkedList::~LinkedList() {

  

}

//Adding on tail

void LinkedList::AddTail(int Item)

{

Node* current;

Node* node = new Node();

node->info = Item;

node->next = NULL;

//if head is in null declare the added node as head

if (m_front == NULL)

{

m_front = node;

}

else

{ //set the current to head, move the current node to current next node

current = m_front;

while (current->next != NULL)

{

current = current->next;

}

current->next = node;

}

}

bool LinkedList::isEmpty() const {

return m_front == NULL;

}

int LinkedList::getLength() const {

int count = 0; // Initialize count

struct Node* current = m_front; // Initialize current

while (current != NULL)

{

count++;

current = current->next;

}

return count;

}

void LinkedList::insert(int position, int entry) {

struct Node *n = new struct Node;

n->info = entry;

  

if(position == 0) {

n->next = m_front;

m_front = n;

}

else {

struct Node *c = new struct Node;

int count=1;

c = m_front;

while(count!=position)

{

c = c->next;

count++;

}

n->next = c->next;

c->next = n;

  

}

}

void LinkedList::remove(int position) {

// If linked list is empty

if (m_front == NULL)

return;

  

// Store head node

struct Node* temp = m_front;

  

// If head needs to be removed

if (position == 0)

{

m_front = temp->next; // Change head

free(temp); // free old head

return;

}

  

// Find previous node of the node to be deleted

for (int i=0; temp!=NULL && i<position-1; i++)

temp = temp->next;

  

// If position is more than number of ndoes

if (temp == NULL || temp->next == NULL)

return;

  

// Node temp->next is the node to be deleted

// Store pointer to the next of node to be deleted

struct Node *next = temp->next->next;

  

// Unlink the node from linked list

free(temp->next); // Free memory

  

temp->next = next; // Unlink the deleted node from list

}

void LinkedList:: clear() {

/* deref head_ref to get the real head */

struct Node* current = m_front;

struct Node* next;

  

while (current != NULL)

{

next = current->next;

free(current);

current = next;

}

  

/* deref head_ref to affect the real head back

   in the caller. */

m_front = NULL;

}

int LinkedList::getEntry(int position) const {

struct Node* current = m_front;

  

int count = 0;

while (current != NULL) {

if (count == position)

return(current->info);

count++;

current = current->next;

}

return 0;

}

//LinkedListTester.h

#ifndef LinkedListTester_hpp

#define LinkedListTester_hpp

#include <stdio.h>

#include "LinkedList.h"

class LinkedListTester

{

public:

  

LinkedListTester();

LinkedList* linked;

  

//This will call all your test methods

void runTests();

  

private:

  

/**

   * @brief Creates an empty list and verifies isEmpty() returns true

   **/

void test01();

  

/**

   * @brief Creates an empty list adds 1 value, verifies isEmpty() returns false

   **/

void test02();

  

/**

   * @brief Creates an empty list and verifies getLength() returns 0

   **/

void test03();

  

//more test methods as needed

};

#endif

//LinkedListTester.cpp

#include "LinkedListTester.h"

#include "LinkedList.h"

#include <iostream>

using namespace std;

LinkedListTester::LinkedListTester(){

linked = new LinkedList();

}

void LinkedListTester::runTests() {

test01();

test02();

test03();

}

/**

* @brief Creates an empty list and verifies isEmpty() returns true

**/

void LinkedListTester::test01() {

cout<<"is list empty "<<(linked->isEmpty() ? "TRUE" : "FALSE")<<endl;

}

/**

* @brief Creates an empty list adds 1 value, verifies isEmpty() returns false

**/

void LinkedListTester::test02() {

linked->clear();

linked->AddTail(1);

cout<<"is list empty "<<(linked->isEmpty() ? "TRUE" : "FALSE")<<endl;

}

/**

* @brief Creates an empty list and verifies getLength() returns 0

**/

void LinkedListTester::test03() {

linked->clear();

cout<<"is list empty "<<(linked->isEmpty() ? "TRUE" : "FALSE")<<endl;

}

//main.cpp

#include <iostream>

#include "LinkedListTester.h"

using namespace std;

int main()

{

char flag;

cout<<"Enter command in a \"-i\" flag for interactive or \"-t\" for test "<<endl;

cin>>flag;

  

if (flag == 'i') {

LinkedList* l = new LinkedList();

// call the respected function here to do actions.

l->AddTail(10);

l->AddTail(12);

  

} else if (flag == 't') {

LinkedListTester* t = new LinkedListTester();

t->runTests();

}

  

cout<<"Invalid entry please try again running the project"<<endl;

  

return 0;

}