3-class linked list

Question

I am trying to make a linked list using 3 classes, however I cannot find ANY information online about it, and I can't seem to figure it out myself.

If you could please correct and explain what I am doing wrong, I would greatly appreciate it.

LinkTest.h:

#include <string>
class Test
{
public:
 void get(int &, std::string &);
private:
 int int1;
 std::string string1;
};
typedef class TestNode
{
 private:
 Test test;
 TestNode* next;
} *TestPtr;
class TestList
{
 public:
 TestList();
 void add(int &, std::string &);
 void print();
 private:
 TestPtr head;
 TestPtr tail;
 TestPtr temp;
};

LinkTest.cpp:

#include <iostream>
#include "LinkTest.h"
using namespace std;
void Test::get(int &otherint1, string &otherstring1)
{
 int1 = otherint1;
 string1 = otherstring1;
}
TestList::TestList()
{
 head = NULL;
 tail = NULL;
 temp = NULL;
}
void TestList::add(int &otherint1, string &otherstring1)
{
 TestPtr* n = new TestPtr;
 n->next = NULL;
 n->get(otherint1, otherstring1);
 if(head != NULL)
 {
 tail = head;
 while(tail->next != NULL)
 {
 tail = tail->next;
 }
 tail->next = n;
 }
 else
 {
 head = n;
 }
}
void TestList::print()
{
 tail = head;
 while(tail != NULL)
 {
 cout << tail->test.int1 << " " << tail->test.string1 << endl;
 temp = tail;
 tail = tail->next;
 }
}

The main function just does:

int otherint1 = 1;
string otherstring1 = "hi";
TestList l;
l.add(otherint1, otherstring1);
otherint1 = 2;
otherstring1 = "there";
l.add(otherint1, otherstring1);
l.print();

• rolfl: Linked Lists are not normally classified by how many classes they have. What made you classify it that way?
• user40128: Every example I find is usually: class TestList{ struct Node{ ... } *NodePtr; NodePtr head; NodePtr tail; NodePtr temp; //functions... } And NodePtr's data is usually just an int or string, not a class.
• rolfl: OK, then what you have is a Singly-Linked list optimized for tail 'add' ( O(1) add performance... ). Each time you add a node at the end, you update the 'tail' to point to the new node. This means you can simply add the node at tail.next, then move tail to point at the new node. If you remove the last node though, it is complicated, you have to 'reverse' the tail by scanning the entire list.

Answer 1

At first glance, your code appears to work, but there is some confusion going on. I'll highlight what I consider to be the four top issues instead of making an exhaustive list.

1. The Test::get() method is actually a setter, not a getter, and should be named Test::set().

2. The Test class seems to represent the kind of data you want to store in the list. You should just eliminate Test in favour of std::pair<int, std::string>.

   The linked list code doesn't really have any business providing an add() method that takes two kinds of data to be stuffed into the new node. Instead of calling TestList::add(int, std::string), just make the construction explicit to the caller, as TestList::add(std::pair<int, std::string>(someInt, someString)).

3. TestList has three member variables: head, tail, and temp. Of those three, only head stores object state and deserves to be a member variable. tail and temp should just be local variables within functions that need them.
4. You call new, but it's not paired with a delete anywhere. That's a memory leak. The memory that you allocate should be cleaned up in a destructor.

• user40128: I have not heard of pair before, do I need a special library for that? And yes, I added delete into the program.
• 200_success: See en.cppreference.com/w/cpp/utility/pair.
• user40128: Oh, I'd like to stay away from template for now. I will definitely try it out in another program in the near future though, thanks for the suggestion. As for this program, would you be able to fix the print and add functions for me please? I get errors for when I try to use TestPtr and when I try the line in print(): cout << tail->test.int1 << " " << tail->test.string1 << endl; It confuses me, because to me, that seems logical.
• Michael Urman: @user40128 Note that you're already using templates; they're just hidden: std::string is an alias for std::basic_string<char, ...>. If you just want to avoid the syntax all over the place, you could add your own typedef std::pair<int, std::string> IntString; alias.
• Loki Astari: @user40128: You can;t really stay away from templates. std::string is a template for example. Don't treat templates as special. They are just normal classes.

Answer 2

LinkTest.h:

Test is not really a test class.

class Test
{
public:
 void get(int &, std::string &);
private:
 int int1;
 std::string string1;
};

That's confusing. This is the type of data that you store in the list. Please rename it more appropriately. Common omong containers is value_type.

Again with TestNode the naming thing.

typedef class TestNode
{
 private:
 Test test;
 TestNode* next;
} *TestPtr;

This is not your grandpa's C; this is C++. struct live in the same namespace as other types and objects. Also multiple declarations on the same line is frowned upon so split the above into multiple declarations to make it clear wheat is happening.

class TestNode
{
 private:
 Test test;
 TestNode* next;
};
typedef TestNode* TestPtr;
 // ^^^^^^^^^ Note * on left side.
 // The type you are defing is a TestNode pointer => New Name TestPre

Personally I don't like hiding pointers behind typedefs. It hides pointers that I want to see because memory management needs to be done with them. I would personally drop the typedef.

Again Test in the name.

class TestList

Rather than adding two different types that have nothing to do with your list.

 void add(int &, std::string &);

You should add (or push) the data that is held by your list. In this case Test.

 // pass a test object that is copied into the list.
 void push_back(Test const& ); 

In modern versions of C++ we now use the term emplace for this you pass the parameters that can be used in the constructor of your data class. Unfortunately your data class has no constructor (apart from the default).

 class Test
 {
 public: Test(int v, std::string const& x)
 int1(v), string1(x){}
 };
 // Pass the values for the constructor of a Test object.
 // The object will be created emplace using the constructor.
 // rather than the copy constructor used by push_front() 
 void emplace_back(int const&, std::string const&)

Having a print function is fine (but you should pass a stream to print it on).

 void print(std::ostream& s = std::cout); // default to std::cout
 // if not explicitly specified.

But you should probably also define an operator<< for your class that calls it. Most people basically do away with the print and just put the logic of the print in operator>> and make it a friend of the class.

 std::ostream& operator<<(std::ostream& s, TestList& data)
 {
 data.print(s);
 return s;
 }

LinkTest.cpp:

Include from the most specific to the most general.

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

The most specific is the header file for this class. Followed by any header files for classes that you specifically use followed by C++ libraries )as these are general files but are built on-top of C files) followed by C libraries (as these are the most general system files).

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

Don't do this:

using namespace std;

see Why is "using namespace std;" considered bad practice?

Obviously not a get()

void Test::get(int &otherint1, string &otherstring1)
{
 int1 = otherint1;
 string1 = otherstring1;
}

This is setting the values. It looks more like a constructor than a get. Pass by const& this is a more healthy contract the promises you will not modify the passed parameters (it also allows you to use temporaries).

void TestList::add(int &otherint1, string &otherstring1)
{

Yep you should have a constructor that does all this work.

 TestPtr* n = new TestPtr;
 n->next = NULL;
 n->get(otherint1, otherstring1);

Would have looked much nicer as:

 TestPtr* n = new TestPtr(otherint1, otherstring1);

PS. These are horrible parameter names and do not help in self documenting code.

The tail value is a member of the class. Why it it not maintained as always pointing at the last element? Then you would not need to search for the last element every time you add something new to the class.

 tail = head;
 while(tail->next != NULL)
 {
 tail = tail->next;
 }
 tail->next = n;

The complexities of maintaining a list are reduced considerably if you use a sentinel value. See: Linked List reversal

Then you don't need to worry about when the head is NULL (because it never is).

 else
 {
 head = n;
 }

Also you don't handle memory management.

Technically for every new there should be a call to delete. But that's old school thinking. There should never be any delete specifically in your code. You should be using smart pointers to manage your pointers so that they are exception safe.

void TestList::print()
{
 // Don't use tail here.
 // tail should always point at the last element in the list.
 // Only moe it when there is a new last element.
 tail = head;
 // here use a local function scope temporary (call it printLoop or something).
 while(tail != NULL)

Don't use std::endl.

 std::cout << std::endl;
 // is equivalent to:
 std::cout << '\n' << std::flush;

As you see this forces the buffer to be flushed every time. This is very inefficient. So don't do it every time just do it once you have done all your printing. Personally I hardly ever use it. std::cin and std::cout are synced together so that std::cout is flushed before user input is requested so it is hardly ever necessary and the buffers for files are designed to be the size that gives you the most effecient size for flushing to disk.

 cout << tail->test.int1 << " " << tail->test.string1 << endl;

Rewrite the loop as:

 for(TestPtr printLoop = head; printLoop != NULL; printLoop = printLoop->next)
 {
 std::cout << printLoop->test << '\n';
 // ^^^^^^^^^^^^^^^
 // Note: it is not TestList job to know how to print a Test
 // You should just ask the stream to print it.
 // The the Test object should know how to print itself.
 }