title: concurrent linked list
body: <p>I am trying to design a linked list in c++ that allows concurrent access. Clearly using a single lock for this list is grossly inefficient since disjoint areas may be updated in parallel. Now what are my options other than storing a lock per node? </p>
  
  <p>Also, would a non-blocking version be a better bet in this case? Any relevant links, anyone?</p>
  
  <p><strong>EDIT</strong>: Thanks for the responses people. Couple of things I'd like to add: </p>
  
  <ol>
  <li>How about storing N locks for every M nodes instead of 1:1 lock:node ratio? Some threads would wait but it's kind of a trade off. What do you think?</li>
  <li>If I intend to find some node in this linked list looks like all the mutexes need be locked. This is an issue, because locking and unlocking of all the mutexes is time consuming. Does anyone have a better alternative?</li>
  <li>I am open to non-blocking algorithms. But how do I use CAS in good old C++ without using assembly? I hear that gcc has some __sync attributes that do similar work but not sure. </li>
  <li>With non-blocking approach, how do you do a find on the linked list?</li>
  </ol>