2
\$\begingroup\$

I am learning to write a multi-threaded linked list class implementation with basic functionality such as push to front or back, pop_back and read. I came up with this implementation:

#include <iostream>
#include <thread>
#include <mutex>
std::mutex m;
template<class T>
class Node{
    public:
    T data;
    Node* next;
    Node(T data):data(data),next(NULL){}
};
template<class T>
class List{
  Node<T> *head;
  public:
  List():head(NULL){}
  List(const List<T>&)=default;               //default copy constructor
  List& operator =(const List<T>&)=default;   //default assignment
  List(List<T>&&)=default;                    //default move constructor
  List& operator =(List<T>&&)=default;        //default move assignment
  void push_front(T val){                    //push data to front
    std::lock_guard<std::mutex> lock(m);
    Node<T>* temp=new Node<T>(val);
      if(head==NULL)
        head=temp;
      else{

          temp->next=head;
          head=temp;
      }
  }
  void pop_back(){                      //pop from back
      std::lock_guard<std::mutex> lock(m);
      Node<T>* cur=head;
      while(cur->next->next)
      cur = cur->next;
      Node<T>* temp=cur->next;
      delete(temp);
      cur->next=NULL;
  }
  T front(){                 //return front of Linkedlist
      if(head!=NULL)
      return head->data;
      return -1;
  }
  void push_back(T val){                    //push at back
      std::lock_guard<std::mutex> lock(m);
      Node<T>* temp=new Node<T>(val);
      if(head==NULL)
        head=temp;
      else{
          Node<T>* cur=head;
          while(cur->next)
          cur = cur->next;
          cur->next=temp;
      }
  }
  int size(){               //return size
      int size=0;
      Node<T>* cur=head;
      while(cur){
        size++;
        cur=cur->next;
      }
      return size;
  }
  void display(){            //read from linked list
      std::lock_guard<std::mutex> lock(m);
      Node<T>* cur=head;
      while(cur){
          std::cout<<cur->data<<" ";
          cur = cur->next;
      }
      std::cout<<"\n";
  }
  ~List(){
    Node<T>* current = head;
    Node<T>* next;
    while (current != NULL) {
        next = current->next;
        delete current;
        current = next;
    }
  }
};

But, I am not very sure if I covered it right. Please share some opinions on how to make it perfect. Also, I am targeting C++11, so please throw some pointers/suggestions in that area also.

In particular, I am looking for is answers to these questions:

  1. Is this a correct approach for acquiring mutex in push() and display(), in a multi-threaded environment?
  2. How can I prioritize the read/delete/write operations. For example, suppose 1 thread is displaying the data and another thread comes which wants to pop_back from the data. How do I make the changes so that my 2nd thread gets the priority while 1st thread was using my node.
  3. I have not much worked with C++11 — I just started it few months ago — so I would like to know what more I should have in my class.
  4. In case there are any possible bugs in this code, please let me know that too.
\$\endgroup\$
  • \$\begingroup\$ Whoever so gave me -1, please I would like to understand why? Should I be giving more details, is it not clear enough? \$\endgroup\$ – DevCplusplus Nov 12 at 19:00
  • 1
    \$\begingroup\$ I didn't downvote, but did you test this before posting? Does it appear to work? Are you sure you want your deconstructie written like that? \$\endgroup\$ – Mast Nov 12 at 19:08
  • 1
    \$\begingroup\$ yes, of course I tested it, It is working. I am not sure what's wrong with the deconstructor, can you explain more please? \$\endgroup\$ – DevCplusplus Nov 12 at 19:10
  • 1
    \$\begingroup\$ The person that downvoted [presumably] also voted to close for "lacks concrete context", a very disputable reason in this case. Consider editing your post to add more information about what your code is doing and how it's doing it, but I see nothing wrong with your post. \$\endgroup\$ – Mathieu Guindon Nov 12 at 19:35
  • \$\begingroup\$ Thanks! I have edited the post with the specific questions to which I need answer for. \$\endgroup\$ – DevCplusplus Nov 13 at 5:16
5
\$\begingroup\$

About the code:

  1. List& operator =(const List<T>&)=default; and List(const List<T>&)=default; provide excellent opportunity to get double delete with 100% chance of success.
  2. Your linked list required data to be copyable and it copies it on usage. It is bad, since now you cannot store data like std::unique_ptr that are not copyable. Also it is inefficient as it will have to copy large data structures like std::vector instead of moving their internal data around. Utilize std::move in functions like push_back/push_front.
  3. Functions front()/back() should return data by reference so user can modify them. Also you ought to implement their const versions that return data by const reference (or by value for trivial enough data types).
  4. std::list stores also the size of the list so the function call is lazy unlike your implementation. People generally assume that size() is a fast operation which is not the case in your implementation.
  5. Normally in a linked-list you store both head and tail as otherwise all operations regarding the other end are ridiculously slow.
  6. std::cout is not exactly thread safe. It doesn't crash or cause malfunctions but it might can mingle the characters you print. In a multi-threaded environment you need a logger.
  7. Wait... your linked-list doesn't provide any options for iterating over elements. Only adding / deleting / exploring elements at the head/tail and even those are slow. You need iterators or something. One important aspect of a linked list is ability to move elements from one list to another efficiently. This functionality doesn't exist in this implementation.
  8. Your mutex m is shared across all your linked lists-instances and types. If you want any sensible implementation of multi-threaded linked with mutexes list you ought to privately store a std::unique_ptr<std::mutex> for each instance of the linked-list.
  9. Honestly, I don't know why you want to use a linked list or implement one - it is one of the slowest and most inefficient data structures.

In general, I don't think that it is a good idea to make a thread-safe linked-list. Make a concurrent linked-list at most I'd say (I not too familiar on this topic as far as I am aware it is still being researched). Just use std::list and have an associated mutex nearby so whenever user wants to do something with the list - they have to lock the mutex. It might be annoying to write and relying on the user to use it right is problematic but frequently user needs to make composite operations (several in a row without interruptions) which will result in program errors if another users locks the list in between these operations and does something with it.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed review! I agree with 3-8 points. In 1) and 2) do you mean I should have List& operator =(const List<T>&)=delete; and List(const List<T>&)=delete; instead of List& operator =(const List<T>&)=default and List(const List<T>&)=default; since unique_ptr can not have the copy constructor \$\endgroup\$ – DevCplusplus Nov 13 at 16:47
  • \$\begingroup\$ 9. I am just prepping up for interview's and linked list seems to be a very very important topic being asked around. \$\endgroup\$ – DevCplusplus Nov 13 at 16:48
  • 1
    \$\begingroup\$ (1) either delete the copy-ctor/assignment or make a custom implementation that copies the data - a deep copy not a shallow copy. @MFCDev \$\endgroup\$ – ALX23z Nov 13 at 18:25
  • 1
    \$\begingroup\$ (2) In say, push_back you write Node<T>* temp=new Node<T>(std::move(val)); instead of Node<T>* temp=new Node<T>(val); @MFCDev \$\endgroup\$ – ALX23z Nov 13 at 18:27
  • \$\begingroup\$ @MFCDev On the second look, your move ctor/assignment also lead to double delete. You ought to make a custom implementation as well. \$\endgroup\$ – ALX23z Nov 15 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.