LinkedList copy constructor implementation details.

Question

Hello all.

My first post here so be please be kind :)

I searched SO before posting but I couldn't find an answer (it's possible that my search wasn't the best though)

I'm starting to learn C++ and as an exercise decide to implement a simple LinkedList class (Below there is part of the code). I have a question regarding the way the copy constructor should be implemented and the best way the data on the original LinkedList should be accessed.

    template <typename T>
    class LinkedList {

        struct Node {
            T data;
            Node *next;

            Node(T t, Node *n) : data(t), next(n) {};
        };

    public:
        LinkedList();
        LinkedList(const LinkedList&);
        ~LinkedList();

        //member functions
        int size() const;              //done
        bool empty() const;            //done
        void append(const T&);         //done
        void prepend(const T&);        //done
        void insert(const T&, int i); 
        bool contains(const T&) const; //done
        bool removeOne(const T&);      //done
        int  removeAll(const T&);      //done
        void clear();                  //done
        T& last();                     //done
        const T& last() const;         //done
        T& first();                    //done
        const T& first() const;        //done
        void removeFirst();            //done
        T takeFirst();                 //done
        void removeLast();
        T takeLast();


        //delete when finished
        void print();                  
        //end delete

        //operators
        bool operator ==(const LinkedList<T> &other) const;    //done
        bool operator !=(const LinkedList<T> &other) const;    //done
        LinkedList<T>& operator =(const LinkedList<T> &other); //done


    private:
        Node* m_head;
        Node* m_tail;
        int   m_size;

    };

    template<typename T>
    LinkedList<T>::LinkedList() : m_head(0), m_tail(0), m_size(0) {

    }
...

Should my copy constructor access the data on each node of the original LinkedList directly?

template<typename T>
LinkedList<T>::LinkedList(const LinkedList& l) {

    m_head = 0;
    m_tail = 0;
    m_size = 0;

    Node *n = l.m_head;

    // construct list from given list
    while(n) {
        append(n->data);
        n = n->next;
    }
}

Or should I access the data through the corresponding accessor? (I know that I don't have the accessor(s) defined).

Also, I intend to create a custom iterator so that it can be possible to iterate over the LinkedList. Should I use in the copy constructor to access the data on each node?

Another question (completely off-topic, I know), when and/or why should we declare a pointer to a LinkedList

LinkedList *l = new LinkedList(); instead of LinkedList l;

Thank you very much.

Bruno

Answer 1

I assume append will properly handle the initial head/tail details, yes? If so, what you have now is great and simple: Go through the other list, and take its item and add a copy to my list. Perfect.

Well, almost. Use an initializer list to initialize member variables:

template<typename T>
LinkedList<T>::LinkedList(const LinkedList& l) :
m_head(0), m_tail(0), m_size(0)
{
 // ...
}

Also, maybe a matter of style, this woks instead of a while loop:

// construct list from given list
for (Node *n = l.m_head; n != 0; n = n->next)
    append(m->data);

In fact, I'd recommend this instead. When you have iterators, you'd do something like:

for (const_iterator iter = l.begin(); iter != l.end(); ++iter)
    append(*iter);

It just follows the style of a for-loop better. (Initialize something, check something, do something). Though for iterators, it'll probably be different. (More later)

---

Or should I access the data through the corresponding accessor? (I know that I don't have the accessor(s) defined).

Also, I intend to create a custom iterator so that it can be possible to iterate over the LinkedList. Should I use in the copy constructor to access the data on each node?

Those iterators are your accessors. You don't want to expose your internal head-tail pointers, that a recipe for disaster. The purpose of the class is to not expose the details. That said, iterators are the abstract wrapper around those details.

Once you have your iterators, then you could use them to iterate through the list instead of pointer arithmetic. This ties in to this recently asked question. In general, you should use your abstractions to deal with your data. So yes once you have your iterators in place, you should use those to iterate across the data.

Most classes that provide iterators also provide a way to insert data given a beginning and ending iterator. This is usually called insert, like this: insert(iterBegin, iterEnd). This loops through the iterators, appending it's data to the list.

If you had such functionality, your copy-constructor would simply be:

insert(l.begin(), l.end()); // insert the other list's entire range

Where insert is implemented like the for-loop we had above.

---

Another question (completely off-topic, I know), when and/or why should we declare a pointer to a LinkedList

LinkedList *l = new LinkedList(); instead of LinkedList l;

The first is dynamic allocation, the second is automatic (stack) allocation. You should prefer stack allocation. It's almost always faster, and safer too (since you don't need to delete anything). In fact, a concept called RAII relies on automatic storage, so destructors are guaranteed to run.

Only use dynamic allocation when you have to.

Answer 2

I think it is still a very valuable exercise to implement your own linked list as it helps you to learn the details of pointers, data structures, etc. Just be sure not to use your linked list class in real code as there are many existing libraries that are already writtern and tested. The best code is the code you don't have to write. See std::list.

I see no problem in the way you have implemented your copy constructor. You might do well to move the code to a dedicated copy function and call that from the constructor however, so that there is less code you have to maintain. But in general using the implementation details of your class from within the class itself is not only acceptable, but in many cases preferred as it will be as fast as possible.

As for creating the list with new vs creating it on the stack, this is a decision that applies not only to your class but data structures in general. Over-simplified rule of thumb: allocate on the stack if you can, allocate on the heap if you need to. You would need to for instance if you need tohe list to outlive the function in which it is created.

And again getting back to not hand-rolling your own code, if you do decide to use new to allocate on the heap, you should be using smart pointers instead of trying to manage the memory yourself. Get yourself in to this habit now. Don't wait until you're working on 'real' code. Many people you encounter will be unhelpful to you in your search to write better code, and will insist on "just using new".