Singly Linked List Implementation (With Nodes)

Question

This code was recommended to me by my dear friend Jon after I wrote an implementation using arrays. With his help, I managed to create a Singly linked List similar to std::vector using Nodes.

#include <iostream>

template <class T>
class LinkedList
{
private:
    size_t _size;
public:

    class Node
    {
    public:
        Node* next;
        T value;
        Node(T val) : value(val), next(NULL) {}
    };

    Node* head;

    LinkedList() : _size(0), head(NULL) {}

    ~LinkedList() {
        std::cout << "Linked List Deleted!" << std::endl;
    }

    void push(T val) {
        Node* node = new Node(val);
        node->next = head;
        head = node;
        ++_size;
    }
    size_t size() {
        return _size;
    }
    bool empty() const {
        return head == NULL;
    }
    T pop() {
        Node* n = head;
        if (n == NULL) return NULL;
        head = n->next;
        _size--;
        return n->value;


    }
};

int main() {
    LinkedList<int> list;
    std::cout << "Empty: " << list.empty() << std::endl;
    list.push(5);
    list.push(6);
    list.push(7);
    list.push(8);
    list.push(9);
    list.push(10);
    std::cout << "Empty: " << list.empty() << std::endl;

    std::cout << "Size: " << list.size() << std::endl;
    list.pop();

    std::cout << "Size: " << list.size() << std::endl;
    LinkedList<int>::Node* n = list.head;
    while (n != NULL) {
        std::cout << n->value << std::endl;
        n = n->next;
    }
}

Answer 1

I recommend you compile with more warnings enabled. That would alert you to these problems:

g++ -std=c++11 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds  -Weffc++       208038.cpp    -o 208038
208038.cpp: In instantiation of ‘class LinkedList<int>’:
208038.cpp:50:21:   required from here
208038.cpp:4:7: warning: ‘class LinkedList<int>’ has pointer data members [-Weffc++]
 class LinkedList
       ^~~~~~~~~~
208038.cpp:4:7: warning:   but does not override ‘LinkedList<int>(const LinkedList<int>&)’ [-Weffc++]
208038.cpp:4:7: warning:   or ‘operator=(const LinkedList<int>&)’ [-Weffc++]
208038.cpp: In instantiation of ‘T LinkedList<T>::pop() [with T = int]’:
208038.cpp:61:14:   required from here
208038.cpp:40:31: warning: converting to non-pointer type ‘int’ from NULL [-Wconversion-null]
         if (n == NULL) return NULL;
                               ^~~~
208038.cpp: In instantiation of ‘LinkedList<T>::Node::Node(T) [with T = int]’:
208038.cpp:27:22:   required from ‘void LinkedList<T>::push(T) [with T = int]’
208038.cpp:52:16:   required from here
208038.cpp:14:11: warning: ‘LinkedList<int>::Node::value’ will be initialized after [-Wreorder]
         T value;
           ^~~~~
208038.cpp:13:15: warning:   ‘LinkedList<int>::Node* LinkedList<int>::Node::next’ [-Wreorder]
         Node* next;
               ^~~~
208038.cpp:15:9: warning:   when initialized here [-Wreorder]
         Node(T val) : value(val), next(NULL) {}
         ^~~~

The lack of consideration of copy/move behaviour is particularly concerning, given that we have a pointer which we own. The destructor is also faulty, failing to release the allocated resource:

valgrind -q --leak-check=full ./208038   
Empty: 1
Empty: 0
Size: 6
Size: 5
9
8
7
6
5
Linked List Deleted!
==18193== 96 (16 direct, 80 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 6
==18193==    at 0x4835E2F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18193==    by 0x1094BD: LinkedList<int>::push(int) (208038.cpp:27)
==18193==    by 0x109276: main (208038.cpp:57)
==18193== 

Remember the guideline - whenever you write new or new[], make sure you know where the corresponding delete or delete[] is! (Don't forget that you need a delete in the pop() method, too).

There's no need for Node to be a class:

struct Node
{
    T value;
    Node* next;
};

void push(T val) {
    head = new Node{std::move(val), head};
    ++_size;
}

I think it would be better if it didn't need to be public, either - there's nothing to stop broken code messing up the guts of the list. We'd like a way to iterate through the values of the list without having to understand its innards, and without being able to accidentally change it (potentially breaking the size invariant).

Finally, std::size_t is written incorrectly throughout, and is missing its header (<iostream> is not one of the headers specified to define this type).

Answer 2

Fast review:

Be sure about what you post

Actually your code isn't a linked list, but a stack implemented in term of simply linked list, which the underlying data is publicly accessible. A linked list (even simply linked) have a lot of things that your implementation is lacking.

---

Sidenote: Please, you post a lot of code but before posting ask yourself if your code is really ready to be reviewed. "What's the purpose of my code? How usable it is? Did it lack something or isn't fully implemented?" Proposing codes to be reviewed isn't just throw as much code as possible in lesser time.

---

Your code have a lot of memory leaks.

Even if the memory will be cleaned up by the program termination, it's a good habit to delete resource that you allocated once you don't need it anymore. Because, yes, the OS normally will clean not released memory, but then, it don't call destructor.

Consider using smart pointer they are better, safer, stronger (© DP).

---

Misc

• Prefer the C++ std::size_t to the C size_t (here's the difference)
• The member variable value have to be initialized after field next, because you declare it last. (more info)
• Use nullptr instead of NULL or 0. To know why, read this (and follow inside's links)
• Don't be redundant in your conditions: As explained in the Core Guideline, comparing a pointer to nullptr in a condition, not only is useless, but it's also much more verbose.
• Returning NULL in case of empty list when you call pop is a poor design and should be avoided. You have many better option here: returning a std::optional, using exceptions ans many other ways.
• Be consistent: at one place, you use pre-crementation, at other you use post-decrementation. There's a huge list of SO posts talking about post that.
• Take care that memory allocation can fail.