Author Message

I've been having problems writing a function to swap nodes in a doubly
linked list.  At one time (before I accidently erased the code), I was
able to make it swap the nodes as long as neither was at the start or
end of the list and they weren't next to each other.  I don't want to
just swap the data in the nodes because the nodes are rather large and
I'd like to do it the proper way anyway.

Would someone be so kind as to give me some help here?

--

Sun, 24 Mar 2002 03:00:00 GMT

Quote:

> I've been having problems writing a function to swap nodes in a doubly
> linked list.  At one time (before I accidently erased the code), I was
> able to make it swap the nodes as long as neither was at the start or
> end of the list and they weren't next to each other.  I don't want to
> just swap the data in the nodes because the nodes are rather large and
> I'd like to do it the proper way anyway.

> Would someone be so kind as to give me some help here?

Ben...

If p1 is a pointer to the first node (n1) and p2 is a pointer to the
second node (n2), then for non-terminal nodes all that should be
necessary is to do something like:

pf1 = p1->fwd_ref;   /* save n1 fwd link     */
pb1 = p1->bkw_ref;   /* save n1 bkw link     */
pf2 = p2->fwd_ref;   /* save n2 fwd link     */
pb2 = p2->bkw_ref;   /* save n2 bkw link     */

pf1->bkw_ref = p2;   /* Update pointers on   */
pb1->fwd_ref = p2;   /*   both sides of n1   */
pf2->bkw_ref = p1;   /* Update pointers on   */
pb2->fwd_ref = p1;   /*   both sides of n2   */

p1->fwd_ref = pf2;   /* Update n1 fwd and    */
p1->bkw_ref = pb2;   /*   bkw pointers       */
p2->fwd_ref = pf1;   /* Update n2 fwd and    */
p2->bkw_ref = pb1;   /*   bkw pointers       */

For a terminal node, the pointers will only need to be updated on one
side; and I leave that logic to you. If you're maintaining pointers to
head/tail of the list, then you'll need to check to see if those
pointers need to be updated.

Sometimes it helps to draw yourself a picture.

Morris Dovey
West Des Moines, Iowa USA

Sun, 24 Mar 2002 03:00:00 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages