3
\$\begingroup\$

Here is a non-circular, singly linked list data structure (with no headers). This is done using a pre-C++11 standard. Is there a more efficient way/shorter way of writing this (especially the copy assignment operator which contains duplicate code from the copy constructor and clear() method)?

template<typename T>
class linked_list{
    class node {
    public:
        T data;
        node *next;

        node() :
            data(T()),
            next(NULL)
            { }

        node(const T &data, node *next) :
            data(T(data)),
            next(next)
            { }
    }; // class node
protected:
    node *mFirst;
    size_t mSize;
public:
    /** Empty Constructor */
    linked_list(): 
        mFirst(NULL), 
        mSize(0) {}

    /** Array Constructor */
    linked_list(T* others, size_t n) {
        for (int i = 0; i < n; i++) {
            mFirst = new node(*others, mFirst);
            others++;
        }
    }

    /** Copy Constructor*/
    linked_list(const linked_list &other):
        mFirst(NULL),
        mSize(other.mSize)
        {
        node *p = other.mFirst;
        while (p != NULL) {
            mFirst = new node(p->data, mFirst);
            p = p->next;
        }
        if (mFirst != NULL){
            node *q, *prev;
            p = mFirst;
            q = p->next;
            p->next = NULL;
            prev = p;
            p = q;
            for (int i = 1; i < mSize; i++) {
                q = p->next;
                p->next = prev;
                prev = p;
                p = q;
            }
            mFirst = prev;
        }
    }

    /** Destructor */
    ~linked_list(){
        clear();
    }

    /** Copy Assignment Operator*/
    linked_list &operator=(const linked_list &other) {
        if (this != &other) {
            // allocate and copy from other to r
            mSize = other.mSize;
            node *p = other.mFirst, *r = NULL;
            while (p != NULL) {
                r = new node(p->data, r);
                p = p->next;
            }
            if (r != NULL){
                node *q, *prev;
                p = r;
                q = p->next;
                p->next = NULL;
                prev = p;
                p = q;
                for (int i = 1; i < mSize; i++) {
                    q = p->next;
                    p->next = prev;
                    prev = p;
                    p = q;
                }
                r = prev;
            }

            // deallocate current
            node *q;
            p = mFirst;
            while(p != NULL) {
                q = p->next;
                delete p;
                p = q;
            }

            // replace
            mFirst = r;
        }
        return *this;
    }

    void clear() {
        node *q, *p = mFirst;
        while(p != NULL) {
            q = p->next;
            delete p;
            p = q;
        }
        mFirst = NULL;
        mSize = 0;
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Yes there is. You should look up the Copy and Swap Idiom. \$\endgroup\$ – Martin York May 2 '17 at 21:26
2
\$\begingroup\$

Putting member variables in a protected block is a worry.

 protected:
    node *mFirst;
    size_t mSize;

I would put them into a private block and give limited accesses via members in the protected block that prevents derived classes from breaking the invariant on your members.

Personal preference here:

linked_list(): 
    mFirst(NULL), 
    mSize(0) {}

I like to write it like this:

// Take it or leave it.
// Nobody should complain about your style just looks slightly different.
linked_list() 
    : mFirst(NULL) 
    , mSize(0)
{}

I would also change mFirst to mRoot. The use of m to mark member variables is an indicator that you are using bad member Vs local names and need a rule to allow people to distinguish between the two. I would prefer you improve the naming convention of your variables so that it si obvious from context the meaning.

Modify the array constructor to use members to do the real work and make the code more readable and thus self documenting.

linked_list(T* others, size_t n) {
    for (int i = 0; i < n; i++) {
        mFirst = new node(*others, mFirst);
        others++;
    }
}


// More Self documenting
linked_list(T* others, size_t n) {
    for (int i = 0; i < n; i++) {
        append(others[n]);         // Note this is inefficient with only
                                   // mFirst (you would need an mLast
                                   // to make it efficient. But alternatively
                                   // you could insert at the beginning and insert
                                   // in reverse order.
    }
}

Copy constructor

linked_list(const linked_list &other)
    : mFirst(NULL),
    , mSize(0)
{
    for(Node* tmp = other.mFirst; tmp; tmp = tmp->next) {
        append(tmp->data);   // Same comment as above.
    }
}

Copy and Swap Idiom

linked_list& operator=(linked_list const& rhs)
{
     linked_list  copy(rhs);   // use copy constructor to copy.
     swap(copy);               // swap the content of this and copy.
     return *this;
}
// The object copy goes out of scope calling its destructor and
// thus cleaning up the original content of this object.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.