6
\$\begingroup\$

I haven't done much C++ coding the last few years, so I've been reviewing in preparation for upcoming interviews. I wrote a minimally functional singly linked-list. I'm using my implementation for practicing interview problems and hopefully later to build more complex data structures.

Currently, the code is not templatized since I've been focusing on the basics more than wide usability. I've made the head and tail pointers protected because of how I code up practice problems - each one is a derived class where I implement the required functions and they often require modifying head and/or tail.

Style-wise, I've at least tried to use the Google C++ Style Guide. Please provide feedback on the overall design, improvements, style, and others.

Header:

#ifndef LINKED_LIST_H
#define LINKED_LIST_H
struct Node
{
    int data;
    Node *next = nullptr;
};

class LinkedList
{
    public:
        LinkedList();
        LinkedList(const LinkedList &list);
        ~LinkedList();
        LinkedList & operator=(const LinkedList &other);
        LinkedList & operator+=(const LinkedList &rhs);
        friend LinkedList operator+(const LinkedList &lhs, const LinkedList &rhs);

        bool IsEmpty() const;
        void Append(int value); // add to end
        void Insert(int value); // add to beginning
        void Print() const;

    protected:       
        // Protected so that derived class can modify these directly
        Node *head;
        Node *tail; // allows O(1) append

    private:
        void swap(LinkedList &other);

};

#endif

Implementation:

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

LinkedList::LinkedList(): head(nullptr), tail(nullptr) 
{
}

LinkedList::LinkedList(const LinkedList &list): LinkedList() // call base constructor
{
    Node *curr = list.head;
    while(curr != nullptr)
    {
        this->Append(curr->data);
        curr = curr->next;
    }
}

LinkedList::~LinkedList()
{
    Node *curr = head;
    while (curr != nullptr)
    {
        Node *next = curr->next;
        delete curr;
        curr = next;
    }
    head = tail = nullptr;
}

void LinkedList::swap(LinkedList &other) 
{
    using std::swap;
    swap(this->head, other.head);
    swap(this->tail, other.tail);
}

// Operator '=': use copy-and-swap idiom
LinkedList & LinkedList::operator=(const LinkedList &other)
{
    LinkedList temp(other); // Use copy constructor to make deep local copy
    this->swap(temp);       // Swap contents, destroy local list with old data
    return *this;
}

LinkedList & LinkedList::operator+=(const LinkedList &rhs)
{
    LinkedList *addition = new LinkedList(rhs); // make deep copy of passed in list
    if (this->IsEmpty())
        head = addition->head;
    else
        tail->next = addition->head;
    tail = addition->tail;

    // Destroy deep copy members but not what they point to
    addition->head = addition->tail = nullptr;
    delete addition;

    return *this;
}

LinkedList operator+(const LinkedList &lhs, const LinkedList &rhs)
{
    LinkedList result(lhs); // make deep local copy 
    result += rhs;
    return result;
}

bool LinkedList::IsEmpty() const
{
    return head == nullptr;
}

void LinkedList::Append(int data)
{
    Node *new_node = new Node;
    new_node->data = data;
    if (IsEmpty())
    { 
        head = tail = new_node;
        return;
    }
    tail->next = new_node;
    tail = new_node;
}

void LinkedList::Insert(int data)
{
    Node *new_node = new Node;
    new_node->data = data;
    new_node->next = head;
    head = new_node;
    if (tail == nullptr)
        tail = head;
}

void LinkedList::Print() const
{
    Node *curr = head;
    while(curr != nullptr)
    {
        std::cout << curr->data << "-->";
        curr = curr->next;
    }
    std::cout << "nullptr";
    std::cout << " [head = " << ((head == nullptr) ? (-1) : (head->data)) << "], [tail = " << 
        ((tail == nullptr) ? (-1) : (tail->data)) << "]" << std::endl;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that you haven't followed the Google C++ Style Guide (though it's better that you don't). You've used a raw new, which throws an exception on failure (forbidden by the Google C++ Style Guide). \$\endgroup\$ – Jerry Coffin Apr 16 '16 at 6:00
  • \$\begingroup\$ I see, I'm mostly using it for the naming and declaration order conventions. I admit I haven't read the entire guide and I'm definitely not adhering to much of the Google-isms (like no exceptions). \$\endgroup\$ – ruslank Apr 16 '16 at 6:18
2
\$\begingroup\$

If, instead of just writing new, you write new (std::nothrow), then if new fails, it will return a nullptr instead of throwing an exception. Then check if the result was nullptr. Some basic error checking like this isn't going to slow your program down if you're already using linked lists, which are inherently of the devil when it comes to performance.
Also, I don't think an employer would like to see code that might cause bugs. They rather see slower code than code that will cost them development time, I suspect. (I am definitely not an expert on that subject, though.)

I'm also not sure why you keep writing this-> in lots of places, such as this->Append(curr->data);. In case you didn't know, this-> is implicit, so you're only cluttering the code.

At the end of the destructor, you've written head = tail = nullptr;. I'm not sure what the point is, since the very next line, those member functions will be gone as the object is deleted. Just a thought. Perhaps you have some reason for it, I'm just pointing it out as I see it.

Your assignment operators do not check for self-assignment. At the start, check to see if this == &rhs. Even if it still "works", you're making a copy of "yourself", and then swapping yourself with the copy, which is clearly useless.

It would also probably be a good idea to see if the list you're trying to add in operator+= is actually empty, in which case you shouldn't do anything.

Lastly, you should mark all functions that do not throw any exceptions as noexcept, similarly to how you mark some functions as const. That is, unless you're using some older version of C++, for some reason.

I would personally make Struct Node a member structure of LinkedList, but that is a design choice, really, and not of much relevance.

Other than this, it looks pretty neat and good. Good work, I'd say. If I missed anything, perhaps others will care to point those things out.

\$\endgroup\$
  • \$\begingroup\$ The destructor code used to be in a standalone DeleteList function that basically restored the list to an empty state; I just copied it over to the destructor so as you say - that last line doesn't make sense now. \$\endgroup\$ – ruslank Apr 17 '16 at 17:30
  • \$\begingroup\$ I thought the copy-and-swap idiom eliminates the need for self-assignment in the "=" operator. stackoverflow.com/questions/3279543/… \$\endgroup\$ – ruslank Apr 17 '16 at 17:32
  • \$\begingroup\$ @ruslank But do you actually want it to be able to do self-assignment? When is there ever a point to doing x=x? If someone writes that, then I would assume they made a mistake. I might even go so far as to report it as an error, since I don't see why anyone would intend to do that. \$\endgroup\$ – antiHUMAN Apr 18 '16 at 6:44
  • \$\begingroup\$ I'm no expert and don't have a good example but it seems like a common thing to allow: isocpp.org/wiki/faq/assignment-operators \$\endgroup\$ – ruslank Apr 18 '16 at 7:45
  • \$\begingroup\$ @ruslank I'm not an "expert" either, so don't take my word as law. I looked at your link, and I'm not sure what you mean. They agree that you should check for self-assignment. Whether to treat it as an error or not is a different thing, but the code should be aware of self-assignment and should handle it in some appropriate way. Sometimes only to improve performance, and other times to avoid bugs. \$\endgroup\$ – antiHUMAN Apr 18 '16 at 12:55
2
\$\begingroup\$

I'm not going to pick on the implementation, the other answer did that already.


Please don't re-invent the wheel. There is nothing wrong with wanting to re-implement linked lists, but you also re-invented the interface.

Your interface is not compatible with any of the standard ones, neither STL, nor boost, nor anything else.

There are some strange design choices in that interface, you ended up placing e.g. a LinkedList::Print method in that class, but completely omitting a basic functionality: Iterators.

And neither does your implementation include any functionality which you would typically associate with a linked list, namely insertion at arbitrary points.

You also mentioned in the comments that you intent do derive from this class, and yet not a single method of that class is virtual.


LinkedList::Print is also awkward for another reason, and that is being hard wired to std::cout. An acceptable compromise would have been to overload operator<< on std::ostream for debug purposes instead.

But that's not all, it's providing debug information on the inner structure of the class, not a simple serialization as you would expect from a function with that name.


If you had tried to implement iterators, you would also have encountered another design flaw, and that is the visibility of Node and its attributes. You don't want that struct to be visible to the outside at all, and if you ever gave out a reference to an instance, it would be easy to accidentally break your list.


No move constructor?

There is no need to perform a deep copy if the parameter is a "rvalue-reference".

\$\endgroup\$
  • \$\begingroup\$ As I understood it, it is being used for practice and/or for job application. "Re-inventing the wheel" for the sake of practice is perfectly valid, as I see it. \$\endgroup\$ – antiHUMAN Apr 18 '16 at 12:56
  • \$\begingroup\$ I've done some reading on move semantics but I don't know too much about it. It seems like it could definitely come in handy. The last time I wrote non-trivial C++ code was ~2011 so I've been catching up on the C++11 standard lately. \$\endgroup\$ – ruslank Apr 19 '16 at 7:52
  • \$\begingroup\$ I want to make 'Node' private since none of the derived classes will need to change that data structure. However, the protected data members head and tail are declared first in the code. I couldn't forward declare a protected node structure since the visibility is different - is there a standard way to do this? \$\endgroup\$ – ruslank Apr 19 '16 at 8:23

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.