7
\$\begingroup\$

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.)

\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Code Review! We only review working code here - after reading the body of your post it sounds like it does work, but your title makes it sound like you aren't sure. Can you edit your question to make the title & body explicit that this works to the best of your knowledge? \$\endgroup\$ – Dannnno Oct 28 at 21:59
  • \$\begingroup\$ display_all: Instead of hard-coding it as output to cout, allow output to an arbitrary ostream. Better yet, rewrite this to override operator << \$\endgroup\$ – Hagen von Eitzen Oct 30 at 7:10
8
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks. Can you please explain further what you mean by "streamlining"? \$\endgroup\$ – Tom Gebel Oct 28 at 23:18
  • \$\begingroup\$ @TomGebel See here, especially the second meaning; the emphasis on simpler. A very important concept in software engineering. \$\endgroup\$ – vnp Oct 28 at 23:54
  • \$\begingroup\$ Oh, haha thanks. I thought it might be a technical term, english is not my mother tongue. \$\endgroup\$ – Tom Gebel Oct 29 at 0:08
  • \$\begingroup\$ Actually, making Node a simple struct simplifies implementation of linked_list, and is thus the way to go. \$\endgroup\$ – Deduplicator Oct 29 at 10:48
  • \$\begingroup\$ For clear, this is not just streamlining - in the OP version it is not clear to me why tmp != last upon entry when the list is not empty (though this is possibly true somehow) \$\endgroup\$ – Hagen von Eitzen Oct 30 at 7:12
7
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That can be done without storing a full Node in the linked_list class: Separate out the links, store them first, and store one set in the linked_list. Only convert from pointer to links to pointer to full Node when and if the Node must be destroyed or its data accessed. \$\endgroup\$ – Deduplicator Oct 29 at 23:25
  • 1
    \$\begingroup\$ True, although I wanted to keep it simple for the my first linked list implementation. I'm always surprised at how many tutorials miss out good practice even on the simplest structures. \$\endgroup\$ – Useless Oct 30 at 10:04
  • \$\begingroup\$ True enough. I wonder why nobody mentioned the rule-of-three though. \$\endgroup\$ – Deduplicator Oct 30 at 13:34
  • 1
    \$\begingroup\$ I really thought this answer was long enough covering only the core (more-or-less language agnostic) data structure. Actually coding the whole thing to what I'd consider a good standard seems ... probably worthwhile, but more effort than I have to spare. \$\endgroup\$ – Useless Oct 30 at 14:20

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.