C++ LinkedList Implementation

Question

I've been studying data structures and making implementations for different types. This is my linked list code. Please let me know if there's anything here that could be improved upon or changed for better performance. I should mention that it compiles and functions as intended.

Also, I'm not sure what I need the friend line and class prototype line for. I think the class prototype line stems from some intricate detail of how templates work on compilation, but I'm not sure what that is. As for the friend line, it's either that or I make a get() and set() function in the Node class. I'm not sure which would be better.

template <typename T> class LinkedList;  // Not sure why this needs to be... LOOK INTO IT

// Node CLASS ===================================
template <typename T>
class Node {
    friend class LinkedList<T>;  // Not sure why this needs to be... LOOK INTO IT
public:
    Node(T data);
    ~Node();
    T getData();
private:
    T mData;  // Some data stored by user
    Node<T>* mNextNode;  // Points to the next node in the list
};
// ==============================================

// LinkedList CLASS =============================
template <typename T>
class LinkedList {
public:
    LinkedList();
    ~LinkedList();
    void print();  // Prints the contents of each node in the list
    void insert(T data);  // Crafts a new node using the argument then inserts it properly into the list
    void remove(T data);  // Removes/deletes a node from the list
private:
    Node<T>* mHeadNode;  // Leading node in the list
    unsigned int mSize;  // Number of nodes in the list
};
// ==============================================

// Node IMPLEMENTATION ==========================
template <typename T>
Node<T>::Node(T data) {
    mData = data;
    mNextNode = nullptr;  // Creating a node has nothing to do with what comes after it
}

template <typename T>
Node<T>::~Node() {}  // Don't delete mNextNode or you'll end up deleting essentially every node in the list

template <typename T>
T Node<T>::getData() {
    return mData;
}
// ==============================================

// LinkedList IMPLEMENTATION ====================
template <typename T>
LinkedList<T>::LinkedList() {
    mHeadNode = nullptr;  // When a new list is created, there is no leading node
    mSize = 0;
}

template <typename T>
LinkedList<T>::~LinkedList() {
    if (mHeadNode) {  // No need to delete anything if the list is empty
        Node<T>* trailingNode = mHeadNode;  // Deletes each node in the list
        while (trailingNode) {  // Keep traversing list until we've hit nullptr, or end of list
            Node<T>* breadcrumbNode = trailingNode->mNextNode; // Iterator to traverse list. Directs trailingNode
                                                               // where to go after trailingNode deletes itself
            delete trailingNode;
            trailingNode = breadcrumbNode;  // Move forward in the list
        }
    }
}

template <typename T>
void LinkedList<T>::print() {
    Node<T>* traversalNode = mHeadNode;  // Iterator to traverse list
    while (traversalNode) {  // Keep traversing list until we've hit nullptr, or end of list
        cout << traversalNode->getData() << endl;  // Print the contents of each node
        traversalNode = traversalNode->mNextNode;  // Point to next node in the list
    }
}

template <typename T>
void LinkedList<T>::insert(T data) {
    Node<T>* nodeToInsert = new Node<T>(data);  // Craft the new node to be inserted using argument
    if (!mHeadNode) {  // If the list is empty, the new node should be the leading node
        mHeadNode = nodeToInsert;
    }
    else {  // Begin traversing the list to find the proper position for the new node
        Node<T>* nodeToCompareTo = mHeadNode;  // This traversal node's content will be compared with the new node's
                                               // content. Represents the node that will lie just ahead of the new node
                                               // after the new node is inserted
        Node<T>* trailingNode = nullptr;  // Represents the node that will lie just behind the new node. This traversal
                                          // node will always trail behind nodeToCompareTo by one position
        while (nodeToCompareTo) {  // Traverse the list until we hit the end nullptr
            if (nodeToCompareTo->getData() >= nodeToInsert->getData()) {
                break;  // Found the new node's proper position
            }
            else {
                trailingNode = nodeToCompareTo;  // Trailing node needs to move to catch up with comparison node
                nodeToCompareTo = nodeToCompareTo->mNextNode;
            }
        }
        if (nodeToCompareTo == mHeadNode) {  // New node should be the new leading node
            nodeToInsert->mNextNode = mHeadNode;  // Don't loose sight of the old head node
            mHeadNode = nodeToInsert;  // Now that we have sight of the old head node, replace it with the new node
        }
        else {  // New node needs to be positioned somewhere in the list, not at the head
            nodeToInsert->mNextNode = nodeToCompareTo;  // nodeToCompareTo represents the new node's front neighbor
            trailingNode->mNextNode = nodeToInsert;  // trailingNode represents the new node's back neighbor
        }
        mSize++;
    }
}

template <typename T>
void LinkedList<T>::remove(T data) {
    if (!mHeadNode) {  // Check if the list is empty
        cout << "List is empty..." << endl;
    }
    else {
        Node<T>* nodeToCompareTo = mHeadNode;  // Argument will be compared with this node's data. If there's a match,
                                               // we will delete the node that this traversal node points to
        Node<T>* trailingNode = nullptr;       // Trails nodeToCompareTo. Keeps track of removed node's back neighbor
                                               // so we can redirect its pointer after removal
        while (nodeToCompareTo) {  // Traverse the list until it ends
            if (nodeToCompareTo->getData() == data) {  // Does targeted node's data match argument data?
                break;
            }
            else {
                trailingNode = nodeToCompareTo;  // Trail nodeToCompareTo as it iterates through the list
                nodeToCompareTo = nodeToCompareTo->mNextNode;
            }
        }
        if (!nodeToCompareTo) {  // Check if the traversal node has fallen off the list without a match
            cout << "Node not found..." << endl;
        }
        else if (nodeToCompareTo == mHeadNode) {  // Check if the node to remove is the leading node
            mHeadNode = mHeadNode->mNextNode;  // Shift the head node one iteration further
            delete nodeToCompareTo;  // Delete the old head node from the list
            mSize--;
        }
        else {  // Node found was somewhere within the list, not the leading node
            trailingNode->mNextNode = nodeToCompareTo->mNextNode;  // Node to be removed's back neighbor should "skip"
                                                                   // its mNext pointer to the node after the one that
                                                                   // is about to be deleted
            delete nodeToCompareTo;  // Delete the targeted node from the list
            mSize--;
        }
    }
}
// ==============================================

Answer 1

The review will unfortunately be mostly tutorial style, since I assume the code is a consequence of low familiarity with the language. But, I'll just leave some keywords or clues on what to google for. Knowing how to google efficiently is a very useful skill.

I'll make it top to bottom style.

template <typename T> class LinkedList;

There is a term for the expression you've written. It is only used when current translation unit (usually a .cpp file) doesn't need the definition of the declared class (I've slightly unveiled the term). Example can be storing pointer/reference to it.

template <typename T>
class Node {
    friend class LinkedList<T>;  // Not sure why this needs to be... LOOK INTO IT
public:
    Node(T data);
    ~Node();
    T getData();
private:
    T mData;  // Some data stored by user
    Node<T>* mNextNode;  // Points to the next node in the list
};

C++ has structs. Always preferring class usually suggests Java background. You should know that structs are not prohibited (google when is it appropriate to use either, first SO link should be the right one).

Also, add some newlines to decrease the length of the lines (especially with longer comments). It is easier to move head down/scroll down than moving head to the right. Generally, it improves readability.

Node(T data);

Again suggests Java background. Try to google about C++ constructors. You'll see how the situation is complicated. You might also stumble upon a rule of 0,3,5.

~Node();

Compiler generates default one for you. You should omit both declaration and definition.

T getData();

There is a very big problem with this. Think about difference between Java and C++ about variables (if container with immutable elements is not meant, of course).

Node<T>* mNextNode;

There is no need to write Node<T> inside of Node, just write Node, compiler will understand you.

---

Exposing implementation:

Node<> should be private to LinkedList<>, since users don't need to care about it.

---

Incomplete:

May be it was intended, but for now the LinkedList<> is incomplete and lacks numerous useful functions.

---

template <typename T>
LinkedList<T>::LinkedList() {
    mHeadNode = nullptr;  // When a new list is created, there is no leading node
    mSize = 0;
}

When searching about constructors, you'll probably find out a better way of writing this (hint: google member initialization list).

void print();  // Prints the contents of each node in the list
void insert(T data);  // Crafts a new node using the argument then inserts it properly into the list
void remove(T data);

Where does print prints to? std::cout, or any other stream?

Where does insert inserts to? Which element remove removes? Looking at the implementation it looks you've written a stack, not linked list.

Also, after reading about constructors, you should rethink the way you take data (currently it is by value).

unsigned int mSize;

There is a typedef for the data type you need. unsigned int is not always the right choice.

mHeadNode = nullptr;

This line is written right. Use nullptr, not 0 or NULL.

Print:

print() function is a consequence of lack of iterator based or index based access. With iterators you could write container independent print function.

Destructor:

Destructor is done right as well. Though you could just return if the head is nullptr, and then everything would be one indentation unit closer to the left.

insert():

Behavior of this function is even more weird. So it turns out that the structure is a hybrid of set and stack. Some people want it, but in a more specific situations. You wanted a linked list, so you didn't write what you wanted. Try to have a look at C++'s std::list<> or std::forward_list<> to get idea of what is expected.

        if (nodeToCompareTo->getData() >= nodeToInsert->getData()) {
            break;  // Found the new node's proper position
        }
        else {

No need to write else after break or return, since control won't reach else if the control goes inside of if.

remove():

This function suggests that you've written using namespace std (from cout, since it should be std::cout). Don't do it, especially in global scope in header files. Also, do users want to see the message on the screen? It seems like it is left for debugging purposes. You should just do nothing (since it is expectable behavior) if the list is empty.

In my opinion, it is overly complicated. You could write it like this: keep previous and current element, loop until size, and if current is matching you can achieve constant time deletion, and also decrement the size to not step over the list. Since first one is edge case, you'll need another while loop to make sure you won't remove from the beginning.

Not the end of the story:

The points are actually what came to mind from the first read. I'm afraid there are more problems. I recommend you to pick up a book on C++, preferably from this list.