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

• Dan Oberlam: 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?
• Hagen von Eitzen: display_all: Instead of hard-coding it as output to cout, allow output to an arbitrary ostream. Better yet, rewrite this to override operator <<

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.

• Tom Gebel: Thanks. Can you please explain further what you mean by "streamlining"?
• vnp: @TomGebel See here, especially the second meaning; the emphasis on simpler. A very important concept in software engineering.
• Tom Gebel: Oh, haha thanks. I thought it might be a technical term, english is not my mother tongue.
• Deduplicator: Actually, making Node a simple struct simplifies implementation of linked_list, and is thus the way to go.
• Hagen von Eitzen: 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)

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

• Deduplicator: 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.
• Useless: 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.
• Deduplicator: True enough. I wonder why nobody mentioned the rule-of-three though.
• Useless: 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.