Iyfjky

Question

I implemented a Double linked list in c++ to practice. I reviewed the code myself and I would like others perspective about the improvements that could be made. I have also noticed that I don't take fully advantage of many c++ features nor use them in my code. Any comments about significant performance improvements are also appreciated!

Header File (List.h)

#pragma once

class List 
private:
 struct Node 
 int x;
 Node* next;
 Node* prev;
 ;

 Node * head;
 Node * tail;

public:
 List();
 List(const int x);

 void printList();
 void insert(const int x);

 unsigned short length();

 bool deleteList();
 bool isEmpty();
 bool isSorted();

 void reversePrint();
 void sortedInsert(const int x);

 List operator+(List const &obj1);
 void operator+(const int x);

;

Source File (Source.cpp)

#include <iostream>
#include "List.h"

using std::cout;

List::List() 
 head = nullptr;

List::List(const int x) 
 List();
 insert(x);


List List::operator+(List const &obj1) 
 List newList;
 Node* tmp = head;
 Node* tmp2 = obj1.head;

 while (tmp != nullptr) 
 newList.insert(tmp->x);
 tmp = tmp->next;
 
 while (tmp2 != nullptr) 
 newList.insert(tmp2->x);
 tmp2 = tmp2->next;
 

 return newList;

void List::operator+(const int x) 
 insert(x);



void List::printList() 

 if (head == nullptr) 
 return;
 

 Node* tmp = head;


 while (tmp != nullptr) 
 cout << tmp->x << " ";
 tmp = tmp->next;
 

 cout << 'n';

void List::insert(const int x) 
 // If list is empty
 if (head == nullptr) 
 head = new Node;

 head->x = x;
 head->next = nullptr;
 head->prev = nullptr;

 return;
 
 // Inserting at the end
 Node* copy = head;
 while (copy->next != nullptr) 
 copy = copy->next;
 

 // Inserting at the end
 Node* tmp2 = new Node;
 tmp2->x = x;
 tmp2->next = nullptr;

 copy->next = tmp2;
 tmp2->prev = copy;

 // Save the last node (tail)
 tail = tmp2;


unsigned short List::length() 
 short c = 0;
 Node* copy = head;
 while (copy != nullptr) 
 c++;
 copy = copy->next;
 

 return c;

void List::reversePrint() 
 Node* tmp = tail;

 while (tmp->prev != nullptr) 
 cout << tmp->x << ' ';
 tmp = tmp->prev;
 

 cout << tmp->x << 'n';

bool List::deleteList() 
 if (head == nullptr) 
 return false;

 Node* tmp = head;
 Node* tmp2 = head;
 head = nullptr;

 while (tmp != nullptr) 
 tmp = tmp->next;
 delete tmp2;
 tmp2 = tmp;

 


 return true;

bool List::isEmpty() 
 if (length() == 0) 
 return true;
 
 else 
 return false;
 

void List::sortedInsert(const int x) 
 if (isEmpty()) 
 insert(x);
 return;
 

 Node* copy = head;

 while (copy != nullptr) 
 if (copy->x > x) 
 //Insertar antes
 Node* tmp = new Node;
 tmp->x = x;

 head = tmp;

 tmp->next = copy;
 tmp->prev = nullptr;
 copy->prev = tmp;

 break;
 
 if (copy->next == nullptr) 
 insert(x);
 break;
 
 if ((x >= copy->x) && (x < copy->next->x)) 
 // insertar Despues
 Node* tmp = new Node;
 tmp->x = x;
 tmp->prev = copy;
 tmp->next = copy->next;

 copy->next->prev = tmp;
 copy->next = tmp; // -> next next
 break;
 

 copy = copy->next;
 


bool List::isSorted() 
 Node* tmp = head;
 while (tmp->next != nullptr) 
 if (tmp->x > tmp->next->x) 
 return false;
 
 tmp = tmp->next;
 

 return true;

Additional notes:
The sortedInsert(x) function would only work properly if it is used with a new list. It wouldn't work if first insert(x) is used and then sortedInsert(x)

cariehl 44619 · Accepted Answer · 2018-08-20 21:36:55Z

Here are a few suggestions, in order of importance

Delete nodes in the destructor

Right now, you are relying on users to call deleteList in order to delete the nodes in the List. Modern C++ uses the concept of RAII to remove the need for this. Write a destructor for your list that automatically deletes all nodes, so that users do not have to remember to call deleteList every time their list is about to go out of scope.

Finish adding double-linked list functionality

Right now, this is not a double-linked list, because you cannot perform operations on both ends of the list. In order to be a true double-linked list, you need to support adding and removing nodes from both the front and back of the list.

Break up responsibility

The sortedInsert(x) function would only work properly if it is used with a new list. It wouldn't work if first insert(x) is used and then sortedInsert(x)

This smells like one class trying to do two different things that it doesn't actually support. I can use your List as either a regular linked list, or a sorted linked list, but not both. If this is the case, you should split up these two responsibilities into two different classes, which can be made simpler through inheritance or composition.

I recommend you first remove the sortedInsert function from your List and focus on making that a true double-linked list. Then, you can create a new class called SortedList that either uses List as a base class...

class SortedList : public List

 ...

...or is a wrapper around a regular List which it keeps sorted.

class SortedList

private:
 List list;
public:
 void sortedInsert(int x);
 ...

The interfaces for List and SortedList are very different (you don't want to regular insert() into a SortedList). Therefore, I would personally go with the second option (composition) as it allows you to control the interface of your SortedList without exposing any of the underlying List interface.

Don't use `operator+`

Operator overloading is an easy trap to fall into that actually ends up making your code more confusing. Really think about it for a moment - what does it mean to add two Lists together? Do we append one to the other? Or do we add together all of their elements? In your case it is the former, but if you look at this code snippet...

List list1;
List list2 = list1 + 5;
List list3 = list1 + list2;

...it is hard for me to tell what is going on here. Especially in C++ where addition generally means "adding two numbers together", I would not expect list1 + 5 to insert 5 at the end of list1.

For containers, explicitly-named functions are usually more useful than operator overloads. I would prefer insert(int element); and append(const List& otherList); to an ambiguous operator+ that doesn't cleanly show what it is doing.

Make it templated

You can make your List more useful by making it a templated container. The interface will be very similar to what you have now, but instead of using int everywhere, you can define the class as

template <typename T>
class List ...

and use T everywhere you are currently using int.

Write more idiomatic C++

There are a couple of small idioms that you can use in your code to make it more readable for a C++ programmer. One that I noticed right away is comparing to nullptr. In C++, it is very common to write while (node) rather than while (node != nullptr), or if (!node) instead of if (node == nullptr). This is common practice, and will be recognizable by most C++ programmers.

Improve variable names

Most of your functions are short and easy-to-parse, which is good. They can be improved by using more descriptive names i.e currentNode instead of tmp. This is more of a problem in long functions, but having the context of a "real" name is always more useful than simply temp or c etc.

Fix minor formatting issues

Sometimes you have two empty lines between statements, but sometimes you have zero. You also have the same problem with functions. Additionally, you usually put the * for a pointer directly after the type i.e Node* except for two places where you use Node * with a space. These are minor issues, but if your code is formatted consistently, it becomes much easier to read quickly.

Jerry Coffin 27.5k360125 · Answer 2 · 2018-08-20 22:47:59Z

In addition to @cariehl's excellent comments, I'll add a few more:

Const Correctness

Member functions that only report the object's current state (without changing it) should be marked const:

void printList() const;

unsigned short length() const;

bool isEmpty() const;
bool isSorted() const;

void reversePrint() const;

This allows you to invoke the member function via a pointer or reference to const, so you can pass a list by const reference and still use those members that don't modify it. They also assure that if you accidentally write code that attempts to modify the list in a member function that shouldn't do so, the compiler will catch it and report it as an error.

Exception safety

Likewise, if a function is supposed to never throw an exception, it's better to mark it as noexcept to inform both the compiler and the user of that fact.

unsigned short length() const noexcept;

bool isEmpty() const noexcept;
bool isSorted() const noexcept;

This list isn't necessarily comprehensive--I just glanced through things, noted a few I was (pretty) sure should never throw, and listed them. There may easily be others that shouldn't throw either.

Use Boolean Values Directly

In your isEmpty() you have:

bool List::isEmpty() 
 if (length() == 0) 
 return true;
 
 else 
 return false;

You could simplify this quite a bit, to become something like:

bool isEmpty() const noexcept 
 return length() == 0;

Operator Usage

The C++ standard library generally attempts to use operator< rather than operator>, so generic containers place the minimum possible requirements on the types that can be stored in those containers. I'd advise following their lead on this when possible, so (for example) your isSorted would replace:

 if (tmp->x > tmp->next->x) 
 return false;

...with:

 if (tmp-next->x < temp->x) 
 return false;

Retain Information

Rather than computing the length when needed, I'd tend to just store the length of the list, and return it when needed--increment it when you add an item, decrement it when you remove one, and return it when needed.

From what I read, noexcept is most useful for move constructors, but otherwise has no effect in other code. Are you sure you want to recommend annotating methods with noexcept? — Aug 21 at 16:44

Toby Speight 18.6k13695 · Answer 3 · 2018-08-21 17:07:51Z

In addition to the fine answers by cariehl and Jerry Coffin, here's what I can offer:

Call the other constructor properly

List::List(const int x) 
 List();
 insert(x);

The code above creates a new object on the stack, calls the 0-argument constructor on it, and discards the object. Instead, what you want to do is call the 0-argument constructor on this object:

List::List(const int x) : List() 
 insert(x);

Size type

unsigned short length();

Why are you returning unsigned short? It is a rare type with not many good reasons to use it. If you're lazy, return int. If you want to be correct, return std::size_t (defined in cstddef).

On the same topic, in the implementation of length() you are using short as the counter variable, but returning unsigned short. This technically isn't wrong, but is a code smell.

unsigned short List::length() 
 short c = 0;
 (...)
 return c;

Aggregate initialization

You can simplify the code for creating and initializing new Node structs:

head = new Node;
head->x = x;
head->next = nullptr;
head->prev = nullptr;

The above can simplify to:

head = new Nodex, nullptr, nullptr;

This occurs in 4 places in your code.

cariehl 44619 · Accepted Answer · 2018-08-20 21:36:55Z

Here are a few suggestions, in order of importance

Delete nodes in the destructor

Right now, you are relying on users to call deleteList in order to delete the nodes in the List. Modern C++ uses the concept of RAII to remove the need for this. Write a destructor for your list that automatically deletes all nodes, so that users do not have to remember to call deleteList every time their list is about to go out of scope.

Finish adding double-linked list functionality

Right now, this is not a double-linked list, because you cannot perform operations on both ends of the list. In order to be a true double-linked list, you need to support adding and removing nodes from both the front and back of the list.

Break up responsibility

The sortedInsert(x) function would only work properly if it is used with a new list. It wouldn't work if first insert(x) is used and then sortedInsert(x)

This smells like one class trying to do two different things that it doesn't actually support. I can use your List as either a regular linked list, or a sorted linked list, but not both. If this is the case, you should split up these two responsibilities into two different classes, which can be made simpler through inheritance or composition.

I recommend you first remove the sortedInsert function from your List and focus on making that a true double-linked list. Then, you can create a new class called SortedList that either uses List as a base class...

class SortedList : public List

 ...

...or is a wrapper around a regular List which it keeps sorted.

class SortedList

private:
 List list;
public:
 void sortedInsert(int x);
 ...

The interfaces for List and SortedList are very different (you don't want to regular insert() into a SortedList). Therefore, I would personally go with the second option (composition) as it allows you to control the interface of your SortedList without exposing any of the underlying List interface.

Don't use `operator+`

Operator overloading is an easy trap to fall into that actually ends up making your code more confusing. Really think about it for a moment - what does it mean to add two Lists together? Do we append one to the other? Or do we add together all of their elements? In your case it is the former, but if you look at this code snippet...

List list1;
List list2 = list1 + 5;
List list3 = list1 + list2;

...it is hard for me to tell what is going on here. Especially in C++ where addition generally means "adding two numbers together", I would not expect list1 + 5 to insert 5 at the end of list1.

For containers, explicitly-named functions are usually more useful than operator overloads. I would prefer insert(int element); and append(const List& otherList); to an ambiguous operator+ that doesn't cleanly show what it is doing.

Make it templated

You can make your List more useful by making it a templated container. The interface will be very similar to what you have now, but instead of using int everywhere, you can define the class as

template <typename T>
class List ...

and use T everywhere you are currently using int.

Write more idiomatic C++

There are a couple of small idioms that you can use in your code to make it more readable for a C++ programmer. One that I noticed right away is comparing to nullptr. In C++, it is very common to write while (node) rather than while (node != nullptr), or if (!node) instead of if (node == nullptr). This is common practice, and will be recognizable by most C++ programmers.

Improve variable names

Most of your functions are short and easy-to-parse, which is good. They can be improved by using more descriptive names i.e currentNode instead of tmp. This is more of a problem in long functions, but having the context of a "real" name is always more useful than simply temp or c etc.

Fix minor formatting issues

Sometimes you have two empty lines between statements, but sometimes you have zero. You also have the same problem with functions. Additionally, you usually put the * for a pointer directly after the type i.e Node* except for two places where you use Node * with a space. These are minor issues, but if your code is formatted consistently, it becomes much easier to read quickly.

Jerry Coffin 27.5k360125 · Answer 5 · 2018-08-20 22:47:59Z

In addition to @cariehl's excellent comments, I'll add a few more:

Const Correctness

Member functions that only report the object's current state (without changing it) should be marked const:

void printList() const;

unsigned short length() const;

bool isEmpty() const;
bool isSorted() const;

void reversePrint() const;

This allows you to invoke the member function via a pointer or reference to const, so you can pass a list by const reference and still use those members that don't modify it. They also assure that if you accidentally write code that attempts to modify the list in a member function that shouldn't do so, the compiler will catch it and report it as an error.

Exception safety

Likewise, if a function is supposed to never throw an exception, it's better to mark it as noexcept to inform both the compiler and the user of that fact.

unsigned short length() const noexcept;

bool isEmpty() const noexcept;
bool isSorted() const noexcept;

This list isn't necessarily comprehensive--I just glanced through things, noted a few I was (pretty) sure should never throw, and listed them. There may easily be others that shouldn't throw either.

Use Boolean Values Directly

In your isEmpty() you have:

bool List::isEmpty() 
 if (length() == 0) 
 return true;
 
 else 
 return false;

You could simplify this quite a bit, to become something like:

bool isEmpty() const noexcept 
 return length() == 0;

Operator Usage

The C++ standard library generally attempts to use operator< rather than operator>, so generic containers place the minimum possible requirements on the types that can be stored in those containers. I'd advise following their lead on this when possible, so (for example) your isSorted would replace:

 if (tmp->x > tmp->next->x) 
 return false;

...with:

 if (tmp-next->x < temp->x) 
 return false;

Retain Information

Rather than computing the length when needed, I'd tend to just store the length of the list, and return it when needed--increment it when you add an item, decrement it when you remove one, and return it when needed.

From what I read, noexcept is most useful for move constructors, but otherwise has no effect in other code. Are you sure you want to recommend annotating methods with noexcept? — Aug 21 at 16:44

Toby Speight 18.6k13695 · Answer 6 · 2018-08-21 17:07:51Z

In addition to the fine answers by cariehl and Jerry Coffin, here's what I can offer:

Call the other constructor properly

List::List(const int x) 
 List();
 insert(x);

The code above creates a new object on the stack, calls the 0-argument constructor on it, and discards the object. Instead, what you want to do is call the 0-argument constructor on this object:

List::List(const int x) : List() 
 insert(x);

Size type

unsigned short length();

Why are you returning unsigned short? It is a rare type with not many good reasons to use it. If you're lazy, return int. If you want to be correct, return std::size_t (defined in cstddef).

On the same topic, in the implementation of length() you are using short as the counter variable, but returning unsigned short. This technically isn't wrong, but is a code smell.

unsigned short List::length() 
 short c = 0;
 (...)
 return c;

Aggregate initialization

You can simplify the code for creating and initializing new Node structs:

head = new Node;
head->x = x;
head->next = nullptr;
head->prev = nullptr;

The above can simplify to:

head = new Nodex, nullptr, nullptr;

This occurs in 4 places in your code.

Category

Random preview

Double Linked-List Implementation

3 Answers 3

Delete nodes in the destructor

Finish adding double-linked list functionality

Break up responsibility

Don't use operator+

Make it templated

Write more idiomatic C++

Improve variable names

Fix minor formatting issues

Const Correctness

Exception safety

Use Boolean Values Directly

Operator Usage

Retain Information

Call the other constructor properly

Size type

Aggregate initialization

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

Delete nodes in the destructor

Finish adding double-linked list functionality

Break up responsibility

Don't use operator+

Make it templated

Write more idiomatic C++

Improve variable names

Fix minor formatting issues

Delete nodes in the destructor

Finish adding double-linked list functionality

Break up responsibility

Don't use operator+

Make it templated

Write more idiomatic C++

Improve variable names

Fix minor formatting issues

Delete nodes in the destructor

Finish adding double-linked list functionality

Break up responsibility

Don't use operator+

Make it templated

Write more idiomatic C++

Improve variable names

Fix minor formatting issues

Delete nodes in the destructor

Finish adding double-linked list functionality

Break up responsibility

Don't use operator+

Make it templated

Write more idiomatic C++

Improve variable names

Fix minor formatting issues

Const Correctness

Exception safety

Use Boolean Values Directly

Operator Usage

Retain Information

Const Correctness

Exception safety

Use Boolean Values Directly

Operator Usage

Retain Information

Const Correctness

Exception safety

Use Boolean Values Directly

Operator Usage

Retain Information

Const Correctness

Exception safety

Use Boolean Values Directly

Operator Usage

Retain Information

Call the other constructor properly

Size type

3 Answers
3

Don't use `operator+`

3 Answers
3

3 Answers
3

Don't use `operator+`

Don't use `operator+`

Don't use `operator+`

Don't use `operator+`