Thread safe switching of Linked-List nodes without locking the entire list

I'm learning about threads, locks etc. Therefore, I don't want to use synchronized key word or any class that is thread-safe other then semaphore and ReentrantLock (without Atomic variables).

I want to have kind of synchronized LinkedList<T> of Node<T>, order by the size of T (assume that T is implements an interface that have size and increment functions and lock, unlock functions). I want to be able to replace two Nodes by their T.getSize() function without locking all the list.

For example, if I only had one thread the function will be a "classic" replace function, something like that:

public void IncrementAndcheckReplace(Node<T> node)
{
    node.getData().incrementSize();
    Node nextNode = node.getNext();
    if(nextNode == null)
        return;
    while(node.getData().getSize() > nextNode.getData().getSize())
     {
        node.getPrev().setNext(nextNode);
        nextNode.setPrev(node.getPrev());
        Node nextnext = nextNode.getNext();
        nextNode.setNext(node);
        node.setPrev(nextNode);
        node.setNext(nextnext);
        nextnext.setPrev(node);

        nextNode = node.getNext();
        if(nextNode == null)
            break; 
    }

}

now lets get to the synchronized problem.

I thought about trying to do something like that to create a lock for my Nodes:

public void IncrementAndcheckReplace(Node<T> node)
{
    node.lock(); //using fair ReentrantLock for specific node       
    node.getData().incrementSize();
    Node nextNode = node.getNext();
    if(nextNode == null)
    {
        node.unlock();
        return;
    }
    nextNode.lock();
    while(node.getData().getSize() > nextNode.getData().getSize())
     {
        Node prev = node.getPrev();
        if(prev != null)
        {
            prev.lock();
            prev.setNext(nextNode);
        }
        nextNode.setPrev(prev);
        Node nextnext = nextNode.getNext();
        if(nextnext != null)
        {
            nextnext.lock();
            nextnext.setPrev(node);
        }
        nextNode.setNext(node);
        node.setPrev(nextNode);
        node.setNext(nextnext);
        if(prev!=null)
            prev.unlock();
        if(nextnext!=null)
            nextnext.unlock();
        nextNode.unlock();

        nextNode = node.getNext();
        if(nextNode == null)
            break;
        nextNode.lock();
    }
    node.unlock();
}

the problem is that this is not thread safe as all, and dead-lock may happens. For example lets assume that we have Node a, Node b which a.next == b and b.prev==a that now if thread A trying to use replace function on a, and thread B trying to use replace function on b, they will both be locked and I will get nowhere ever.

how can I make the replace function to be thread safe without lock the entire list? I want to avoid dead-lock and starvation.

thanks!

The most general answer, permitting the most concurrency, is to lock all of the four nodes involved in the reordering. After they are all locked, check that the ordering hasn't changed - perhaps aborting and retrying if it has - then do the reordering, then release the locks in reverse order.

The tricky part is that, to avoid deadlock, the nodes have to be locked in order according to some fixed order. Unfortunately, ordering them by position in the list won't work, since that ordering can change. The nodes' hashCode and identityHashCode aren't guaranteed to work, since there can be collisions. You'll need to provide some ordering of your own, for example by giving each node a unique permanent ID on construction, which can then be used for the locking order.