Hi I am trying to find out a way to swap two nodes in an unordered linked list. I want to find out a way where i can change the links of the two nodes so they are swapped. I know I am supposed to use the previous and next links as a way to swap them but I've tried a lot and I don't understand the algorithm. This is what I did so far, but it just deletes the node instead of swapping it and sometimes gives me a java heap error.

``````public void swap (int idx1, int idx2){							//error
Node node1prev;
Node node2prev;
Node tmp;

node1prev = this.getNode(idx1).prev;
node2prev = this.getNode(idx2).prev;

tmp = this.getNode(idx2).next;

if (this.getNode(idx1).next == this.getNode(idx2))
{
this.getNode(idx2).next = this.getNode(idx1);
this.getNode(idx1).next = tmp;
}
else
{
this.getNode(idx2).next = this.getNode(idx1).next;
this.getNode(idx1).next = tmp;
this.getNode(idx2).prev.next = this.getNode(idx1);
}

}``````

can someone please help? I want to swap the nodes, not the data within because I've already done that and it's easy to do, but I want to find a way to actually change the links of both nodes so the nodes swap altogether.

Thanks!

2
Contributors
3
Replies
6
Views
8 Years
Discussion Span

The concept is fairly simple, when you can use "temp" references. It's when you can't that it gets hard.

``````n1 = getNode(idx1)
n2 = getNode(idx2)

temp = n1.next
n1.next = n2.next
n2.next = temp

temp = n1.prev
n1.prev = n2.prev
n2.prev = temp``````

This is, of course, not thread-safe, though.

The concept is fairly simple, when you can use "temp" references. It's when you can't that it gets hard.

``````n1 = getNode(idx1)
n2 = getNode(idx2)

temp = n1.next
n1.next = n2.next
n2.next = temp

temp = n1.prev
n1.prev = n2.prev
n2.prev = temp``````

This is, of course, not thread-safe, though.

well thanks for replying but it just deleted the nodes

Because you need to "extend" it a bit further. I never said that was complete. I am not here to do your homework for you.

``````n1.prev.next = n2
n1.next.prev = n2

n2.prev.next = n1
n2.next.prev = n1``````

And I'll leave it to you to figure out whether this goes before or after that above.

Edit: And to figure out whether or not it will need any "special" handling if the two nodes immediately follow one another.