# Implementing a linked list using C++

Any suggestions?

#include<iostream>

using namespace std;

class node
{
friend class linked;

private:
int data;

public:
node *link;
node()
{
data=0;
link=NULL;

}

};
class linked
{
public:
node *start=NULL;
node *ptr;
node *temp=NULL;

void append(int item);
void traverse();

};

void linked::append(int item)
{
ptr = new node();
ptr->data=item;
if(start==NULL)
{
start=ptr;
ptr->link=NULL;
temp=start;

}
else
{
while(temp->link!=NULL)
{
temp=temp->link;

}
temp->link=ptr;
ptr->link=NULL;

}

}
void linked::traverse()
{
node *trav=start;
while(trav!=NULL)
{
cout<<trav->data<<endl;
trav=trav->link;
}

}
int  main()
{
int i;

linked box;

for(i=0;i<10;i++)
{
box.append(i);

}

box.traverse();
}


## Starting at the top

//any suggestions


Yes, plenty. But don't add that to the code.

## using namespace std;

Nearly every beginner includes this (and it's understandable because this is what they do in books).

In actual practice this is a bad idea. Never include this line in real code. The reason books include it is to save space (because each printed page costs extra). When writing real code, this will create bad habits that will bite you in the end so it is a habit you should break now.

## node class

### protection level

There is no need to make the node class public. This is internal to your linked list so you should hide its implementation from other people by making it a private member class of the linked class.

### style

class Node
{
friend class linked;

private:
int data;

public:
Node *link;
Node()
{
data=0;
link=NULL;

}

};


Small note on vertical spacing: there is way too much here. It's a small class so it does not stand out. But if you do the same thing on a bigger class it becomes hard to read. Now don't take this to the extreme and completely eliminate vertical space-- break things up into logical units.

Since we are making this class a private member of linked there's no need for friendship; just make everything public.

But we can improve the code by having a constructor that takes the data value and the link (if you look at your code you could use both at the same time. When writing constructors, it's preferred to use the initializer list syntax to initialize members:

                Node(int data, Node* link)
: data(data)
, link(link)
{}


You will notice here that everything is lower case. It is relatively common to define user-defined types with an initial capital letter, while objects have an initial lower case letter. This allows you to quickly see the difference between types and objects (an important distinction in C++).

So, following this style, your code should look like this:

class Linked
{
struct Node
{
int    data;
Node*  next;
Node(int data, Node* next)
: data(data)
, next(next)
{}
};

....


## linked class

class linked
{
public:
Node *start=NULL;
Node *ptr;
Node *temp=NULL;

void append(int item);
void traverse();

};


Not sure what all the pointers are for? OK start marks the start of the list (usually called head). But what are the others supposed to represent? If they are really just things you use a throw away then they can be local to the function methods and not part of the class.

You call new in your code. For every call to new there must be a corresponding call to delete. Otherwise you will leak memory (and resources). So the best place to do this is in the destructor.

Also you are missing a constructor. This means that all you member variables are likely to be undefined (this means they have random values in them. C++ (unlike Java and other languages at this level) does not do automatic initialization of variables.

So lets add the constructor and destructor

class Linked
{
struct Node
{
int    data;
Node*  next;
Node(int data, Node* next)
: data(data)
, next(next)
{}
};

Node*   head;

Linked():
head(nullptr)
{}
~Linked()
{
Node* tmp;
for(;head;head = tmp)
{
tmp = head->next;
delete head;
}
}
...


If we look at append. You get the correct test for adding an element to an empty list. But it starts to go wrong in the second half where you are using a loop.

The member temp is not initialized. It is also public -- this means it could have been altered since last time you used it. So it is best to use a local variable that you initialize to head.

Note: you can also use the new constructor for node to reduce code in this function.

void Linked::append(int item)
{
if (head == nullptr)
{
head = new Node(item, nullptr);
}
else
{
// First find a pointer to the last item in the chain.
Node* last = head;
while(last->next)
{
last = last->next;
}
// Now just add the node.
last->next = new Node(item, nullptr);

// Notice this loop happens each time you add an element.
// This makes adding an element relatively expensive.
// To avoid this a lot of implementation keep two pointers
// in the list a head and a tail. That way data elements
// can be quickly added to the tail.

// When you start adding things like delete.
// It becomes useful to know your previous element.
// So it is also very common for the node object to have
// two pointers next and prev
}


Note: we always seem to place nullptr as the second argument. So we could potentially remove it. But if you try to implement an insert function then it becomes useful:

void Linked::insert_at_head(int value)
{
head = new Node(item, head); // See very useful.
}


Not sure what your traverse is doing.

void linked::traverse()
{
Node *trav=start;
while(trav!=NULL)
{
cout<<trav->data<<endl;
trav=trav->link;
}

}


I would just name that print; traverse implies going through a tree.

One way to improve the functionality and modularity of traverse would be for it to take a parameter of a function that should be applied to all the nodes (but I think that is a bit beyond this exercise). So a couple of things here:

1. Rename to print
2. Mark the function as const
It does not alter the state of the object. So it is safe to call on a const version of the object.
3. Printing in C++ is usally done by operator<<
so create one of these that calls your print method.

Like this:

void Linked::print(std::ostream& str = std::cout) const // Note const
{
Node *trav=start;
while(trav!=NULL)
{
// Added space here so yo can see the <<
// and what they are applied too.
//
// Also prefer "\n" to std::endl (especially in here)
// The std::endl forces a buffer flush. Doing this
// after printing every integer becomes very inefficient.
str << trav->data << "\n";
trav=trav->next;
}
}
std::ostream& operator<<(std::ostream& str, Linked const& data)
{
data.print(str);
return str;
}


I think we have now covered enough in one review. I would have another bash at this example. Once you have done that post the code for review again and we can go into some other details.

• Singly linked lists are not supposed to have double pointers, and quite often, they don't have tail pointers either. – xyz Oct 18 '15 at 9:34
• Btw, not only this is a great code review, it's a good tutorial on linked list. You should put this into a blog. – xyz Oct 18 '15 at 9:35
• Actually, slashing all constructors of node is superior: Use aggregate-initialization. – Deduplicator Oct 18 '15 at 16:46
• @Deduplicator: What. Can you paste a link? – Martin York Oct 18 '15 at 21:04
• If the struct node just contains data and next, nothing else, you can use aggregate-initialization, like new node{} for a zeroed node, new node{42} for a node with 42 as data and a null next-link, new node{42, pointer} if you want to initialize both. I used it in my answer (somewhere far below). – Deduplicator Oct 18 '15 at 21:21

## Structure Requirements

Just in a general form, nearly all data structures require these three methods:

1. Insert
2. Search/Find
3. Delete

So far, you have insertion somewhat, but you are missing some key points:

• You are currently only appending to the tail of the structure. What happens when you want to append at the head of the structure? Or even in between two nodes? You need to define the cases that would allow such an insertion to take place.

There is a real lack of functionality to delete data that is no longer needed. When considering deletion in linked list, it's important to note the following cases that can take place.

• Deleting the head (first) node
• Deleting a node between two nodes
• Deleting the tail (last) node

Each one of these cases requires different logic.

For Search/Find, you have the hard part down; traversing the list and checking for null values. But you need to look for specific data at some point. Search is pretty simple and it only requires a couple additional lines to your void linked::traverse() method.

## Naming Your Methods

Most of the time you are fine, but it's important to remember that you need to give names that represent what the methods/class/variable does. My main example in this instance is your void linked::traverse() method.

While the method does traverse the list, it is actually doing more than just going through the list and looking for null values; this method is actively displaying the data. Therefore, I would change this method definition to the following for clarity: void linked::printAll() or something along those lines.

I would then make a separate method that is specifically responsible for traversing the list, nothing else. By keeping the responsibilities of each method separate, you'll cut down on debugging time greatly as you extrapolate the structure.

## Closing Pointers and Cleanup

This is a big one! I currently see no attempt to delete pointers, there are also no destructors. Any time you are using an Object-Oriented approach, especially in something such as a data structure, it is imperative that you make sure there are no memory leaks. What happens when this structure gets really big and you have no way to cleanup?

This is the kind of thing that will ruin your data structure as you do some serious testing on it.

## Object-Oriented Design

When you are implementing your linked class, you should consider which of the following you will need.

• Default constructor (if you wish to instantiate an object with default values)
• Value-accepting constructor (nearly always)
• Destructor (If using new keyword in your code, you need to delete whatever it is you instantiated at the end of use/program)
• OPTIONAL A copy constructor (if using a destructor, this must be present)

EDIT:
As mentioned by Corbin in the comments, you should consider the rule of 3/5/0 when designing a class. Rule of Three C++
The Rule of Three states that if you are implementing one or more of the following methods, you should explicitly define all three.

1. Copy Constructor MyObj obj1(obj2);
2. Copy Assignment operator obj1 = obj2; or... MyObj obj1 = obj2;
3. Destructor ~linked() { //Cleanup }
The Rule of 5, and Rule of 0 expand on this and more can be found in the link provided above.
• Your "Anytime you design a calss, you need to create a ..." advice applies in this situation, but it's wrong when presented as general rules. Destructors are only required if you're managing some resource (which in modern C++ you very rarely should be) or if you are opening your class to be extended. As for a copy constructor: if you have a destructor you must have a copy constructor (even if it's just a private or deleted one). It might be worth throwing something about the rules of 3, 5 and 0 in there. – Corbin Mar 29 '15 at 17:42
• Also, your setter/getter seem to have gone Java for a second? And getData should be const. And the idiomatic way to do this for a container in C++ would be to return a reference in the non-const version and a const reference in the const version (although blah.data() = 5; does look pretty weird, so maybe I'm just trying to over apply iterator patterns). – Corbin Mar 29 '15 at 17:44
• Getters/Setters break encapsulation. You are exposing the internal types of your class to the outside world. Methods should be actions that apply to your object. Getters/Setters are popular in languages like Java/C# because they can be used by tooling infrastructures like serializers. Of course there are always exceptions to the rule (that make it a rule). Containers expose there content but in C++ we usually do it via other techniques. Like iterators operator[] etc. – Martin York Mar 29 '15 at 17:46
• @Corbin Yeah, I swicthed to java w/o thinking about it :P I'll update it to be C++ once I'm back @ a PC. I'll update my answer with the suggestions you posted also, thanks for those btw. – Evan Bechtol Mar 29 '15 at 17:54
• @LokiAstari Thanks for pointing this out, I primarily use Java and over-looked this fact in C++. I'll update shortly! – Evan Bechtol Mar 29 '15 at 17:55

## Naming things

The names you give your classes and variables could be improved. Consider telling a colleague that you "have a linked" in your code (will they understand that?)

I would simply call it "list", "linked_list", or "forward_list" (but not "linked").

Same goes for:

node *link;


If it is a link, you are better off naming it based on what it points to, not what it is (i.e. call it "next", "next_node", etc).

Also, your traverse function should be called print, dump, display, show or something similar.

## Encapsulation

Your data is erratically set as public or private; This seems (to me) to follow no rules. Instead of creating a node as a public class (although you will not use it outside of the linked class) and making linked a friend, consider making it a private structure of the linked class: the friend declaration dissapears, everything will be public to list, and private to the outside world.

Similarly, the data in the linked class should be private.

## List Operations

Your public interface for the list is inadequate for any purpose except printing the elements to the output stream.

Common scenarios for a list are:

• insertion in various positions;
• iterating the elements;
• FIFO processing (you will need iteration support);
• checking for emptyness;
• reading the list size;
• modifying values;
• removing elements;
• removing all elements (that is, clearing the list);

For size and emptyness checks, you should consider caching the list size.

For iteration you should implement either iterators, or the visitor pattern, or both.

## Code Style

• consider using nullptr instead of NULL
• optimize code for ease of writing client code instead of ease of writing implementation:

ptr = new node();
ptr->data=item;


This should be a single line, looking like this:

ptr = new node{ item };


Well, something a bit different:

1. As Loki Astari already said, don't use using namespace std;. That actually holds for any namespace, unless you know exactly what symbols that might import, now and in the future, and are absolutely sure that's what you want/need.

2. A better name for a single-linked-list would be slist.

3. As no node is ever exposed by the slist, and the slist needs full access, node should be a struct with everything public.

4. As all the behavior is in the slist, node doesn't need any member-variables. And as aggregate-initialization is perfectly adequate, it also shouldn't have any explicitly declared constructors.

5. Because node is an implementation-detail of slist without any behavior which could be fruitfully shared, it should not be exposed to any other code.
Make it a private member.

The private member-struct of slist:

struct node {
int data;
struct node* link;
};

6. slist also has some useless members, namely ptr and temp. What are they for? Slash them.

7. It's missing a destructor that cleans everything up:

~slist() {
for(node* head = start, *next; head; head = next) {
next = head->link;
delete head;
}
}

8. Its implicit default-ctor is fine, because it picks up the member-initializer for start. Still, when we fix the other constructors, it needs to be explicitly declared or it will be suppressed:

slist() = default;

9. The other constructors are just bad and need to be explicitly replaced:

slist(linked&& x) : start(x.start) { x.start = 0; }
slist(const linked& x) {
for(node** target = &start, source = x.start; source; source = source->link) {
*target = new node {source.data};
target = &target[0]->link;
}
}

10. Throwing in how to enable use of initializer-lists here:

slist(std::initializer_list<int> l) {
node** target = &start;
for(auto x : l) {
*target = new node {x};
target = &target[0]->link;
}
}

11. Now we just need a method to swap two slists:

void swap(slist& x) { std::swap(start, x.start); }

12. And assignment is easily done thanks to the copy-and-swap-idiom:

slist& operator=(slist x) { swap(x); return *this; }

13. append(int item) currently pushes some of its temporaries into the class? Well, cannot have that. Aside from that, the function is far more complex than needed.

void append(int item) {
node** target = &start;
while(*target)
target = &target[0]->link;
*target = new node{item};
}

14. traverse should accept the output-stream as an argument, though it can default to std::cout. Also, it should not needlessly repeatedly flush the stream. And that's a good place for a for-loop:

void traverse(std::ostream& o = std::cout) {
for(node* p = start; p; p = p->link)
o << p->data << '\n';
}

• Why do you need pointer on pointer and what is &target[0]->link? – green diod Jul 16 '16 at 20:38
• I'm using node** to avoid unnesseccary special-cases. And &target[0]->link is the address of the member link of the structure the pointer target points to points to. – Deduplicator Jul 16 '16 at 21:34
• Could you please elaborate on the special cases you try to avoid? I had difficulty parsing your expression. My first attempt was *(&(*target)).link. Is it equivalent to &((*(*target)).link) (if I correctly understand the operators precedence page)? – green diod Jul 16 '16 at 22:03
• @greendiod The last one it is. And the special case would be assigning the head-pointer in contrast to some link-pointer. – Deduplicator Jul 17 '16 at 7:12