Is this a proper singly linked list?

Question

/*
 * LinkedList.h
 *
 *  Created on: Mar 9, 2014
 *      Author: steven
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <iostream>
using std::cout;
using std::endl;

template<class T>
class LinkedList {

    template<class E>
    struct Node {
        Node<E> *rightNode;
        E data;
        Node() {
            rightNode = NULL;
        }
    };
private:
    Node<T> *startNode;
    int size;
public:
    LinkedList() {
        startNode = NULL;
        size = 0;
    }
    void pushFront(T data) {
        if (size > 0) {
            Node<T> *temp = new Node<T>();
            temp->data = data;
            temp->rightNode = startNode;
            startNode = temp;
            size++;
            return;
        }
        pushBack(data);
    }
    void pushBack(T data) {
        if (size > 0) {
            Node<T> *temp = startNode;
            for (int i = 0; i < size - 1; i++) {
                temp = temp->rightNode;
            }
            temp->rightNode = new Node<T>();
            temp->rightNode->data = data;
            size++;
            return;
        }
        startNode = new Node<T>();
        startNode->data = data;
        size++;

    }

    T get(int num) {
        if (num > 0) {
            Node<T> * temp = startNode; //1
            for (int i = 0; i < num - 1; i++) {
                temp = temp->rightNode;
            }
            T tempData = temp->rightNode->data;
            delete temp;
            return tempData;
        } else {
            return startNode->data;
        }
    }
    void removeBack() {
        if (size > 2) {
            Node<T> *temp = startNode;
            for (int i = 0; i < size - 2; i++) {
                temp = temp->rightNode;
            }
            delete temp->rightNode;
            temp->rightNode = NULL;
        } else if (size == 2) {
            delete startNode->rightNode;
            startNode->rightNode = NULL;
        } else {
            delete startNode;
            startNode = NULL;
        }
        size--;

    }
    void printLinkedList() {
        Node<T> *temp = startNode;
        cout << temp->data << endl;
        for (int i = 0; i < size - 1; i++) {
            temp = temp->rightNode;
            cout << temp->data << endl;
        }
    }
    int getSize() {
        return size;
    }
    virtual ~LinkedList() {
        if (size > 2) {
            Node<T> *temp = startNode;
            while (temp->rightNode->rightNode != NULL) {
                Node<T> *currentTemp = temp;
                temp = temp->rightNode;
                delete currentTemp;
            }
            return;
        }
        if (size == 1) {
            delete startNode;
            return;
        }
        if (size == 2) {
            delete startNode->rightNode;
            delete startNode;
            return;
        }

    }
};

#endif /* LINKEDLIST_H_ */

Please critique the singly linked list, specifically the working aspect of it (making sure deleting correctly, etc.).

Answer 1

When possible, use an initializer list:

Node() : rightNode()
{ }

---

I don't think you're using C++11, but in case you are, use nullptr.

---

Giving Node a full constructor would be very advantageous for simplifying a lot of boilerplate code.

For example, everything like:

Node<T> *temp = new Node<T>();
temp->data = data;
temp->rightNode = startNode;

Could become a one liner:

Node* temp = new Node(data, startNode);

Also, a proper constructor avoids the exception safety problem that user1703394 mentioned.

Just for reference, the Node with a constructor would look like:

struct Node {
    T data;
    Node *rightNode;

    Node(const T& val, Node* rightNode) : data(val), rightNode(rightNode)
    { }
};

Note that the member order was changed since it needs to match the initialization list order. Changing the order allowed the constructor to be more natural (since the constructor argument order should match the initialization list order).

---

In C++, it's much more common to see T* var rather than T *var. It's just a stylistic qualm, but something to be aware of.

---

You should have blank lines between your methods.

---

A non-constant operator shouldn't exist on a list. If you can't provide it in constant time, don't provide it. It's very non-standard, and it's misleading to a consumer of the class. Note that the idiomatic way to expose the data is via a forward iterator.

---

There's a grave lack of understanding of memory ownership in get. In particular, unless you want the ownership of the node to end, you should not be freeing it.

As a general piece of advice, whenever you have doubts about memory management, consider using something like valgrind.

---

Try to simplify your code down to a general case rather than having lots of special cases. As others have noted, a sentinel node can heavily simplify this. As a random note, if you do use a sentinel node, and you're concern about performance, try to not dynamically allocate it. That saves you an allocation on an empty list.

---

Is LinkedList actually ever going to be extended (as implied by the virtual destructor)? Considering all of the properties are private and none of the methods (other than destructor) are virtual, there's not really a meaningful way that you can extend it.

---

Don't use the implicit private visibility of classes. Everything should be in either a public, private, or protected block. (There's nothing technically wrong with it of course, it's just good to be consistent.) Note that this doesn't apply to structs. Structs are almost always only public, so there's no potential confusion.

---

Be mindful of what can cause copies. In particular, get can cause an extra copy for no reason. T tempData = temp->rightNode->data; creates a copy, and then returning could, in theory--though never in practice--create a copy. If you just return directly, you can avoid a possible copy (though one will still have to happen).

---

Better yet, should get really be returning a copy? You could be returning either a reference or const reference (depending on if either a const or non-const version of get is called) so that the caller can modify the data, or so that a needless copy can be avoided in the read-only situation.

---

Your header stuff should have more spacing in it:

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

#include <iostream>

using std::cout; // These should not be here!
using std::endl;

---

#endif /* LINKEDLIST_H_ */

The comment is just useless noise unless you have a lot of nested directives. Considering you only have one, this comment is useless. Also, most modern IDEs make these types of comments useless even if there are a ton of directives since they can highlight the counterpart. (I'm of the school of thought that even without highlighting, if there's enough levels for the comments to be necessary, something is very, very wrong with the the structure of the code.)

---

There's not a technical need to do so, but it's nice to try to be consistent with the standard library. This allows someone who is using your class for the first time to very intuitively pick up it's use. For example, I would expect size() rather than getSize(). I also might use pop instead of remove.

---

Sometimes an else clause is less confusing than a hidden return, especially in void functions. For example, the following is much clearer to me:

void pushFront(T data) {
    if (size > 0) {
        Node<T> *temp = new Node<T>();
        temp->data = data;
        temp->rightNode = startNode;
        startNode = temp;
        size++;
    } else {
        pushBack(data);
    }
}

I actually had to stop and pause for a long moment the first time I read through your code to make sure you weren't adding twice.

---

There are a lot of const correctness issues in your code. Please look into it. The short explanation is that any time something is only being read, it should be accepted by const reference.

---

Consider having each node own it's rightNode. This would mean that instead of a looping destructor, you could simple delete the head node and let the deletion cascade. This would work particularly well with a automatically allocated sentinel node since it would mean you could have a default destructor in the list.

---

Sized based looping on a linked structure is rather rare. The standard way to do it is to loop on the pointers. In the situations you've used it though, the uses are arguably just as clear as the pointer case.

---

Consider keeping a tail pointer. That lets you push and pop to/from the end in constant time.

Answer 2

Bugs

For a header-only library, using std::cout and using std::endl are unacceptable side effects.

The LinkedList<T>::Node<E> class should just be LinkedList<T>::Node, and it should be private.

get(int), printLinkedList(), and getSize() should be const methods.

get(int) should not call delete. There's no corresponding new, and furthermore it should be a read-only operation.

Style

Instead of a printLinkedList() method, define an operator that allows the list to be sent to any std::ostream:

friend std::ostream &operator<<(std::ostream &out, const LinkedList<T> &list) {
    Node *temp = list.startNode;
    out << temp->data << std::endl;
    for (int i = 1; i < list.size; i++) {
        temp = temp->rightNode;
        out << temp->data << std::endl;
    }
    return out;
}

You shouldn't need more than one base case in removeBack() and ~LinkedList(). For example, removeBack() could be

void removeBack() {
    if (size == 1) {
        delete startNode;
        startNode = NULL;
    } else {
        Node *temp = startNode;
        for (int i = 2; i < size; i++) {
            temp = temp->rightNode;
        }
        delete temp->rightNode;
        temp->rightNode = NULL;
    }
    size--;
}

In fact, nearly every one of your methods has a special case to handle an empty list. Not only is that tedious, it also doubles the number of tests you would have to write to get complete code coverage. It would be much more advantageous to use a "dummy" node as the head to eliminate all of those special cases.

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <iostream>

template<class T>
class LinkedList {

private:
    struct Node {
        Node *rightNode;
        T data;
        Node() {
            rightNode = NULL;
        }
    };
    Node head;
    int size;

public:
    LinkedList() {
        size = 0;
    }

    void pushFront(T data) {
        Node *temp = new Node();
        temp->data = data;
        temp->rightNode = head.rightNode;
        head.rightNode = temp;
        size++;
    }

    void pushBack(T data) {
        Node *temp = &head;
        for (int i = 0; i < size; i++) {
            temp = temp->rightNode;
        }
        temp->rightNode = new Node();
        temp->rightNode->data = data;
        size++;
    }

    T get(int num) const {
        Node *temp = head.rightNode;
        for (int i = 0; i < num; i++) {
            temp = temp->rightNode;
        }
        return temp->data;
    }

    void removeBack() {
        Node *temp = &head;
        for (int i = 0; i < size; i++) {
            temp = temp->rightNode;
        }
        delete temp->rightNode;
        temp->rightNode = NULL;
        size--;
    }

    friend std::ostream &operator<<(std::ostream &out, const LinkedList<T> &list) {
        Node *temp = list.head.rightNode;
        for (int i = 0; i < list.size; i++) {
            out << temp->data << std::endl;
            temp = temp->rightNode;
        }
        return out;
    }

    int getSize() const {
        return size;
    }

    virtual ~LinkedList() {
        Node *temp = head.rightNode;
        for (int i = 0; i < size; i++) {
            Node *del = temp;
            temp = temp->rightNode;
            delete del;
        }
    }
};

#endif /* LINKEDLIST_H_ */

Answer 3

There seems to be an exception safety bug:

If T::operator=(T&) throws in LinkedList< T >::pushFront you will leak a Node< T >.

Answer 4

When adding items to a list one of the most common operations is to add them to the back of the list. Your implementation makes that an O(n) operation while it should be O(1) - so consider keeping a tail pointer as well.