5 replies to this topic

[thieflock]

I've been trying to google a good tutorial on how to swap notes in a linked list, but not luck. I looked at some of the tutorials here at codecall but I didn't find what I was looking for. I need to design a function that can swap two nodes given a certain condition. If you someone could redirect me to a site or tutorial that would be great.

Thanks.

[WingedPanther]

Swapping nodes is simply a matter of swapping the pointers.

void swapptrs(int* first, int* second){
  int* temp;
  temp=first;
  first=second;
  second=temp;
}

You will have to change the pointer type as needed.

You'll have to take some additional care with the nodes to move the Next pointers as well, but this is the basic idea.

Edited by WingedPanther, 09 December 2008 - 08:57 AM.
add note about next pntrs

[TALucas]

With a linked list each node will have a next and previous node. Lets say you have the following:

nodeA----nodeB----nodeC----nodeD----nodeE

If you knew which nodes you wanted to swap...lets say B and D. you could do the following.

nodeB.setNext(nodeE)
nodeB.setPrevious(nodeC)

nodeD.setNext(nodeC)
nodeD.setPrevious(nodeA)

you may have to iterate through the list, and create a temp node to hold the position of a node.

Do you have your linked list and node classes created yet?

*************************
I just noticed this was a c/c++ question...I'm still pretty new here. So wanted to say sorry for the java flavor. But the structure should work the same.

Edited by TALucas, 09 December 2008 - 10:35 AM.
added comments

[WingedPanther]

The number of links will depend on whether you are supposed to traverse it backwards. Some linked lists only have a child link, but not a parent link.

To swap B and D, you have to update links from A to B, B to A, B to C, C to B, and the corresponding C/D/E pairs.

You also have to take into account the boundary conditions, A and E. If swapping E with an element, it has no child to update the links of. Similarly, A has no parent.

[TALucas]

Good catch WingedPanther,

I didn't point out that you would also need to update A,C,E

Here's what I had before:

nodeB.setNext(nodeE)

nodeB.setPrevious(nodeC)

nodeD.setNext(nodeC)

nodeD.setPrevious(nodeA)

you would also need:

nodeA.setNext(nodeD)

nodeC.setPrevious(nodeD)

nodeC.setNext(nodeB)

nodeE.setPrevious(nodeB)

[WingedPanther]

I got caught by that a while back when I was working with linked lists. VERY annoying. I also walked off the end of my list and got nasty errors.