Implementation of Singly Linked List (C++)

Question

I tried to implement a singly linked list myself, sorry it is not commented but I think it should be pretty self-explanatory, if not feel free to comment. I know that using namespace std; is not optimal, but I figured it would be okay for this little example. Same goes for defining the class right in the main.cpp file (and in the declaration). I have two questions:

1. Is this even a correct implementation or did I miss something important? The methods worked as expected for me.
2. Would it make any sense to use smart pointers here? If yes, why? And what would I have to change for it to work?

Thank you for your time, I would appreciate any answers! :)

#include <iostream>

using namespace std;

struct Node
{
int32_t data;
Node* next;
};

class linked_list
{
public:

linked_list() : last{ NULL }, tmp{ NULL }, begin{ NULL } {};

~linked_list()
{
    clear();
}
void push_back(int32_t data)
{
    if (begin)
    {
        tmp = new Node;
        tmp->data = data;
        tmp->next = NULL;

        last->next = tmp;
        last = tmp;
        tmp = NULL;
    }
    else
    {
        begin = new Node;
        begin->data = data;
        begin->next = NULL;
        last = begin;
    }
}
void display_all()
{
    if (begin)
    {
        tmp = begin;
        while (tmp)
        {
            cout << tmp->data << endl;
            tmp = tmp->next;
        }
        tmp = NULL;
    }
    else
    {
        cout << "List is empty." << endl;
    }
}
void clear()
{
    while (tmp != last)
    {
        tmp = begin->next;
        delete begin;
        begin = tmp;
    }
    delete last;
    begin = NULL;
    tmp = NULL;
    last = NULL;
    }
private:
    Node* last;
    Node* begin;
    Node* tmp;
};

PS:

(Someone told me this would fit better on this site than on Stack Overflow so I am reposting.)

Answer 1

• struct Node would benefit from its own constructor. As a side note, if you don't want to expose struct Node to the client (and trust me, you don't), better make it private to class LinkedList.

• tmp doesn't deserve to be a class member. It is strictly local to each method.

• DRY. push_back could and should be streamlined:

    struct Node * tmp = new Node(data);
    if (begin) {
        last->next = tmp;
    } else {
        begin = tmp;
    }
    last = tmp;
  

• display_all should not print anything on the empty list. The caller might be greatly confused.

• clear could and should be streamlined. Run the loop till nullptr:

    while (begin) {
        struct Node * tmp = begin->next;
        delete begin;
        begin = tmp;
    }
    last = nullptr;
  

  As a side note, prefer nullptr to NULL.

Answer 2

General Observations

Welcome to Code Review. It is helpful when you provide the code that tested the class as well as the class so that we can do a better code review.

As noted by VNP modern C++ uses nullptr rather than NULL, this helps differentiate it from the C programming language.

Obvious additional possible methods are addNode(), and deleteNode() although the push back method does basically implement the addNode() method. A method to search through the linked list might also be helpful.

As VNP also noted it would be better if the class linked_list contained the class Node.

If you follow VNP's advice about display_all() then that method becomes much simpler because the while loop won't be entered at all if begin is equal to nullptr.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Answer 3

There's an implementation trick for linked lists which simplifies a lot of the logic. If your per-node data isn't too large that this is wasteful, consider

class linked_list
{
  struct Node
  {
    int32_t data;
    Node* next;
  };

  Node sentinel {0, nullptr};
  Node *last {&sentinel};

  // ...
};

Now: you don't need a special case for an empty list, because last is always non-NULL. Just replace references to begin with sentinel.next.

See how vnp's streamlined push_back becomes simpler still:

void push_back(int32_t data)
{
  struct Node *tmp = new Node{data};
  last->next = tmp;
  last = tmp;
}

---

Potential improvements:

• if the per-node data is too large, you can split the Node type into two parts:

    struct NodeLink { NodeLink *next; };
    struct Node : public NodeLink { LargeObject data; };
  
    NodeLink sentinel {nullptr};
    NodeLink *last {&sentinel};
  

  This will add some casts when you're returning data, but doesn't otherwise complicate things too much.

• if sentinel does contain data, and if your data type has a well-known "invalid" value, you should probably store that in sentinel. You should never be reading that field, so it's sensible to make it easy to detect.

• consider documenting your class invariants, even when you don't comment every individual method. These invariants often give you clear conditions you can assert on, or write unit tests for, if things aren't behaving as you expect. For example:

  1. last must never be nullptr
  2. last->next must always be nullptr
  3. sentinel.next must never point to sentinel (there are uses for circular lists, but that isn't what you've chosen to write)
  4. sentinel.data (assuming the original Node structure) must never be read or written
  5. there must be no cycles in the list