Thread: Trouble inplementing a linked list

I am writing a linked list implementation as part of a larger program I am designing, but there is an error I can't seem to figure out:

Code:

./src/list.cpp:89: undefined reference to `show::show(std::string, std::string, std::string, bool, show*)

The error looks straghtforward enough, but I cant see what is wrong with the signature in question.

Here is the code:
list.cpp:

Code:

#include "list.h"
#include "show.h"
using namespace std;

list::list() {
    // TODO Auto-generated constructor stub
    m_head = new show();
}
show::show()
{
    episodeTitle = "none";
    seriesTitle = "none";
    recordDate = "000";
    isTivoSuggested = false;
    nextShow = NULL;
}

bool list::ListIsEmpty()
{
    return m_head ->nextShow == NULL;
}

list::list (const list& otherList)
{
    CopyData (otherList);



}
list& list::operator=(const list l2)
{
    if( this !=  &l2)    // check for self-assignment
        {
            //1- cleanup current list
            DeleteItems(this ->m_head);

            //2 copy over new data
            CopyData(l2);
        }

        //3
        return *this;
}


bool list::addItem (string showTitle, string seriesTitle, string showRecordDate, bool isSuggested)
{
     show *CurrentNode = m_head ->nextShow;
        show *PreviousNode = m_head;
        if (ListIsEmpty())
        {
          CurrentNode = new show (showTitle, seriesTitle, showRecordDate, isSuggested, NULL); //error is on this line
          m_head ->nextShow = CurrentNode;

          //CurrentNode ->info = item;
            return true;
        }
        else
        {
            if (showTitle == CurrentNode ->episodeTitle)
            {
                return false;
            }
            while (CurrentNode ->episodeTitle < showTitle)//doesn't work
            /* the second condition in the above while statement is what to do if we reach the end of the list*/
            {
          if (CurrentNode -> nextShow  == NULL/* if we have reached the end of the list*/)
            {
              CurrentNode ->nextShow  = new show (showTitle, seriesTitle, showRecordDate, isSuggested, NULL); //here too
              // PreviousNode -> NextNode = CurrentNode;

              //CurrentNode = CurrentNode ->NextNode;
              //CurrentNode ->info = item;
              return true;
            }
          CurrentNode = CurrentNode ->nextShow;
          PreviousNode =  PreviousNode ->nextShow;
                /*Set position between nodes*/
            }

            //if we not at the end of fhe list, the following code will re-adjust the pointers
            PreviousNode ->nextShow = new show(showTitle, seriesTitle, showRecordDate, isSuggested, NULL);
            PreviousNode = PreviousNode ->nextShow;
            PreviousNode ->nextShow = CurrentNode;


         }
        return true;
}

void list::ShowList() //this part will need to be expanded for more dynamic options
{
    show *currentShow = m_head ->nextShow;
    while (currentShow != NULL)
    {
        cout << currentShow ->episodeTitle << endl;
        cout << currentShow ->seriesTitle << endl;
        cout << currentShow ->recordDate << endl << endl;
        currentShow = currentShow ->nextShow;
    }
}
bool list::FindItem(string showTitle)
{
    show *currentShow = m_head ->nextShow;
    while (currentShow != NULL)
    {
        if (currentShow ->episodeTitle == showTitle)
        {
            return true;
        }
        if (currentShow ->episodeTitle > showTitle)
        {
            //this works since shows are alphabetized
            return false;
        }
        currentShow = currentShow ->nextShow;
    }
    return false;

}

bool list::DeleteItem(string showTitle)
{
    show *previousShow = m_head;
    show *currentShow = m_head ->nextShow;

    if (FindItem (showTitle))
    {
        while (currentShow != NULL)
        {
            if (currentShow ->episodeTitle == showTitle)
            {
                previousShow ->nextShow = currentShow ->nextShow;
                delete currentShow;
                return true;
            }
            else
            {
                currentShow = currentShow ->nextShow;
                previousShow = previousShow ->nextShow;
            }

        }
    }
    return false;
}

void list::DeleteItems(show *currentShow)
{
    /*CurrentNode starts off as m_head*/

    if (currentShow ->nextShow != NULL) //base case
    {
        DeleteItems (currentShow ->nextShow);
        /*Each node must delete itself, but only the base case has a null at the end,
         therefore, deletion and return statements must go outside the loop*/
    }
    delete currentShow;
    return;
}

void list::CopyData (const list& list2)
{
    show *showcopy = list2.m_head ->nextShow;
    show *thisShow = new show();
    while (thisShow != NULL)
    {
        //copy one node into another
        thisShow ->nextShow = new show(showcopy ->episodeTitle, showcopy ->seriesTitle, showcopy ->recordDate, showcopy ->isTivoSuggested, NULL);
        //Advance both pointers
        thisShow = thisShow ->nextShow;
        showcopy = showcopy ->nextShow;
    }

}
list::~list() {
    // TODO Auto-generated destructor stub
    DeleteItems (m_head);

}

list.h:

Code:

#include <iostream>
#include <string>
//#include "show.h"
using namespace std;

#ifndef LIST_H_
#define LIST_H_

class list {
public:
    list();
    list (const list &otherList);
    bool addItem (string showTitle, string seriesTitle, string showRecordDate, bool isSuggested); //this is the signature
    bool DeleteItem (string show);
      bool FindItem (string show);
      bool ListIsEmpty();
      list& operator=(const list l2);
      void ShowList ();
        virtual ~list();
        struct show *m_head;

private:
          void DeleteItems (show *m_head);
          void CopyData (const list& list2);

};

#endif /* LIST_H_ */

What am I doing wrong?
Thanks.
S

Why do you want to use a linked list? why do you feel you need to implement your own linked list?

If this is just a learning exercise more power to you. I "reinvent the wheel" all the time to get a better feel for things. In practice it's generally a good idea to avoid linked lists as pointed out in this video: Bjarne Stroustrup: Why you should avoid Linked Lists - YouTube

Originally Posted by Meiryousa

In practice it's generally a good idea to avoid linked lists as pointed out in this video: Bjarne Stroustrup: Why you should avoid Linked Lists - YouTube

Stroustrup isn't saying "In general avoid linked lists" in that video -- not at all. He's demonstrating that due to modern architectures (CPU pipelines, caches, etc, etc) that the long-taught "inserting into an arbitrary location in an array (vector) is slower than the same operation with a linked list" is not always true nowadays depending on the architecture, cache, etc. Technically memcpy(), which is required for inserting into a vanilla array because of the realloc(), is still O(n) it's just that behind that scenes that O(n) is much, much faster¹ than the O(n) you might naively implement (e.g. with a for loop). Coupled with the caches it's even faster.

The "problem" with linked lists is that in the way they're normally implemented spatial proximity of data (nodes) is, well, all over the place and therefore cache cannot be utilised as effectively by the CPU. There are ways around this. But in either case the insertion is O(1).

So, what Stroustrup is saying in not "don't ever use linked lists", he's saying "don't assume that linked lists are always faster".

Further, just like memcpy(), memmove() etc are now optimised on the CPU (they were not all that long ago) who's to say that a new CPU won't come out that optimises (on the CPU) linked list operations²?

Worrying about this stuff (implementation details) and never using linked lists based on Stroustrup's analysis is premature optimisation. My advice would be choose the data structure most appropriate for your problem, and often linked lists are the most appropriate data structure.

Aside from that it's an interesting video -- thanks for sharing.

¹ Behind the scenes the CPU is still doing, effectively, a loop over each of the elements, however because it's on the CPU itself it can 'micro-optimise' much better than a programmer possibly could.
² It seems unlikely BUT not outside the realms of possibility at all.

I stand by what I said. In general it is best to avoid linked lists. It's about the fact linked lists can't have random access just as much as it is about cache misses. However, I never said linked lists should be avoided at all costs. Personally I can think of a few instances of where I would use a linked list right off the top of my head. He is trying to say people use linked lists for the wrong reasons. Not that they shouldn't be used at all. Anyways...

I want to know why he wants to implement his own linked list class rather than using std::list. Not only that I want to know what types of problems he is trying to solve with it so that I might be able to recommend a better solution.

Why I'm using a linked list:
Partially to put in practice what I learned in CS class, partially because I'm not really familiar with how c++ implements more advanced data structures. So basically because that is the way I learned in class. I'm embaressed to say, It never really occurred to me until you mentioned it that there might be a better way. It made sense at the time to try to apply my lessons in real world projects, and the other way I had some familiarity with was dynamic arrays, which would have been very inefficent for this use case. The list may end up resizing up and down a few times over the course of the program execution.

Really, I have been debating for a long time which parts of this program I should implement myself vs using external libraries, as I do want to get something done at the end of the day. I kind of have 2 conflicting goals though
In case you were wondering, I am trying to implement a CLI .Tivo fetcher that can grab shows based on certain command line parameters.
This is my first "Real" project.

regarding the constructor:
Oops, forgot to include a file -- sorry. Fixing that now. It is in show.h

regarding the commented line:
I pulled these straight from my IDE, I had been experimenting before I posted, including show.h in that header did not fix anything.

Thank you for so many quick and helpful responses
PS I will definitely watch the youtube video

Originally Posted by Meiryousa

I stand by what I said. In general it is best to avoid linked lists. It's about the fact linked lists can't have random access just as much as it is about cache misses.

Correct (I should have placed more emphasis on finding the insertion point... I meant to but forgot).

I stand by what I said though: choose the "correct" data structure in the first place. If you need (fast/predictable) random access then linked lists are not the "correct" choice. I guess the most common/suitable use of a linked list is where you insert only at the head or tail -- and only ever use the head or tail (in the case of stacks and queues) or iterate over the list -- and in both of these cases a linked list is a reasonable choice. You wouldn't choose an array/vector simply because insertions into arbitrary locations is faster. Well, I wouldn't.

Code:

#include <iostream>
#include <string>
using namespace std;
#ifndef SHOW_H_
#define SHOW_H_

struct show
{
    string episodeTitle;
    string seriesTitle;
    string recordDate;
    bool isTivoSuggested;
    show (string episodeTitle,     string seriesTitle, string recordDate, bool isTivoSuggested, show *nextShow);
    show();
    struct show *nextShow;
};


#endif /* SHOW_H_ */

I think I see my error, but I am not sure. I need a body for the other constructor (the one with parameters) don't I? I will try it tomorrow and post results.

I just glanced over your code but basically this is the error:

./src/list.cpp:89: undefined reference to `show::show(std::string, std::string, std::string, bool, show*)

It is saying it can't find the constructor of show that takes the parameters "string, string, string, bool, show"

There is a constructor for show defined that I can see but it isn't that one.

Code:

show::show()
{
    episodeTitle = "none";
    seriesTitle = "none";
    recordDate = "000";
    isTivoSuggested = false;
    nextShow = NULL;
}

This constructor takes 0 arguments. You are trying to use a constructer that takes 5 arguments. Go define that constructor too.

Thank you,
I added the second constructor and that fixed it.