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!

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.

Edited 7 Years Ago by masijade: n/a

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.

Edited 7 Years Ago by masijade: n/a

This question has already been answered. Start a new discussion instead.