0

A thread safe method to delete nodes from a Linkedlist. 

 public void delete(String x, LinkedList<String> list)
   {
      String lock = "false";
        for (int i = 0; i < list.size(); i++) {
            synchronized (lock) {
                if (list.get(i).equals(x)) {
                    lock = "true";
                    list.remove(i);
                }
                lock = "false";
            }
        }
   }

Many thanks!

Edit: the above method is thread safe but its performance needs to improve. It is an interview question.

Bobo
  • 8,777
  • 18
  • 66
  • 85
  • 1
    This may be more appropriate for [Code Review](http://codereview.stackexchange.com/) – Beau Grantham May 07 '12 at 19:58
  • 3
    Definitely not enter synchronized block *inside* a loop. This is at the same time detrimental to performance **and** thread-unsafe. – Marko Topolnik May 07 '12 at 19:58
  • 1
    Is this really about multiple threads or are you getting an exception because you are removing from the list while iterating across it? – Gray May 07 '12 at 19:58
  • And you are using indexed iteration over a `LinkedList`? A performance abyss right there. – Marko Topolnik May 07 '12 at 19:59
  • Here's good information about why _not_ to synchronize on a boolean. As mentioned, there are a lot of other errors here. http://stackoverflow.com/questions/10324272/why-is-it-not-good-practice-to-synchronize-on-boolean/10324280#10324280 – Gray May 07 '12 at 20:13
  • 1
    If someone gave you that in and interview and told you it's threadsafe with a straight face, look for another job! – Affe May 08 '12 at 05:38
  • @Gray He's synchronizing on a String literal, but in all probability this is irrelevant. – Marko Topolnik May 09 '12 at 12:22

7 Answers7

3

  1. synchronizing on an object that is local to the method isn't really doing anything useful. Also, overwriting the reference to the object you're locking on inside the synchronized block is confusing in purpose. Some explanation on the purpose of that code might help us help you improve it :)

  2. The actual question. get(i) and remove(i) both require you to iterate the list out to position i. If you use the list's actual iterator and the iterator's remove method, you will only have to iterate the entire list once.

Gray
  • 115,027
  • 24
  • 293
  • 354
Affe
  • 47,174
  • 11
  • 83
  • 83
2

Thread-safe:

public void delete(String x, LinkedList<String> list) {
    synchronized (list) {
       for (Iterator<String> it = list.iterator(); it.hasNext();)
            if (it.next().equals(x)) it.remove();
    }
}

But, in all probability, your problem wasn't thread safety. You used list.delete() while iterating through the list and got ConcurrentModificationException. If that is the case, feel free to remove synchronized block.

Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
  • Sort of, only if every operation on the list is performed via the same instance of whatever class holds this method. – Affe May 07 '12 at 20:04
  • tried your method it works but seems to be only the first thread is really doing the work. every other threads are blocked by synchronized (list) – Bobo May 09 '12 at 12:19
  • Well we didn't see any specification of concurrency in your problem. Update your question with appropriate details and alert with a comment. BTW What I show already is a thread-safe method with improved performance. The original is neither thread-safe nor performant. – Marko Topolnik May 09 '12 at 12:20
1

I would use List.removeAll

List<String> list = new LinkedList<>();
list.addAll(Arrays.asList("a,b,c,d,a,b,c,d,e,a,b,a,b".split(",")));
System.out.println("Before removeAll(a) " + list);

list.removeAll(Collections.singleton("a"));

System.out.println("After removeAll " +list);

prints

Before removeAll(a) [a, b, c, d, a, b, c, d, e, a, b, a, b]
After removeAll [b, c, d, b, c, d, e, b, b]
Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
0

Try using out-of-box Java Collections API functionality for synchronized collections. Official documentation.

And also you could use an iterator to remove items. As documentation states:

If an explicit iterator is used, the iterator method must be called from within the synchronized block. Failure to follow this advice may result in nondeterministic behavior.

d1e
  • 6,372
  • 2
  • 28
  • 41
0
public void delete (String x, LinkedList<String> list) {

            synchronized (list) {
                Iterator<String> it = list.iterator();
                while (it.hasNext()) {
                    String y = it.next();
                    if (x.equals(y)) {
                        it.remove();
                    }
                }
            }
        }
象嘉道
  • 3,657
  • 5
  • 33
  • 49
0
public void delete(String x, LinkedList<String> list){
    Set<String> target = Collections.singleton(x);
    synchronized (list) {
        list.removeAll( target );
    }
}

Two things:

  1. Synchronizing on a string you just created does nothing (well, not exactly, since "false" is an interned string, all pieces of code that synchronize on "false" will be synchronized, but that's a hackish way to get application-wide synchronization, and probably not at all what you intended). You should be synchronizing on the list. Everyone using the list should be synchronizing on the list. Although better practice would be to use a synchronized collection in the first place, eliminating the need for an explicit synchronized block in the using code.
  2. removeAll is usually the most efficient method to remove all occurrences of one or more objects from a collection. In the worst case it is equivalent to iterating over the collection and using the iterator to remove the items (which is the case of LinkedList), but for some implementations (like ArrayList) it is made to be more efficient.
trutheality
  • 23,114
  • 6
  • 54
  • 68
0

use this-> http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

memo
  • 441
  • 2
  • 6