Class LockFreeOrderedList<E>

  extended by org.amino.ds.lockfree.LockFreeList<E>
      extended by org.amino.ds.lockfree.LockFreeOrderedList<E>
Type Parameters:
E - the type of elements held in this collection
All Implemented Interfaces:
java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>

public class LockFreeOrderedList<E>
extends LockFreeList<E>

This an implementation of a lock-free ordered linked list data structure. The implementation is according to the paper High Performance Dynamic Lock-Free Hash Tables and List-Based Sets by Maged M. Michael, 2002. To gain a complete understanding of this data structure, please first read this paper, available at:

An unbounded thread-safe linked list which its element is ordered. A LockFreeOrderedList is an appropriate choice when many threads will share access to a common collection. This list does not permit null elements. All elements in the list is ordered according to compare()

This is a lock-free implementation intended for highly scalable add, remove and contains which is thread safe. All mothed related to index is not thread safe. Add() will add the element to the head of the list which is different with the normal list.

Xiao Jun Dai

Nested Class Summary
Nested classes/interfaces inherited from class org.amino.ds.lockfree.LockFreeList
LockFreeList.Entry<E>, LockFreeList.ListStateHolder<E>
Field Summary
Fields inherited from class org.amino.ds.lockfree.LockFreeList
Constructor Summary
          Creates a LockfreeList that is initially empty.
LockFreeOrderedList(java.util.Collection<? extends E> c)
          Creates a LockfreeList initially containing the elements of the given collection, added in traversal order of the collection's iterator.
Method Summary
 boolean add(E e)
          Adds the specified element to this list.
Methods inherited from class org.amino.ds.lockfree.LockFreeList
add, addAll, addAll, clear, contains, containsAll, get, indexOf, isEmpty, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, retainAll, set, size, subList, toArray, toArray
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.util.List
equals, hashCode

Constructor Detail


public LockFreeOrderedList()
Creates a LockfreeList that is initially empty.


public LockFreeOrderedList(java.util.Collection<? extends E> c)
Creates a LockfreeList initially containing the elements of the given collection, added in traversal order of the collection's iterator.

c - the collection of elements to initially contain
Method Detail


public boolean add(E e)
Adds the specified element to this list.

Thread Safe

Specified by:
add in interface java.util.Collection<E>
Specified by:
add in interface java.util.List<E>
add in class LockFreeList<E>
e - the element to add.
true (as per the general contract of Collection.add).

Copyright © 2008. All Rights Reserved.