Exchange two nodes in LinkedList

Question

Hello

I encountered a simple "problem": Exchange two nodes in a LinkedList (.NET 2) How can I do it in a "optimal" way. Thanks!

Dim label1 As New Label()
Dim label2 As New Label()
'... some code
Dim testList As New LinkedList(Of Label)
'... some code
Dim node1 As LinkedListNode(Of Label) = testList.Find(label1)
Dim node2 As LinkedListNode(Of Label) = testList.Find(label2)


If ??? Then
  ' exchange two nodes
End If

is the

node1.Value = label2
node2.Value = label1

sufficient?

Answer 1

How about:

testList.AddAfter(node1, node2.Value)
testList.AddAfter(node2, node1.Value)
testList.Remove(node1)
testList.Remove(node2)

This is four O(1) operations, and will work whether the nodes are at the start or end of the list. The only problem is that if node1 == node2 it will add two new nodes, remove the existing one, and then throw an exception as it tries to remove it again. Obviously this isn't a problem if your algorithm makes sure they're different to start with...

EDIT: Doh. The MSDN docs misled me into thinking that Value is read-only. (It says: "Gets the value contained in the node" - rather than "Gets or sets [...]." Actually it's writable, so you could do:

Label tmp = node1.Value
node1.Value = node2.Value
node2.Value = tmp

On the other hand, anything that already has a reference to the nodes will see the change, which may not be what you want. Of course, anything that already has a reference to the nodes will end up seeing nodes which are no longer part of the list using my first approach...

Answer 2

I don't know the implementation, but if your nodes have simply one value (in addition to the next and previous links), you can just swap the values.