# C++ Doubly Linked List Implementation

Does anyone have suggestions on how to improve this?

Specifically:

• Am I passing and returning references correctly to prevent unnecessary copying?
• Am I using destructors and the delete keyword correctly to prevent memory leaks?
• Am I throwing exceptions correctly?

Also, just wondering whether it would be possible, when inserting an element, to just declare a node as

list_node_generic node;


list_node_generic* node = new list_node_generic();


Is this doable? If it is, is it encouraged or discouraged and why?

#ifndef list_generic_hpp
#define list_generic_hpp

#include <iostream>

namespace ds{

template <typename T>
class list_generic{

private:

class list_node_generic{

private:
list_node_generic* prev;
list_node_generic* next;
T data;

public:
list_node_generic(){
prev = nullptr;
next = nullptr;
}

~list_node_generic(){
delete next;
delete prev;
}

//Get Functions.
list_node_generic* get_prev(){
return prev;
}

list_node_generic* get_next(){
return next;
}

T& get_data(){
return data;
}

//Set Functions.
void set_prev(list_node_generic* p){
prev = p;
}

void set_next(list_node_generic* n){
next = n;
}

void set_data(T& d){
data = d;
}

};

list_node_generic* first;
list_node_generic* last;
int length;

public:
list_generic(){
list_node_generic* dummy = new list_node_generic();
first = dummy;
last = dummy;
length = 0;
}

list_generic(list_generic& other){
list_node_generic* dummy = new list_node_generic();
first = dummy;
last = dummy;
length = 0;
list_node_generic* current = other.first->get_next();
for (int i = 0; i < other.length; ++i){
append(current->get_data());
current = current->get_next();
}
}

list_generic operator=(list_generic& other){
list_generic replacement = (*new list_generic(other));

return replacement;

}

int size(){
return length;
}

bool empty(){
if (length == 0){
return true;
}
else{
return false;
}
}

void print(){
list_node_generic* current = first;
cout << "{";
for (int i = 0; i < length - 1; ++i){
current = current->get_next();
cout << current->get_data() << ", ";
}
current = current->get_next();

cout << current->get_data() << "}";
}

void insert(int index, T element){
if (index > length){
throw "Error: Index goes out of bounds.";
}

list_node_generic* node = new list_node_generic();
node->set_data(element);

if(index == length){
last->set_next(node);
node->set_prev(last);
last = node;
++length;
return;
}

list_node_generic* current = first->get_next();

for (int i = 0; i < index; ++i){
current = current->get_next();
}

node->set_prev(current->get_prev());
node->set_next(current);
current->get_prev()->set_next(node);
current->set_prev(node);
++length;
return;
}

void prepend(T element){
insert(0, element);
}

void append(T element){
insert(length, element);
}

T& get(int index){
if (empty()){
throw "Error: List is Empty... returning -1";
}

int real_index = index % length;
list_node_generic* current = first->get_next();
for (int i = 0; i < real_index; ++i){
current = current->get_next();
}

return current->get_data();
}

T& front(){

if (empty()){
throw "Error: List is empty...";
}

return first->get_next()->get_data();

}

T& back(){
if (empty()){
throw "Error: List is Empty... returning -1";
}

return last->get_data();
}

int search(T element){
if (empty()){
return -1;
}

list_node_generic* current = first;
for (int i = 0; i < length; ++i){
if (current->get_data() == element){
return i;
}
current = current->get_next();
}

std::cout << endl << element << " is not in the list" << endl;
return -1;

}

void remove(int index){
if (index >= length || index < 0){
return;
}

list_node_generic* current = first->get_next();

if (index == length - 1){
last = last->get_prev();
current = last->get_next();
current->get_prev()->set_next(nullptr);
length--;
return;
}

for (int i = 0; i < index; ++i){
current = current->get_next();
}

current->get_prev()->set_next(current->get_next());
current->get_next()->set_prev(current->get_prev());

length--;

return;

}

void pop_front(){
if(empty()){
return;
}

remove(0);
}

void pop_back(){
if (empty()){
return;
}

remove(length - 1);
}

~list_generic(){

}

};

}

#endif


Not a bad first crack at a linked list. Here's some things that are obvious issues to me:

1. Your getters and setters for list_node_generic aren't really encapsulating much. They allow unchecked access to private fields. Essentially rendering those fields public, but with much verbosity. Since you don't intend to let any code other than the enclosing list_generic touch those, I suggest you just have node objects with all public fields.

2. The suffx _generic is to me redundant. You are creating a template, any C++ savvy programmer will understand it's meant for generating concrete classes when given type parameters. The suffix is just noise. Also, list_node ought to be just node. There's no need for prefixes, because the complete type name for it is ds::list_generic::node. There is no ambiguity to guard against. And by the way, good use of a namespace. Although perhaps something a bit longer and more descriptive for a namespace identifier would be better.

3. The list_generic copy c'tor and assignment operator. You try to reuse the copy c'tor in the assignment operator. That's awesome awareness to code reuse. However, you have several serious bugs there:

list_generic replacement = (*new list_generic(other));


This allocates a copy of the other list dynamically. Then it immediately dereferences that pointer and creates another local copy. The dynamic memory allocation leaks (since you don't call delete).

Then you return the newly copied list. But you didn't modify *this. Nothing was assigned!

An improvement, and better reuse of the copy c'tor, is the copy-and-swap idiom. First, you add a simple swap member function that can swap the innards of two lists. Something like this:

void list_generic::swap(list_generic& other) {
using std::swap;
swap(first, other.first);
swap(last, other.last);
swap(length, other.length);
}


It makes use of std::swap. It's usually a good idea to make use of the standard library. It's full of stuff that saves you work. Now, back to business, the assignment operator:

list_generic& operator=(list_generic other) {
other.swap(*this);
return *this;
}


Note two things: firstly, we accept the other list by value. This means that the list we are assigning from will either be copied or moved (if you add move semantics to your class), depending on where it came from. Either way, we get a ready made list that we swap with the this object. Secondly, we return a reference to the current object (not a superfluous copy). This is a canonical implementation that allows for assignment chaining.

4. empty is a very simple method written in quite a verbose manner. It could be simplified to return size() == 0;

5. Instead of throwing string literals, throw an exception object. You don't have to roll out your own, it can be one of the standard ones. I.e:

throw std::out_of_range("Error: List is Empty");


This gives the catching code a concrete type to catch against. And the type name indicates the problem. To contrast catch (char const*) doesn't tell what's wrong. If the calling code wants to handle the error, it would have to parse strings. That's really sub-optimal.

6. ~list_generic is an empty destructor! How are all the nodes you allocated going to be freed? There needs to be a loop here that deletes all the nodes from first to last.

A followup, given the comments bellow:

# noexcept

This tells the compiler there won't be any exceptions thrown by the designated function. Adding the noexcept specifier to functions allows for further optimization opportunities if your compiler is so inclined. Since swap is always assumed a non-throwing operation, let's mark it as such:

void list_generic::swap(list_generic& other) noexcept { // In the declaration as well
// Same as before
}


# Moving objects

I touched upon this originally. The suggested assignment operator is a catch-all implementation that should work for both the copy-c'tor and the move-c'tor. So let's add move semantics to your class. It's rather simple really, the c'tor can steal another objects inner state if it knows the other object is about to expire. The compiler can tell you that, by binding to an r-value reference:

list_generic(list_generic&& other) : list_generic() {
// We delegate to the default c'tor to make this object have
// "empty" state. And now we swap with the other object:
other.swap(*this);
}


# Empty objects

Like I noted above, we delegated to the default c'tor in order to create an "empty" object to swap with. However, your default c'tor allocates storage off the bat. Try to reformulate your solution to avoid that. It will allow you to mark it as noexcept as well, and then of course the move-c'tor could be noexcept on account of calling only non-throwing operations.

• Great first answer on the site! Welcome! – user1118321 Aug 10 '17 at 5:48
• Actually OP has the deletion in the destructor of Node. Though the bad thing is that it deletes next and previous nodes, which surprisingly didn't get into infinite recursion, even with element count > 1. Wandbox. – Incomputable Aug 10 '17 at 7:36
• @Incomputable - The OP didn't delete anything in the destructor of the. And personally I wouldn't recommend recursive destructor calls. – StoryTeller Aug 10 '17 at 7:37
• @StoryTeller, yeah, I forgot that he holds them as pointers. I believe stack overflow on linked lists is rare? Maybe depends on the complexity of the T's destructor. I mean people don't put many elements into linked list. – Incomputable Aug 10 '17 at 7:38
• @DanielJour - Normally yes. I actually started by writing the naive swapping by hand, before it hit me to use a named operation. – StoryTeller Aug 10 '17 at 15:15

## Bug is waiting for you

Your code will get segmentation fault when you'll try to fix the destructor of the liste, e.g. add delete first in the destructor.

Here is the main of it:

int main()
{
ds::list_generic<int> list;
list.append(0);
list.append(1);
list.append(2);
list.print();
}


## Reason

Lets reproduce the list in the code I provided above.

nullptr <- 0 -> <- 1 -> <- 2 -> nullptr

1. Destructor of node containing 0 will run.

2. Then it will call destructor of node containing 1.

3. The destructor of node containing 1 will call destructor of node containing 0.

4. Go to 2.

As you can see, there is no end to this recursion. Note that the issue won't go away by changing order of things as they are now, it is a fundamental problem.

## Solution

The way to fix this is to do what @StoryTeller said:

1. current_node <- first

2. while current_node is not nullptr

2.1. next_node <- current_node.next

2.2. delete current_node

2.3. current_node = next_node

## Compilation errors

Some of cout and endl don't have std:: with them. After prepending them code compiled smoothly.

### Naming:

1. Macros and preprocessor-constants are generally ALL_UPPERCASE_WITH_UNDERSCORES, so they stand out as they don't respect scopes. Two underscores, or starting with underscore followed by uppercase is reserved for the implementation, and you avoided that error.

2. Kudos for putting your library-code in its own namespace, but its name should be distinctive enough to make clashes unlikely. ds is just too short. The user can easily define a namespace-alias for his own convenience later.

3. generic as part of a name is very unusual. All templates are generic, so putting it in the name does not help. And generally if there's a generic solution and other solutions aren't a specialization of the respective template or provided as overloads, the generic one gets the base-name and the others get a more elaborate name.

4. If you name something, don't repeat its context as that's a given. Brevity is a virtue as long as you don't go way overboard.

5. Keep to the conventions of your framework whenever feasible. Integrating your code will be vastly easier, both by programmers directly using it but also by templates not needing to special-case your code. Specifically, look at the interface of std::list.

print() -> non-member stream-insertion-operator. Needs better public interface
prepend() -> push_front()
append() -> push_back()
get() -> indexing-operator (T& operator[](std::size_t))
search() -> find()
remove() -> erase()

### Encapsulation:

1. node's observers and modifiers expose all its internals, they don't actually abstract away anything.

2. Anyway, as node is an implementation-detail of list, and is per-se tightly-coupled to it, they are a unit and trying to communicate at arms-length is a wasteful exercise in futility. Only add members (ctors, dtor, ...) to node if doing so simplifies implementing list+node, and dispense with access-control.

3. list's interface is insufficient. Because access is by index instead of using iterators, it's $O(n)$ for anything but beginning and end.

### Error-handling:

1. Some of your functions silently swallow errors (remove(), pop_front(), pop_back()). Better to throw an exception.

2. Other functions throw a cstring-pointer. That's very unusual, as the type doesn't even hint at the real problem, and wrapping it in the appropriate standard exception-class doesn't cost much. You want std::out_of_range.

3. search() is the only function returning an error-code, which is appropriate as failing to find an element is somewhat expected.

4. Yet others just let exceptions bubble up. That's often appropriate, but be aware of where that might happen.

5. Never report an error from generic library code directly to the end-user, unless everything is lost. Instead, let your user (the programmer) handle it as he wants by using exceptions. Who knows whether there's even anyone able to see the terminal?

6. If a function cannot fail, mark it noexcept. Doing so enables considerable optimizations, be it by the compiler directly or by allowing templates to take advantage of it.

### Memory leaks:

1. Your assignment-operator fails to modify *this and return it. Instead it leaks a copy of the argument and returns a copy of the argument.

2. insert() currently first default-initializes the data-member, and then copy-assigns the real value. Aside from efficiency considerations and impaired generality, if the assignment fails you leak the new node.

3. remove() leaks the removed node. You need to delete it.

4. Your dtor does nothing, though it should delete all node's in a loop. Remove the node's dtor, as it is defective and will result in infinite recursion as every node tries to delete its two neighbours.

### Const-correctness and general argument passing:

1. If you don't change an argument (including implicit *this for member-functions), accept it by constant reference or if efficiently copied by value.

2. Generally invest in move-semantics to avoid copying.

3. Allow constructing a node's value in-place. That can be vastly more efficient, or even the only possible way to do it.

### Avoid allocation:

1. Modify your code so default-initialization does not allocate memory. That's far more efficient and allows initialization at compile-time. Also take a look at constexpr while you are at it.

### Other things:

1. Don't use std::endl unless you really need to explicitly flush the stream. Flushing destroys your code's performance.

2. Don't use using namespace std;. Especially not in a header, as it infects all include-sites. Read "Why is “using namespace std” considered bad practice?" for why.

3. A header should be self-contained. #include what you need, no more and no less, bring select symbols into scope if you must, but don't depend on anyone else already having done it.

4. You can and should return a boolean expression directly. No need to obfuscate it by wrapping it with an if-else-construct.

5. Using std::cout as a default-destination is ok, but the user should really be able to select where the output goes.

list_node_generic node;


when creating a new node.

Thing is, think about where objects live. It is possible, but you should not do it. If you did, the variable would live within the scope in which it is declared - which can be fundamentally different in life length as the list.

Think about ownership. Who should own this variable, control when it lives and so on? Answer is the list. Therefore, you should make the list do that.

That said, the other one is not that good either:

list_node_generic* node = new list_node_generic();


You seem to consider those pointers as something that can be freely passed around. You have setters and getters for the next and prev members and you make the user create the node itself. That means that someone from the outside can manipulate your structure.

I ask you this: can you guarantee that an instance of your list class is consistent? Which means that there is a clear chain of nodes, with this.next.prev = this if not null and so on. Can you guarantee that nobody can use your class to create an object which does not have this probability? No, you can't. I could create the wildest structures with it.

The responsibility that an object is consistent lies with the class. No method should be able to break it. I recommend this architecture:

Have the list class doing all the basic insertion work. Have the user insert only the actual data of a node - not a node. If the data of a node can be big and could come from elsewhere, think about making the data a smart pointer and use move when creating a new node.

Have the list class also return a constant reference to the data whenever that is sufficient. Probably with the signature const T& or const T* or weak_ptr<const T>

Under no circumstances do something like set_next. This is the job of the list class.

So, as an answer: You can technically do what you said, but you shouldn't. You should only give the list object what it necessarily needs, which is the data. The list object then creates a node on it's own. If it should not copy the data, move semantics of smart pointers help.

Another solution would be to use smart pointers. Consider this:

shared_ptr<list_node_generic> next; //owns and thus kills the child
weak_ptr<list_node_generic> prev; //does not own - a raw pointer would also work here


This forms a clear hierarchy of ownership. Every node is owned by it's predecessor. The first node is owned by the list object. The destructor can be left empty.

Nodes handed to the outside are handed out as weak_ptr<const list_node_generic> (or non-const, but you should prefer const whenever possible). This makes sure that the case of the list dying before the pointer will indeed kill the object while the user is able to check whether this happened.

Another thing, your getter is also a setter:

                T& get_data(){
return data;
}


This is a non-const reference. I could do this:

T& data = node.get_data(); //probably with the correct type instead of T here
data = 12345; //assuming that an int value is fine for T


and this would change the data in the actual node. Which I assume you don't want to be, since you have a separate setter. Go with this instead:

                const T& get_data() const {
return data;
}


With this, T& data = node.get_data(); would result in error, so would const T& data = node.get_data(); data = 12345;.

If a member has a setter and a getter which have no further functionality, you might want to simply make the member public. Only reason not to do so would be to allow for child classes that work differently, but since your methods are not virtual, that was not intended.