3
\$\begingroup\$

I've decided to learn a bit of C++, and so I've started with a simple linked list. There's no input to the program and should always output hlo. This is as in main I build a list consisting of hello, and use Get and last to get the data.

I don't know C++, or C, and so this is mostly a stab in the dark. I don't know if I'm using C++ correctly, but I got a working program where I'm mostly exploring pointers, so I would like to know if my usage for them is correct. Otherwise please review any and all aspects of my code.

#include <iostream>

class Node {
public:
    Node(char data_) {
        data = data_;
    }

    Node *next = NULL;
    char data;
};

class LinkedList {
public:
    Node *root = NULL;
    Node *last = NULL;
    LinkedList() {}

    void Add(char data) {
        if (root == NULL) {
            root = new Node(data);
            last = root;
        } else {
            last->next = new Node(data);
            last = last->next;
        }
    }

    char Get(int index) {
        return _Get(index)->data;
    }
private:
    Node* _Get(int index) {
        Node *node = root;
        for (int i = 0; i < index; i++) {
            if (node == NULL) {
                throw std::out_of_range("List doesn't contain that item.");
            }
            node = node->next;
        }
        return node;
    }
};

int main() {
    LinkedList list = LinkedList();
    list.Add('h');
    list.Add('e');
    list.Add('l');
    list.Add('l');
    list.Add('o');
    std::cout << list.Get(0) << list.Get(2) << list.last->data << std::endl;
    return 0;
}
\$\endgroup\$
3
\$\begingroup\$

Memory Leak

Your code leaks. I see calls to new but I see no smart pointers or calls to delete to reclaim the memory. You need a destructor on your linked list.

class LinkedList {
public:
    LinkedList()  {}
    ~LinkedList() {/* Reclaim dynamically allocated memory here */}
};

Rule of three

Once you correct for memory management you also realize that you are violating the rule of three. By default the compiler will automatically add copy constructor and assignment opertors for you.

LinkedList   a;
a.add('x');
LinkedList   b(a);   // Makes a copy of a
                     // But only a shallow copy.
a.add('y');
// This changes 'a' to be {'x', 'y}
// Problem is that b is now also {'x', 'y} 
// **BUT** in b last points at the wrong node.

// Now things get interesting:
b.add('z');
// Now a and b are {'x', 'z'} (if you follow from root)
// a.last still points {'y'} even though this is no longer
// in the chain pointed to from a.root

The default implementation of the copy constructor (and assignment operator) is to make a shallow copy of the members. This fine as long as your members are not owned pointers. But your pointers are owned (even though you missed the deletion). So you either need to implement the copy semantics of the class or explicitly remove these methods.

class LinkedList {
public:
    LinkedList()  {}
    ~LinkedList() {/* Reclaim dynamically allocated memory here */}
    LinkedList(LinkedList const&)            = delete;
    LinkedList& operator=(LinkedList const&) = delete;
};

Prefer nullptr

In C++11 we introduced nullptr to replace NULL. This is because NULL is the integer zero and can accidentally be converted to an integer type without any warning. nullptr on the other hand has a type of std::nullptr_t and can only be converted to pointer types (not integers).

Design.

When building linked lists I prefer to use a Sentinel object. This removes the need for checking for null in your list and thus makes the code easier to write and understand. There are a lot of C++ code reviews on linked lists where I explain the principle.

Node should be private

You declare Node publicly. There is no reason for people to know the implementation details of your linked list. Make this a private member of LinkedList so show that this is an implementation detail.

Prefer to use initializer list:

    Node(char data_) {
        data = data_;
    }

    // Prefer to write like this:

    Node(char data_)
        :data(data_)
    {}

For non pod types this is because the object are constructed before the body of the constructor is entered then the constructor code is applied. If data was a non pod object that means you would first be constructing it and then applying the assignment operator (ie initializing it twice).

For pod data it makes no difference, BUT does no harm either. So it is a good habit to get into. Because that way of the code is later modified to be a non pod type (i.e. CharUTF) then doing it the prefered way keeps the code optimal.

Not a fan

    Node *root = NULL;
    Node *last = NULL;

Personally I like to see all the members initialized in the initializer list. But I can see some advantages for objects with lots of constructors in avoiding writing the same thing repeatedly.

Style Check.

Most style guides for C++ (though this is not ubiquitous so just take as advice and not a rule). User defined types have an initial capital letter, while objects (which includes functions/methods) have an initial lowercase letter.

This is because the most important thing in C++ is the types. So it is useful to be able to quickly identify types from objects.

    void Add(char data) {
    // I would prefer
    void add(char data) {

Self Documenting code

Personally I don't like add() as the name of the function. It does not tell me exactly what the function does. I think a better name would be append().

Dont' use _ in identifers.

The rules on using underscore are non trivial. Even if you know them. Other people don't know them as well as they think they do. So best to avoid to prevent accidental mistakes.

    Node* _Get(int index) { // Note this is a reserved identifier.
                            // And being a common word is very likely
                            // to be used somewhere. including the
                            // wrong header file before this is likely
                            // to generate some confusing error messages
                            // on some systems.

    // Why Note
    Node* getNode(int index)

Bug

 LinkedList  a;
 a.Add('a');
 a.Get(1); // Undefined behavior.
           // I believe _Get() is going to return a `nullptr`
           // which is then dereferenced by Get()

Declaring variables

    LinkedList list = LinkedList();
                   // ^^^^^^^^^^^^  Creates a temporary object.

Technically this is creating a LinkedList temporary object then calling the copy constructor of list to copy the temporary object then destroying the temporary object.

Fortunately most compilers will spot this and optimize out the copy and destruction and just create your object.

But this is simpler to declare as:

    LinkedList list;

Prefer \n to std::endl;

The only difference is that std::endl performs an extra flush. Forcing a manual flush is usually never the correct solution as the libraries will do this for you when required.

Main and return

The main() function is special. If the compiler detects there is no return it will plant one for you.

    return 0;

So there is no need to add it yourself. It is become standard that when main can return no other value than 0 that the return 0 is omitted to indicate that the application can never fail. So when I see a return 0 at then end I generally look around for the other situations where it can fail. So if there are potentially failure situations and you exit early with an return 1; then add a return 0; and then end otherwise don't bother.

\$\endgroup\$
2
\$\begingroup\$

For the beginner, and given the scope of the program, looks good. Few remarks.

  • NULL is frowned upon. A politically correct NULL is nullptr.

  • void Add(char data)

    After the call, the newly added node becomes a last node, no matter what. You better make this explicit. I also recommend to document the invariant with assertion:

    void Add(char data)
    {
        Node * n = new Node(data);
        if (root == nullptr) {
            assert(last == nullptr);
            root = n;
        } else {
            assert(last != nullptr);
            last->next = n;
        }
        last = n;
    }
    
  • Node(char data)

    • next is undefined. Set it to nullptr explicitly.

    • C++ allows a cute shortcut Node(char data): data(data), next(nullptr) {}

  • Exposing next to public hardly has a reason. With it exposed, client is free to violate all invariants. To let a client iterate over the list, provide an iterator.

  • I don't see the point of delegating Get to a private member.

\$\endgroup\$
  • 1
    \$\begingroup\$ "next is undefined" No it's not, look at the declaration of next. \$\endgroup\$ – Rakete1111 Oct 20 '16 at 4:53
  • \$\begingroup\$ @Rakete1111 Point taken, see edit. \$\endgroup\$ – vnp Oct 20 '16 at 7:40
1
\$\begingroup\$

I see some opportunities for improvement, which will get this up to about what we expect from a LinkedList. First, the imposition that the stored elements are char is not optimal. Sooner or later you will want non-char elements, and you will not want to write and maintain another LinkedList for each data type you want. char is, in fact, the least useful element type I can think of. The solution is a template class; instance objects would be declared LinkedList <whateverType >; a programmer will expect this syntax and the reusabilty it produces.

Second, there should be no add method as it is unclear where the new element is added. Instead, we expect methods like insert(int index, T element) for O(index) insertion at index and O(N) append for what you are currently doing with add.

Third, you may recognize your add as being O(k); this is because you've actually written a queue (with minimal modification, a deque), which extends a real LinkedList. A real LinkedList has no need of a tail pointer (last here).

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice points, to be a pedant, I see add as \$O(1)\$ not as \$O(k)\$. But your points stand none the less. Thank you. \$\endgroup\$ – Peilonrayz Oct 20 '16 at 10:07

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.