0

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
Last Post by masijade
0

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 by masijade: n/a

0

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

0

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 by masijade: n/a

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.