Singly Linked list implementation in C++

Question

How can I improve this code
Please tell proper indentation and usage of camel-case.

#include <iostream>
using std::cout;
struct Node
{
 int data;
 Node* next;
};
Node* Create(int data){
 Node* root=new Node();
 root->data=data;
 root->next=NULL;
 Node* head=root;
 return head; 
}
void push_back(int data,Node* head){
 if(!head->next)
 {
 Node* newNode=new Node();
 newNode->data=data;
 newNode->next=NULL;
 head->next=newNode;
 } 
 else 
 push_back(data,head->next);
}
Node* push_front(int data,Node* head){
 Node* newNode=new Node();
 newNode->data=data;
 newNode->next=head;
 head=newNode;
 return head;
}
void pull_back(Node* head){
 Node* temp=head;
 if(!temp->next)
 delete temp;
 else
 pull_back(temp->next);
}
Node* pull_front(Node* head){
 Node* temp=head->next;
 delete head;
 Node* NewHead=temp;
 return NewHead;
}
void print(Node* head){
 while(head)
 cout<<head->data<<" ",
 head=head->next;
 cout<<"\n";
}
Node* Reverse(Node* head)
{
 Node* prev = NULL;
 Node* current = head;
 Node* next;
 while (current != NULL)
 {
 next = current->next; 
 current->next = prev; 
 prev = current;
 current = next;
 }
 head = prev;
 return head;
}
int Search(int data,Node* head,int count=1){
 if(head->data==data)
 return count;
 if(!head->next)
 return -1;
 return Search(data,head->next,count+1);
}
Node* MakeCircular(Node* head)
{
 Node* temp=head;
 while(!temp->next)
 temp=temp->next;
 temp->next=head;
 return head;
}
bool DetectCircle(Node* head){
 //using floyd's cycle
 Node* fast=head;
 Node* slow=head;
 if(!(slow && slow->next))return false;
 while(fast && fast->next){
 slow=slow->next;
 fast=fast->next->next;
 if(slow==fast)
 return true;
 }
 return false;
}
int main(int argc, char const *argv[])
{
 Node* head=Create(12);
 push_back(32,head);
 push_back(123,head);
 head=push_front(-21,head);
 print(head);
 head=Reverse(head);
 print(head);
 return 0;
}

• SirPython: To whoever flagged this for off-topic as "unclear what you are asking", read the title; it says the code's purpose right there.

Answer 1

Let's start with the small stuff, to get in the groove.

Naming convention

Whether you use camelCase or PascalCase or snake_case does not matter, as long as you do so consistently.

Pick a style for your class names, the same or another style for your functions, etc... and stick to it.

I will assume that you go for PascalCase for classes and snake_case for methods, but do as YOU wish.

Spaces

The C++ grammar allows you not to put spaces around operators, however this really hurts readability.

Use spaces:

• after commas: push_back(int data, Node* head)
• after keywords: if (...), while (...), ...
• around operators: a = b, a + b, ! a, ...

The goal is to make sure that your eye does not accidentally "merge" two symbols and treat them as one. For example, !a and la are very close graphically speaking, yet they mean completely different things.

Useless code

Avoid writing code that does not bring anything to the table:

Node* Create(int data){
 Node* root=new Node();
 root->data=data;
 root->next=NULL;
 Node* head=root;
 return head; 
}

There is no reason to create a head variable here. You can simply return root directly.

Inconsistencies

Why does pull_front return Node* but pull_back return void?

This is even more problematic in that the user need to remember than she needs to call delete on the result of pull_front but there is no result to pull_back...

Side Note: one would expect pop_front and pop_back, as far as names go.

---

Let's now move on to more interesting stuff.

Dynamic Memory Allocation

For production code, using new or delete is forbidden¹. You should be using std::unique_ptr, std::shared_ptr, or one of the many Standard Library containers.

Since you do not appear to be familiar with unique_ptr, I advise you to add them to your reading list and will use naked pointers for the rest of this answer.

¹ Unless you are an experienced developer, and no other language facility or library allows you to write this code, and your colleagues have extensively reviewed your code.

Initialize your values

Whenever you build a Node, you have to explicitly remember to initialize the next member to nullptr and the data member to 0, lest they have garbage values.

Instead, use automatic initialization and constructors:

struct Node {
 Node() {}
 Node(int d, Node* n): data(d), next(n) {}
 int data = 0;
 Node* next = nullptr;
};

Beware of recursion

While recursion is elegant, in languages like C++ it can lead to Stack Overflow.

As such, unbounded recursion should be avoided, and therefore your implementation of push_back or pull_back or Search should be converted to an iterative approach (use a while loop).

Encapsulation

It is generally recommended to encapsulate functionality. At the moment, anybody can fiddle with your Node internals (and point its next member to whatever they want without using your functions).

Once next becomes private however, only a specific set of functions will be able to access it:

• member functions (object-oriented approach)
• friend non-member functions

This ties in with the bigger question of whether you really want to expose the Node itself, where a null node represents an empty list and the user has to explicitly call delete on nodes you return. I would recommend to avoid exposing pointers and therefore to create a List class with an inner Node struct.

---

Let's see the code!

Note: I will not transpose all the code, only the first few methods.

class List {
public:
 List() {}
 bool is_empty() const { return this->head == nullptr; }
 void push_front(int value) {
 this->head = new Node(value, this->head);
 }
 void push_back(int value) {
 if (this->head == nullptr) {
 this->head = new Node(value, nullptr);
 return;
 }
 Node* current = this->head;
 while (current->next != nullptr) { current = current->next; }
 current->next = new Node(value, nullptr);
 }
 int pop_front() {
 assert(!this->empty(), "Cannot pop on empty list.");
 Node* popped = this->head;
 this->head = popped->next;
 int const value = popped->data;
 delete popped;
 return value;
 }
 int pop_back() {
 assert(!this->empty(), "Cannot pop on empty list.");
 Node* current = this->head;
 while (current->next != nullptr) { current = current->next; }
 int const value = current->next->data;
 delete current->next;
 current->next = nullptr;
 return value;
 }
 // ...
private:
 struct Node {
 Node() {}
 Node(int d, Node* n): data(d), next(n) {}
 int data = 0;
 Node* next = nullptr;
 };
 Node* head = nullptr;
};

• Juha Untinen: go for PascalCase for classes and snake_case Python style in C++? That's interesting... Is it common nowadays in C++?
• Matthieu M.: @JuhaUntinen: I have no idea what's common and what's not, to be honest. The standard uses snake_case exclusively, my company uses PascalCase for classes and functions and camelCase for methods, I have seen PascalCase only styles, ... I am mostly toying with Rust at the moment, so I went with the Rust convention :)

Answer 2

I see a number of things that may help you improve your code.

Prefer references to raw pointers

In modern C++, we tend not to use raw pointers very often. In this case, It would probably be better to have two different classes, one would be a LinkedList class and the other would be a Node class. That way, instead of starting with a pointer, you can start with an object.

Use objects

You have a Node structure and then separate functions that operate on Node data. With only a slight syntax change, you would have a real object instead of C-style code written in C++.

Use whitespace to improve readability

Lines like this:

head=push_front(-21,head);

become much easier to read with a little bit of whitespace:

head = push_front(-21, head);

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Use consistent naming

The code includes print() (lowercase) and Search() (uppercase). It would be better for both functions to have similar case. I tend to use capital letters to name clases or structs such a Node and then lowercase letters for functions such as print or search.

Match new with delete

If you allocate memory using new, you must also free it using delete or your program will leak memory. This program leaks memory.

Use more descriptive names

The code's DetectCircle function seems to return true if the list is circular. Generally, it's good to name boolean functions so that their sense is unambiguous. For example, I'd probably call it isCircular.

Omit return 0

If your program completes successfully, the return 0 at the end of main() will be generated automatically, so it's not needed in C++ programs.

• Matthew Read: Good points. I disagree with the last one though (removing return 0;) -- it's good to be aware of the implicit behavior dictated by the standard, but it's far from problematic to make it explicit and consistent.
• Daniel Jour: Considering the last point: Moreover, even if unlikely, you could compile on a target where 0 is not equal to EXIT_SUCCESS .. thus the implicit return 0 could mean a different thing.
• Edward: On omitting return 0: I don't claim it's "problematic", merely that it's not needed. Second, the standard explicitly states that an implicit return is the equivalent of return 0 or return EXIT_SUCCESS, so if anything, it's a point in favor of my suggestion.

Answer 3

This is a really straightforward implementation, and it's easy to follow. The code is very readable and I like that in your comments you mention which algorithm you're using to detect cycles. That way someone can look it up if they're not familiar with it. Below are some suggestions for improvements.

Object Oriented Programming

The first thing that strikes me about this code is that it's in C++ but it's not very object oriented. Usually a list is a class. That way all the data and methods for manipulating the data are contained in 1 place. If it were my code, I'd make a class like this:

class List {
 public:
 List();
 virtual ~List();
 void push_back(const int data);
 void push_front(const int data);
 int pull_back();
 int pull_front();
 // ... other methods
 private:
 Node* head;
};

Then to use it, you would construct a List object and call methods on it. The calling code wouldn't need to see the implementation at all, so you could change the underlying implementation and as long as the interface was the same, users would be none the wiser.

Don't Repeat Yourself

A good rule of thumb for any code that allocates memory is to only ever allocate that type of memory in a single place. In this case I see you've written essentially the same code as the Create() function in 2 additional places - push_back() and push_front(). Those 2 functions should just call Create():

void push_back(int data, Node* head) {
 if(!head->next)
 {
 Node* newNode=Create(data);
 head->next=newNode;
 } 
 else 
 push_back(data,head->next);
}

Also, in your Create() method, the last 2 lines are unnecessary. It should just be:

Node* Create(int data){
 Node* root=new Node();
 root->data=data;
 root->next=NULL;
 return root;
}

Don't Try to be Clever

Your print() method is confusing. The while statement doesn't have brackets around it, which makes it look like the following line has an error. It doesn't, but that use of a comma is tricky. It should instead look like this:

void print(Node* head){
 while(head)
 {
 cout<<head->data<<" ";
 head=head->next;
 }
 cout<<"\n";
}

That's much easier to read and understand.

Const

In most of your functions you're changing the Node, but not the data you pass in. If data doesn't change in a method, you should mark it const so the compiler knows it won't be changed and can display an error if you try to change it in the future. It may also be able to apply some optimizations to the code, too.

• Matthieu M.: Please, remove that virtual! List is not a polymorphic class, so it certainly does NOT need a virtual destructor.

Answer 4

Good points, in addition to that I have observed that whereas

using namespace std::cout;

is declared globally, cout is only used in two functions. It would be preferable to just use

std::cout << /* say something*/ << std::endl;

or std::cout << /* say something */ << "\n";