Question

#Linked Lists and Classes #C++

Hi, please use singly linked list method to do this question. Thank you!

Here’s the contents of a file called example.cpp:

// example.cpp

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

using namespace std;

int main() {
    cout << "Please enter some words (ctrl-d to stop):\n";
    LinkedList lst;
    int count = 0;
    string s;
    while (cin >> s) {
        count++;
        lst.add(remove_non_letters(s));
    } // while
    cout << "\n" << count << " total words read in\n";
    cout << lst.size() << " unique words read in\n\n";
    lst.print();
}

If you try to compile this you’ll get an error saying the header file LinkedList.h doesn’t exist. Your task for this assignment is to implement LinkedList.h so that this example program — and any other program that uses it — works correctly.

Here are the parts of the program you need to implement:

LinkedList is a class that implements a linked list. Implement this as singly-linked list, doubly-linked list, or circular list (you decide what is best).

LinkedList has a default constructor, i.e. a constructor that takes no inputs, that creates a new empty LinkedList object.

LinkedList has a destructor that deletes all the nodes on the list. This is necessary to make sure LinkedList has no memory leaks.

Assuming lst is an object of type LinkedList, then it has at least the following methods:

lst.size() returns the number of nodes currently on the linked list.

lst.add(s) adds the string s to the front of the linked list if s is not already somewhere on the list. If s is already somewhere on the list, then it does nothing.

Thus, lst.add(s) ensures that only one copy of each string occurs in lst.

lst.print() prints to cout a numbered list of all the strings in lst. The strings should be printed in the order they occur on the list. Note that because new strings are always added to the front of the list, the order of the strings should always be the same.

Please print your list neatly in the format shown in the example runs below.

The function remove_non_letters(s) takes a string s as input and returns a new string that is the same as s, except any non-letters have been removed. For example, remove_non_letters("M-55a3cfg.1") returns the string "Macfg", and remove_non_letters("555-5390).returns "".

Note that you can add any helper code you need to implement these functions. Please don’t use code from any other sources except the C++ standard library, and implement the linked list using basic C++ (e.g. don’t just use the STL linked list!).

Example Runs

Suppose the file test1.txt contains this text:

this is a test, this is only a test!

Then you can build and run example.cpp like this:

$ make example
g++  -std=c++14 -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g   example.cpp   -o example

$ ./example <test1.txt
Please enter some words (ctrl-d to stop):

9 total words read in
5 unique words read in

1. only
2. test
3. a
4. is
5. this

The command ./example <test1.txt re-directs the contents of test1.txt into the program so that you don’t need to type in the data every time you run it.

You also need to check that your program has no memory leaks, so run it with valgrind like this:

valgrind ./example <test1.txt
==16341== Memcheck, a memory error detector
==16341== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==16341== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==16341== Command: ./example
==16341==
Please enter some words (ctrl-d to stop):

9 total words read in
5 unique words read in

1. only
2. test
3. a
4. is
5. this
==16341==
==16341== HEAP SUMMARY:
==16341==     in use at exit: 18,944 bytes in 1 blocks
==16341==   total heap usage: 8 allocs, 7 frees, 24,204 bytes allocated
==16341==
==16341== LEAK SUMMARY:
==16341==    definitely lost: 0 bytes in 0 blocks
==16341==    indirectly lost: 0 bytes in 0 blocks
==16341==      possibly lost: 0 bytes in 0 blocks
==16341==    still reachable: 18,944 bytes in 1 blocks
==16341==         suppressed: 0 bytes in 0 blocks
==16341== Rerun with --leak-check=full to see details of leaked memory
==16341==
==16341== For counts of detected and suppressed errors, rerun with: -v
==16341== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

valgrind reports that there are no memory leaks. It says that 18,944 bytes are still in use at exit, but that’s okay because the program is done and all memory is being returned to the operating system anyways.

Be sure to test your program on more than just the data in test1.txt, and also on simple code besides the code in example.cpp. Do enough testing to be certain your program works correctly in all cases.

Answer 1

LinkedList.h
-------------------------
#ifndef LinkedList_h
#define LinkedList_h

#include <iostream>
#include <string>
using namespace std;

struct node
{
string name;
node * next;
};
class LinkedList
{
private:
node * head;
int totalLength;
  
public:
// Default Constructor.
LinkedList();
bool insert( node * tempNode, int pos );
bool remove( int pos );
void print();
  
// Destructor
~LinkedList();
};

#endif

--------------------------------------------------------------------------------------------------------------------------------------------------
#include "LinkedList.h"

// Default Constructor
LinkedList::LinkedList()
{
head -> name = "";
head -> next = NULL;
totalLength = 0;
}

bool LinkedList::insert( node * tempNode, int pos )
{
if ((pos <= 0) || (pos > totalLength + 1))
{
cout << "out of range";
return false;
}
if (head -> next == NULL)
{
head -> next = tempNode;
totalLength++;
return true;
}
int totalCount = 0;
node * pp = head;
node * qq = head;
while (qq)
{
if (totalCount == pos)
{
pp -> next = tempNode;
tempNode -> next = qq;
length++;
return true;
}
pp = qq;
qq = pp -> next;
totalCount++;
}
if (totalCount == pos)
{
pp -> next = tempNode;
tempNode -> next = qq;
totalLength++;
return true;
}
cout << "Error.. not added.";
return false;
}

// remove node
bool LinkedList::remove( int pos )
{
if ((pos <= 0) || (pos > totalLength + 1))
{
cout << "give correct position";
return false;
}
if (head -> next == NULL)
{
cout << "empty list.. ";
return false;
}
int totalCount = 0;
node * pp = head;
node * qq = head;
while (qq)
{
if (totalCount == pos)
{
pp -> next = qq -> next;
delete qq;
totalLength--;
return true;
}
pp = qq;
qq = pp -> next;
totalCount++;
}
cout << "error..";
return false;
}

// print all names in list
void LinkedList::print()
{
node * pp = head;
node * qq = head;
cout << "\n-------------------\n";
cout << "Names in list ate: ";
while (qq)
{
pp = qq;
cout << "Name: " << pp -> song << endl;
qq = pp -> next;
totalCount++;
}
}

// Destructor
LinkedList::~LinkedList()
{
node * pp = head;
node * qq = head;
while (qq)
{
pp = qq;
qq = pp -> next;
if (qq) delete pp;
}
}