C++: Doubly linked list

Question

I have written the code for linked list in c++. It has function list_search(int) which returns the node of the given number. list_insertfront(int) inserts the first element. list_insert(int) inserts the element. list_delete(int) deletes the element after searching its node.

#include <iostream>
class double_list{
 struct Node{
 int data;
 struct Node *next; //next will hold the address and *next will show value at that address
 struct Node *prev; //prev will hold the address and *prev will show value at that address
 } *head;
 public:
 double_list(){
 head=NULL; // all address in head are initialised to NULL
 }
 void list_insert(int);
 void list_insertfront(int);
 struct Node *list_search(int n){
 Node *node =new Node();
 node=head;
 while(node!=NULL){
 if(node->data==n) return node;
 node=node->next;}
 std::cout<<"No such elementin the list \n";
 }
 void list_delete(int);
 void display();
};
void double_list::list_insertfront(int n){
Node *node=new Node();
node->data=n;
node->next=head;
head=node;
node->prev=NULL;
}
void double_list::list_insert(int n){
 Node *node =new Node();
 Node *temp =new Node();
 node->data=n;
 node->next=NULL;
 temp=head;
 while(temp){
 if(temp->next==NULL){
 temp->next=node;
 break;
 }
 temp=temp->next;
 }
}
void double_list::list_delete(int n){
 Node *node=list_search(n);//to search node of the given number
 Node *temp=new Node();
 temp=head;
 if(temp==node){
 head=temp->next;
 }
 while(node!=NULL){
 if(temp->next==node) temp->next=node->next;
 temp=temp->next;
 return;
 }
}
void double_list::display(){
 Node *node=new Node();
 node =head;
 while(node!=NULL){
 std::cout<<node->data<<" ";
 node=node->next;
 }
}
int main()
{
 double_list list1;
 list1.list_insertfront(5);
 list1.list_insert(1);
 list1.list_insert(6);
 list1.list_insert(7);
 list1.display();
 list1.list_delete(1);
 std::cout<<"\n";
 list1.display();
 std::cout<<"\n";
 return 0;
}

What should I do to improve this code.

Answer 1

Improvements

What should I do to improve this code.

Well it is linked forward and backward. But you have not facility to use the backwards part as you have to always start at the head.

Add a tail pointer to your list then you can scan from the back.

Personally I would also add a sentinel node. This will remove the need to constantly check for nullptr.

Code Review

Unlike C structs use the same namespace for structures as other type definitions. So once defined there is no need to use struct again.

struct Node{
 int data;
 struct Node *next;
 struct Node *prev;
 } *head;
struct Node{
 int data;
 Node *next; // Note no struct here
 Node *prev;
 } *head;

Also separate the structure declaration and its usage:

 Node* head;
 Node* tail;

Use the constructor to initialize an object

Node *node=new Node();
node->data=n;
node->next=head;
head=node;
node->prev=NULL;
// Can be simplified too:
Node* node = new Node{n, headhead, nullptr);

Don't use NULL C++ has nullptr

NULL is C for zero. While the C++ nullptr is a pointer type. Thus it can not accidentally be assigned to a numerical variable (it can only be assigned to a pointer variable).

std::cout is not the only stream

In display() it only uses std::cout. Should be able to print to any stream. So change the interface to:

void display(std::ostream& out = std::cout) // default to std::cout
 // but let other streams be used

Then also add

std::ostream& operator(std::ostream& s, double_list const& list)

Note:
The standard way of printing things in C++ is to use operator<< you should also be able to print a list using it.

Bugs

You seem to have a memorty leak here:

 struct Node *list_search(int n){
 Node *node =new Node(); // why this is leaked in the next line.
 node=head;

Fix by doing this:

 struct Node *list_search(int n){
 Node *node = head;

Same issue in list_insert

Node *temp =new Node();
...
temp=head;

And once more in list_delete

Node *temp=new Node();
temp=head;

This looks broken

while(node!=NULL){
 if(temp->next==node)
 temp->next=node->next;
 temp=temp->next;
 return; // Seems to return after the first iteration.
}

Rule of 3/5 Violation

You need to look up the rule of 5/3. Currently your list will not do what you expect when you copy it.

But it will not crash at the moment because you leak all the nodes on destruction. But when you fix the leak the copying will become a problem.

Improved Version

#include <iostream>
class DoubleList
{
 struct Node
 { 
 Node* next;
 Node* prev;
 }; 
 struct DataNode: public Node
 { 
 int data;
 DataNode(int val, Node* next, Node* prev)
 : Node{next, prev}
 , data(val)
 {} 
 }; 
 Node sent;
 public:
 DoubleList()
 : sent{&sent, &sent}
 {} 
 ~DoubleList()
 { 
 Node* next;
 for(Node* tmp = sent.next; tmp != &sent; tmp = next) {
 next = tmp->next;
 delete tmp;
 } 
 } 
 DoubleList(DoubleList const&) = delete;
 DoubleList& operator=(DoubleList const&) = delete;
 void insertFront(int val) {insert(val, sent.next, &sent);}
 void insertBack(int val) {insert(val, &sent, sent.prev);}
 bool deleteVal(int val)
 { 
 Node* find = findVal(val);
 if (find != nullptr) {
 find->prev->next = find->next;
 find->next->prev = find->prev;
 delete find;
 } 
 return find != nullptr;
 } 
 void print(std::ostream& str = std::cout) const
 { 
 for(Node* tmp = sent.next; tmp != &sent; tmp = tmp->next) {
 str << static_cast<DataNode*>(tmp)->data << " ";
 } 
 } 
 friend std::ostream& operator<<(std::ostream& str, DoubleList const& list)
 { 
 list.print(str);
 return str;
 } 
 private:
 void insert(int val, Node* next, Node* prev)
 { 
 Node* node = new DataNode(val, next, prev);
 node->next->prev = node;
 node->prev->next = node;
 } 
 Node* findVal(int val)
 { 
 for(Node* tmp = sent.next; tmp != &sent; tmp = tmp->next) {
 if (static_cast<DataNode*>(tmp)->data == val) {
 return tmp;
 } 
 } 
 return nullptr;
 } 
};

Then Main

int main()
{
 DoubleList list1;
 list1.insertFront(5);
 list1.insertBack(1);
 list1.insertBack(6);
 list1.insertBack(7);
 std::cout << list1 << "\n";
 list1.deleteVal(1);
 std::cout << list1 << "\n";
}

• coder: DoubleList(DoubleList const&) = delete; and DoubleList& operator=(DoubleList const&) = delete; means. What they do?
• Incomputable: @coder, they don't allow compiler to default generate it and any invocation of those functions make the program ill-formed (aka compiler will print an error saying the function has been deleted, thus not callable). Purely compile time thing. He put it there because the class does not implement rule of three, and thus those functions disallow any ownership transfer. Go lookup everything I've said, it is really important.

Answer 2

1. Well, it starts with the name. double_list looks like a list of doubles, not a doubly-linked-list, which would be better named list. Anyway, your code doesn't work as a doubly-linked list, and anyway you have one member too few for that.

2. But your list isn't a generic list of T, but a specific list of int, so that should be reflected in the name too, leading to list_int. Better to bite the bullet and templatize it.

3. Use one style for class-names, and use it consistently: Either snake_case like the standard, or UpperCamelCase, but please not a mix.

4. While you can declare a member and a type at the same time, please desist. It's non-obvious, and mimics the pattern of declaring a tag and a typedef-name at the same time in C and C/C++-combi-headers.

5. Use C++11 nullptr instead of the obsolete NULL-macro. The latter can result in surprising behavior as it can be a zero constant.

6. Use consistent indentation. Always indent the same amount, and don't forget to indent / dedent as neccessary.

7. You can signal an error with the return-value or an exception, depending on whether it is expected. But don't ever try interacting with the user directly from generic library code. It seriously restricts usability.

8. list_search must return a value on every execution-path. If your compiler didn't complain loudly, you should fix your invocation.

9. Try to use a for-loop directly instead of simulating it with a while-loop.

10. I wonder why many of your member-functions drag around the prefix list_ as if they were free C-functions.

11. list_delete and display leak memory.

12. You are violating the rule-of-three: Your class manages a resource, except is misses a custom copy-ctor and dtor.

13. Consider allowing output to a different std::ostream than std::cout. While you are at it, implement the stream-output-operator to conform to the standard stream interface.

Answer 3

You should reformat your file for consistent indentation. Most modern IDEs have a feature to do this for you. There are also issues with the way you've arranged your braces.

You may want to consider making this class templated rather than hard-coded for int.

In list_search, do not initialize node to a new Node(), especially since you initialize it to head on the line directly after.

Typo - elementin should be element in

When you output any kind of error (such as "No such element in the list"), you should be using cerr rather than cout.

display() should be display() const since it should not mutate members.

• Loki Astari: Most modern IDEs: If an editor does not have this functionality then you should not be using it to program with. My standard editor vim has this build in (though must would also say that is a modern IDE).
• Reinderien: @LokiAstari You're right, of course; this equates to "most IDEs and many editors".