CODEWITHSUNDEEP
.net.net-2.0linked-list
serhio
serhio

Reputation: 28586

Exchange two nodes in LinkedList

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?

Upvotes: 0

Views: 471

Answers (2)

Jon Skeet
Jon Skeet

Reputation: 1500785

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...

Upvotes: 2

Svante
Svante

Reputation: 51501

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.

Upvotes: 2

Related Questions