Singly linked list class

Question

I have created this program about using a singly linked list class that implements several functions: Add, Display and Sort.

Could you suggest me how to make my code better and which functions to include in the future?

#include <iostream>
using namespace std;
// ----------------------------------------------------
class Node {
private:
 int value;
 Node *next;
public:
 Node(int v) { value = v; next = NULL; }
 void Add(int v);
 void Print();
 void SortValues();
 void SortNodes();
};
// ----------------------------------------------------
void Node::Add(int v)
{
 Node *newItem = new Node(v);
 Node *temp = this;
 while (temp->next != NULL)
 temp = temp->next;
 temp->next = newItem;
}
void Node::Print()
{
 Node *temp = this;
 while (temp != NULL)
 {
 cout << " " << temp << " : " << temp->value << endl;
 temp = temp->next;
 }
}
void Node::SortValues()
{ 
 Node *swapCandidate = next;
 Node *current;
 Node *min;
 // L* temp;
 // Look at every value
 while (swapCandidate != NULL)
 {
 current = swapCandidate;
 min = swapCandidate;
 // ------------------------------
 while (current != NULL)
 {
 if (current->value < min->value)
 {
 min = current;
 }
 current = current->next;
 }
 if(min != swapCandidate)
 {
 int tempV = min->value;
 min->value = swapCandidate->value;
 swapCandidate->value = tempV;
 }
 // ------------------------------
 swapCandidate = swapCandidate->next;
 }
 }
 // ----------------------------------------------------
void main()
{
// Sort - moving values
Node *myList = new Node(0);
myList->Add(15);
myList->Add(3);
myList->Add(20);
myList->Add(1);
myList->Print();
myList->SortValues();
cout << "------------------------------" << endl;
 myList->Print();
system("pause");
}

Answer 1

Don't use using namespace std;

It's bad practice that can cause a lot of problems that are easy to avoid, most people are used to the prefix, and three letters aren't that hard to type.

---

Don't use system("pause")

It's not portable and there are better ways to hold the console open.

---

Prefer nullptr to NULL

NULL is a macro that will be silently converted to 0 whenever possible. nullptr is a language extension and will only work contextually with pointers.

---

Use proper encapsulation

A linked list should be a class that acts as a container of Nodes. Your Node class should not know how to sort all Nodes. This is the job of the container. Furthermore Nodes are an implementation detail that should not be exposed to the user.

class LinkedList
{
public:
 // user functions should go here
private:
 struct Node
 {
 int value;
 Node* next{ nullptr };
 }
}

A few things to note.

• I put the public section first. This way anyone reading the code will know what functions and variables are available to them.
• I used struct for the Node since it represents plain data. It is also easier to use because struct is default public so the LinkedList will be able to access it easily (But since it is properly encapsulated inside the container nothing else can.)
• I initialized new nodes to nullptr.

---

Printing and Sorting aren't typically done as member functions. They should be standalone functions that accept a container, or a range of a container to perform their tasks.

---

Use RAII whenever possible

You shouldn't be manually allocating memory. Especially since you aren't freeing it. Every instance of new should come with an instance of delete but you shouldn't be using them at all.

---

Prefer '\n' to std::endl

std::endl does more than just move to the next line. It is generally preferred not to use it casually.

---

Keep working on it. Try to implement the container with some of the member functions found at std::list. Browse The Core Guidelines from time to time. And bring us more code to review.

Answer 2

Care about memory leaks and memory allocation

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. Here, the good place to put deletion is the destructor of your class.

Consider using smart pointer they are better, safer, stronger (© DP). If you used smart pointers instead of raw pointer, your allocated resources would have been automatically released by the default constructed destructor.

Check this reply from @TobySpeight for further information.

Finally, take care that memory allocation can fail.

---

Use nullptr

Use nullptr instead of NULL or 0. There's a lot of reasons (and follow inside's links) Also, don't be redundant in your conditions: As explained in the Core Guideline, comparing a pointer to nullptr (or even worst, to NULL or 0) in a condition, not only is useless, but it's also much more verbose.

---

Avoid using namespace std;

Putting using namespace std at the top of every program is a bad practice that can cause a lot of problems that are easy to avoid, most people are used to the prefix, and three letters aren't that hard to type.

• Although it's "safe" to use it in some place (e.g. implementation files), as long as you aren't familiar with the features of c ++, try to avoid it.

• It led to a world of name collisions. (best case)

• It's source of silent errors and weird bugs. (worst case)

• If typing std:: is so tedious for you, try to import only truncated namespaces. ( e.g. using namespace std::string;).

• If importing nested namespaces still too awful for you, try to do it inside a restricted scope (e.g. a functions) and not in global scope.

---

Don't use std::endl

Using std::endl send a '\n' and then flushes the output buffer. So std::endl is more expensive in performance. Instead, use '\n' and then, if you want to manually flush the stream, explicitly call std::flush.

---

Constructors/destructor

• Prefer member initialization list for value.
• Prefer [in-class initialization] for next.
• Provide a constructor with only one parameter and another with explicitly two parameters (without defaulted next).
• Respect rules of 3/5/0

---

Avoid system (... )

You should avoid using system('pause') and all it family.

• It's non-portable
• It's slow
• It's dangerous

---

Interface

• Don't put the Print method inside of the class. Instead split it into two function a to_string to transform your list to a string and a overload to operator << to output the string representation of your list (via to_string).
• Where did you Add value? At the beginning or at the end? We know because we see the code, but user of your class don't. The interface is unclear, should be push_front or push_back
• Look at the C++ Standard implementation of singly linked list (std::forward_list) and doubly linked list (std::list), and try to implement iterators related functions, useful for a lot of things.

---

Sorting

• Move sort method as free function
• Add an optional comparator parameter
• Rethink your sorting algorithm, it's not the optimal way. You can do it in less operations (think about "comparator" and iterator).
• Don't reinvent the wheel, use swap.

---

Misc

Also, don't use long commentary lines, it don't help improving readability

• Toby Speight: Most of this just duplicates the answer from 6 hours earlier. Can you be clearer about what's new in your answer (or - preferably - just omit items already covered by other reviewers)?
• Calak: @TobySpeight do you really think that my message brought no added value? *I started it early this morning from my phone, at work. So, I only seen the other response right before posting). IMHO, I go deeply on repeated subjects and I explain some other things that he doesn't tackle. If you think I'm wrong, feel free to delete my message or downvote it.
• Toby Speight: Not at all - I just said it was hard to separate the added value from the rest. It's inevitable that we sometimes write much the same thing as others when good reviews take an hour or two to write - I often find myself having to remove or re-write stuff just before (or just after) posting when I find others are making the same observations.
• Calak: Yes, You're right. TBH, I threw some lines about encapsulation since his explanation was a way more complete. I tried removing other repeated things but can't without break added value or the general logic of the post. (E.g. the sorting part was introduced by previous subsections). And I confess that from my phone, it's more tricky than easy.