COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

• Email
• Follow

```Hi!

I'm writing function which swaps two arbitrary elements
of double-linked list. References to the next element of list
must be unique or NULL (even during swap procedure), the same condition
should be kept for references to previous element of list.

Here is my solution below:

struct node {
int i;
struct node *p; /* prev */
struct node *n; /* next */
};

void swap ( struct node *a1, struct node *a2 ) {

struct node* a1p = a1->p;
struct node* a2p = a2->p;

struct node* a2n_o = a2->n;
struct node* a1n_o = a1->n;

struct node* a1n = a1->n;
struct node* a2n = a2->n;

struct node* a2p_o = a2->p;
struct node* a1p_o = a1->p;

if ( a1->n == a2 ) {
// ...->[ a1 ]->[ a2 ]->...
if ( a1p != NULL ) {
a1p->n = NULL;
}

if ( a2n != NULL ) {
a2n->p = NULL;
}

a2->n = a1;
a1->n = a2n_o;

a1->p = a2;
a2->p = a1p_o;

if ( a1p != NULL ) {
a1p->n = a2;
}

if ( a2n != NULL ) {
a2n->p = a1;
}

} else if ( a2->n == a1 ) {
// ...->[ a2 ]->[ a1 ]->...
if ( a2p != NULL ) {
a2p->n = NULL;
}

if ( a1n != NULL ) {
a1n->p = NULL;
}

a1->n = a2;
a2->n = a1n_o;

a2->p = a1;
a1->p = a2p_o;

if ( a2p != NULL ) {
a2p->n = a1;
}

if ( a1n != NULL ) {
a1n->p = a2;
}
} else {
// ...->[ a1 ]->...->[ a2 ]->...
if ( a2p != NULL ) {
a2p->n = NULL;
}

if ( a1n != NULL ) {
a1n->p = NULL;
}

if ( a1p != NULL ) {
a1p->n = a2;
}

if ( a2n != NULL ) {
a2n->p = a1;
}

if ( a2p != NULL ) {
a2p->n = a1;
}

if ( a1n != NULL ) {
a1n->p = a2;
}

a1->n = NULL;
a2->n = a1n_o;
a1->n = a2n_o;

a2->p = NULL;
a1->p = a2p_o;
a2->p = a1p_o;
}

}

The question is - how to correctly test effectiveness of such implementation
to optimize it? May be some kind of visualisation to make possible to reduce
quantity of steps or something?

Thanks!
```
 0
Reply esobchenko (4) 11/4/2004 9:24:31 AM

See related articles to this posting

```"Eugen J. Sobchenko" <esobchenko@gmail.com> wrote in message
> Hi!
>
> I'm writing function which swaps two arbitrary elements
> of double-linked list. References to the next element of list
> must be unique or NULL (even during swap procedure), the same condition
> should be kept for references to previous element of list.
>
> Here is my solution below:
>
> struct node {
> int i;
> struct node *p; /* prev */
> struct node *n; /* next */
> };
>
> void swap ( struct node *a1, struct node *a2 ) {
>
> struct node* a1p = a1->p;
> struct node* a2p = a2->p;
>
> struct node* a2n_o = a2->n;
> struct node* a1n_o = a1->n;
>
> struct node* a1n = a1->n;
> struct node* a2n = a2->n;
>
> struct node* a2p_o = a2->p;
> struct node* a1p_o = a1->p;
>
> if ( a1->n == a2 ) {
>                 // ...->[ a1 ]->[ a2 ]->...
> if ( a1p != NULL ) {
> a1p->n = NULL;
> }
>
> if ( a2n != NULL ) {
> a2n->p = NULL;
> }
>
> a2->n = a1;
> a1->n = a2n_o;
>
> a1->p = a2;
> a2->p = a1p_o;
>
> if ( a1p != NULL ) {
> a1p->n = a2;
> }
>
> if ( a2n != NULL ) {
> a2n->p = a1;
> }
>
> } else if ( a2->n == a1 ) {
>                 // ...->[ a2 ]->[ a1 ]->...
> if ( a2p != NULL ) {
> a2p->n = NULL;
> }
>
> if ( a1n != NULL ) {
> a1n->p = NULL;
> }
>
> a1->n = a2;
> a2->n = a1n_o;
>
> a2->p = a1;
> a1->p = a2p_o;
>
> if ( a2p != NULL ) {
> a2p->n = a1;
> }
>
> if ( a1n != NULL ) {
> a1n->p = a2;
> }
> } else {
>                 // ...->[ a1 ]->...->[ a2 ]->...
> if ( a2p != NULL ) {
> a2p->n = NULL;
> }
>
> if ( a1n != NULL ) {
> a1n->p = NULL;
> }
>
> if ( a1p != NULL ) {
> a1p->n = a2;
> }
>
> if ( a2n != NULL ) {
> a2n->p = a1;
> }
>
> if ( a2p != NULL ) {
> a2p->n = a1;
> }
>
> if ( a1n != NULL ) {
> a1n->p = a2;
> }
>
> a1->n = NULL;
> a2->n = a1n_o;
> a1->n = a2n_o;
>
> a2->p = NULL;
> a1->p = a2p_o;
> a2->p = a1p_o;
> }
>
> }
>
> The question is - how to correctly test effectiveness of such
implementation
> to optimize it? May be some kind of visualisation to make possible to
reduce
> quantity of steps or something?
>
> Thanks!

Just swap the data instead of all the pointers:

void swap ( struct node *a1, struct node *a2 ) {
int temp;
temp = a1->i;
a1->i = a2->i;
a2->i = temp;
}

```
 0

```In article <b7a52224.0411040124.319c92be@posting.google.com>,
Eugen J. Sobchenko <esobchenko@gmail.com> wrote:
> Hi!

> I'm writing function which swaps two arbitrary elements
> of double-linked list. References to the next element of list
> must be unique or NULL (even during swap procedure), the same condition
> should be kept for references to previous element of list.

void swap( struct node *a1, struct node *a2 ) {
int temp;

temp = a1->i;
a1->i = a2->i;
a2->i = temp;
}

more below:

> Here is my solution below:

> struct node {
> 	int i;
> 	struct node *p; /* prev */
> 	struct node *n; /* next */
> };

> void swap ( struct node *a1, struct node *a2 ) {

> 	struct node* a1p = a1->p;
> 	struct node* a2p = a2->p;

> 	struct node* a2n_o = a2->n;
> 	struct node* a1n_o = a1->n;

> 	struct node* a1n = a1->n;
> 	struct node* a2n = a2->n;

> 	struct node* a2p_o = a2->p;
> 	struct node* a1p_o = a1->p;

> 	if ( a1->n == a2 ) {
>                 // ...->[ a1 ]->[ a2 ]->...
> 		if ( a1p != NULL ) {
> 			a1p->n = NULL;
> 		}

> 		if ( a2n != NULL ) {
> 			a2n->p = NULL;
> 		}

> 		a2->n = a1;
> 		a1->n = a2n_o;

> 		a1->p = a2;
> 		a2->p = a1p_o;

> 		if ( a1p != NULL ) {
> 			a1p->n = a2;
> 		}

> 		if ( a2n != NULL ) {
> 			a2n->p = a1;
> 		}

> 	} else if ( a2->n == a1 ) {
>                 // ...->[ a2 ]->[ a1 ]->...
> 		if ( a2p != NULL ) {
> 			a2p->n = NULL;
> 		}

> 		if ( a1n != NULL ) {
> 			a1n->p = NULL;
> 		}

> 		a1->n = a2;
> 		a2->n = a1n_o;

> 		a2->p = a1;
> 		a1->p = a2p_o;

> 		if ( a2p != NULL ) {
> 			a2p->n = a1;
> 		}

> 		if ( a1n != NULL ) {
> 			a1n->p = a2;
> 		}
> 	} else {
>                 // ...->[ a1 ]->...->[ a2 ]->...
> 		if ( a2p != NULL ) {
> 			a2p->n = NULL;
> 		}

> 		if ( a1n != NULL ) {
> 			a1n->p = NULL;
> 		}

> 		if ( a1p != NULL ) {
> 			a1p->n = a2;
> 		}

> 		if ( a2n != NULL ) {
> 			a2n->p = a1;
> 		}

> 		if ( a2p != NULL ) {
> 			a2p->n = a1;
> 		}

> 		if ( a1n != NULL ) {
> 			a1n->p = a2;
> 		}

> 		a1->n = NULL;
> 		a2->n = a1n_o;
> 		a1->n = a2n_o;

> 		a2->p = NULL;
> 		a1->p = a2p_o;
> 		a2->p = a1p_o;
> 	}

> }

> The question is - how to correctly test effectiveness of such
> implementation to optimize it? May be some kind of visualisation to
> make possible to reduce quantity of steps or something?

I would suggest writing a check double linked list function to which you
pass the head and tail pointers of the linked list, and a constant array
of ints which list the order of the nodes. Then the function simply scans
the linked list starting with the head and compares each i value with the
next value off of the array, if any of the values are incorrect it then
outputs an error, and then reverses the procedure checking from the tail
to the start of the list.

Then write some code to create a list, and perform some node swaps on it
checking after each swap that the list is correct.

Your swap function looks too complicated. If I was writing it I would say
there are two main cases:
1) The two nodes to swap are next to each other,
2) The two nodes to swap are not next to each other

Then to handle the first case you need to:
1) Remove the first node to swap from the linked list
2) Insert the removed node after the second node to swap

And to handle the second case you need to:
1) Remove one of the nodes to swap from the linked list
2) Insert the removed node after the other node
3) Remove the other node from the linked list
4) Insert the removed node where the original removed node was.

Then write functions to remove a specified node from the linked list, and
to insert a node into it.

Kevin.

```
 0
Reply kevin.bagust (36) 11/4/2004 1:15:09 PM

```On 2004-11-04 01:24, Eugen J. Sobchenko wrote:
> I'm writing function which swaps two arbitrary elements of
> double-linked list. References to the next element of list must be
> unique or NULL (even during swap procedure), the same condition should
> be kept for references to previous element of list.

The constraint of keeping the references NULL or unique during the swap is
something you cannot guarantee by reordering the assignments of the pointers.
Some sort of locking must be used, which is machine-dependent and cannot be
described portably here (i.e. a mutex that protects the entire list, while
reordering operations happen).

One trick that you can use to effectively 'swap' two elements of a list is to
decouple the list linkage from the element data, using something like this:

------------------------------------------------------------------------------
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

struct nodeinfo;
struct node {
struct nodeinfo *n_info;
struct node *n_next;
struct node *n_prev;
};

struct nodeinfo {
int ni_data;
};

struct nodeinfo info1 = { 10 };
struct nodeinfo info2 = { 20 };
struct nodeinfo info3 = { 30 };

struct node node1 = { &info1, NULL, NULL };
struct node node2 = { &info2, NULL, NULL };
struct node node3 = { &info3, NULL, NULL };

static void swapnodes(struct node *_alpha, struct node *_beta);

int
main(void)
{
node1.n_next = &node2;
node2.n_next = &node3;
node3.n_next = &node1;
node1.n_prev = &node3;
node2.n_prev = &node1;
node3.n_prev = &node2;

swapnodes(&node1, &node2);
return (0);
}

static void
{
struct node *np;

return;
do {
if (np->n_info != NULL)
printf("    node %p -> %d\n", np,
np->n_info->ni_data);
else
printf("    node %p -> null\n", np);
np = np->n_next;
} while (np != NULL && np != head);
}

static void
swapnodes(struct node *na, struct node *nb)
{
struct nodeinfo *tmp;

assert(na != NULL && nb != NULL);
tmp = na->n_info;
na->n_info = nb->n_info;
nb->n_info = tmp;
}
------------------------------------------------------------------------------

In this case, the swapping of the two nodes is simplified to the swapping of
two pointers, the n_info members of the nodes.  Note though that parts of the
program cannot keep copies of `struct node' pointers around and reuse them
later.  There is no guarantee that the same nodeinfo will be linked under a
pointer to a node after a while, unless the list is locked.

> Here is my solution below:
>
> struct node {
> 	int i;
> 	struct node *p; /* prev */
> 	struct node *n; /* next */
> };
>
> void swap ( struct node *a1, struct node *a2 ) {
>
> 	struct node* a1p = a1->p;
> 	struct node* a2p = a2->p;
>
> 	struct node* a2n_o = a2->n;
> 	struct node* a1n_o = a1->n;
>
> 	struct node* a1n = a1->n;
> 	struct node* a2n = a2->n;
>
> 	struct node* a2p_o = a2->p;
> 	struct node* a1p_o = a1->p;
>
>       [snip]

``You're lost in a maze of twisty little passages, all alike.''
-- Nethack

Your logic seems fine, and teh way you does swapped those nodes make sense,
but the names are so confusing that it took me the better part of 15 minutes
of careful reading *WITH* a notebook by my side to find out what's going on!

IMHO C source shouldn't be so complex, unless there's a very good reason.

> The question is - how to correctly test effectiveness of such implementation
> to optimize it? May be some kind of visualisation to make possible to reduce
> quantity of steps or something?

Sure, drawing on a whiteboard, a piece of paper or something, is certainly
going to help a lot.

- Giorgos

```
 0
Reply keramida (465) 11/4/2004 1:49:39 PM

```Eugen J. Sobchenko wrote:
>
> Hi!
>
> I'm writing function which swaps two arbitrary elements
> of double-linked list. References to the next element of list
> must be unique or NULL (even during swap procedure), the same condition
> should be kept for references to previous element of list.
>
> Here is my solution below:
>
> struct node {
>         int i;
>         struct node *p; /* prev */
>         struct node *n; /* next */
> };
>
> void swap ( struct node *a1, struct node *a2 ) {
>
>         struct node* a1p = a1->p;
>         struct node* a2p = a2->p;
>
>         struct node* a2n_o = a2->n;
>         struct node* a1n_o = a1->n;
>
>         struct node* a1n = a1->n;
>         struct node* a2n = a2->n;
>
>         struct node* a2p_o = a2->p;
>         struct node* a1p_o = a1->p;
>
>         if ( a1->n == a2 ) {
>                 // ...->[ a1 ]->[ a2 ]->...
>                 if ( a1p != NULL ) {
>                         a1p->n = NULL;
>                 }
>
>                 if ( a2n != NULL ) {
>                         a2n->p = NULL;
>                 }
>
>                 a2->n = a1;
>                 a1->n = a2n_o;
>
>                 a1->p = a2;
>                 a2->p = a1p_o;
>
>                 if ( a1p != NULL ) {
>                         a1p->n = a2;
>                 }
>
>                 if ( a2n != NULL ) {
>                         a2n->p = a1;
>                 }
>
>         } else if ( a2->n == a1 ) {
>                 // ...->[ a2 ]->[ a1 ]->...
>                 if ( a2p != NULL ) {
>                         a2p->n = NULL;
>                 }
>
>                 if ( a1n != NULL ) {
>                         a1n->p = NULL;
>                 }
>
>                 a1->n = a2;
>                 a2->n = a1n_o;
>
>                 a2->p = a1;
>                 a1->p = a2p_o;
>
>                 if ( a2p != NULL ) {
>                         a2p->n = a1;
>                 }
>
>                 if ( a1n != NULL ) {
>                         a1n->p = a2;
>                 }
>         } else {
>                 // ...->[ a1 ]->...->[ a2 ]->...
>                 if ( a2p != NULL ) {
>                         a2p->n = NULL;
>                 }
>
>                 if ( a1n != NULL ) {
>                         a1n->p = NULL;
>                 }
>
>                 if ( a1p != NULL ) {
>                         a1p->n = a2;
>                 }
>
>                 if ( a2n != NULL ) {
>                         a2n->p = a1;
>                 }
>
>                 if ( a2p != NULL ) {
>                         a2p->n = a1;
>                 }
>
>                 if ( a1n != NULL ) {
>                         a1n->p = a2;
>                 }
>
>                 a1->n = NULL;
>                 a2->n = a1n_o;
>                 a1->n = a2n_o;
>
>                 a2->p = NULL;
>                 a1->p = a2p_o;
>                 a2->p = a1p_o;
>         }
>
> }
>
> The question is - how to correctly test effectiveness
> of such implementation to optimize it?
> May be some kind of visualisation to make possible to reduce
> quantity of steps or something?

If you swap the head of the list with another node,
then it might be simpler to return the address of the new head.

list = swap(list, list -> next);
l_print(list);
list = swap(list -> next, list);
l_print(list);
vs.
swap(list -> next, list -> next -> next);
l_print(list);

struct node *swap(struct node *a1, struct node *a2)
{
struct node *temp;

temp = a1 -> next;
a1 -> next = a2 -> next;
a2 -> next = temp;
if (a1 -> next != NULL) {
a1 -> next -> prev = a1;
}
if (a2 -> next != NULL) {
a2 -> next -> prev = a2;
}
temp = a1 -> prev;
a1 -> prev = a2 -> prev;
a2 -> prev = temp;
if (a1 -> prev != NULL) {
a1 -> prev -> next = a1;
}
if (a2 -> prev != NULL) {
a2 -> prev -> next = a2;
return a1;
} else {
return a2;
}
}

I modified the program in the below refered to post, to test it.

--
pete
```
 0
Reply pfiland (6614) 11/4/2004 2:17:53 PM

```Giorgos Keramidas <keramida@ceid.upatras.gr> wrote in message news:<20041104152619.T6871@orion>...

> The constraint of keeping the references NULL or unique during the swap is
> something you cannot guarantee by reordering the assignments of the pointers.
> Some sort of locking must be used, which is machine-dependent and cannot be
> described portably here (i.e. a mutex that protects the entire list, while
> reordering operations happen).

I've omited this in my previous post. Of course I'm using mutex'es for
locking.

>
> One trick that you can use to effectively 'swap' two elements of a list is to
> decouple the list linkage from the element data, using something like this:
>
> [ cut ]
>
> static void
> swapnodes(struct node *na, struct node *nb)
> {
>          struct nodeinfo *tmp;
>
>          assert(na != NULL && nb != NULL);
>          tmp = na->n_info;
>          na->n_info = nb->n_info;
>          nb->n_info = tmp;
> }

Good solution. But what should we do when
we have more then one information field ( e.g. 20 )?

> [ cut ]
> Your logic seems fine, and teh way you does swapped those nodes make sense,
> but the names are so confusing that it took me the better part of 15 minutes
> of careful reading *WITH* a notebook by my side to find out what's going on!
>
> IMHO C source shouldn't be so complex, unless there's a very good reason.

You right. My fault.

>
> > The question is - how to correctly test effectiveness of such implementation
> > to optimize it? May be some kind of visualisation to make possible to reduce
> > quantity of steps or something?
>
> Sure, drawing on a whiteboard, a piece of paper or something, is certainly
> going to help a lot.

I've tried a lot but found nothing except simply draw double linked list schemas
and move links between elements on it. ;-)

>
> - Giorgos
```
 0
Reply esobchenko (4) 11/5/2004 7:25:49 AM

```> Just swap the data instead of all the pointers:
>
> void swap ( struct node *a1, struct node *a2 ) {
>    int temp;
>    temp = a1->i;
>    a1->i = a2->i;
>    a2->i = temp;
> }
>

Good. But what should I do when I have tens of informational
fields?
```
 0
Reply esobchenko (4) 11/5/2004 7:27:33 AM

```> If you swap the head of the list with another node,
> then it might be simpler to return the address of the new head.
>
>     list = swap(list, list -> next);
>     l_print(list);
>     list = swap(list -> next, list);
>     l_print(list);
> vs.
>     swap(list -> next, list -> next -> next);
>     l_print(list);
>
>
> struct node *swap(struct node *a1, struct node *a2)
> {
>     struct node *temp;
>
>     temp = a1 -> next;
>     a1 -> next = a2 -> next;
>     a2 -> next = temp;
>     if (a1 -> next != NULL) {
>         a1 -> next -> prev = a1;
>     }
>     if (a2 -> next != NULL) {
>         a2 -> next -> prev = a2;
>     }
>     temp = a1 -> prev;
>     a1 -> prev = a2 -> prev;
>     a2 -> prev = temp;
>     if (a1 -> prev != NULL) {
>         a1 -> prev -> next = a1;
>     }
>     if (a2 -> prev != NULL) {
>         a2 -> prev -> next = a2;
>         return a1;
>     } else {
>      return a2;
>     }
> }
>
> I modified the program in the below refered to post, to test it.

Thanks. But I'm swapping two arbitrary elements of very long
double linked list. This one seems to be very slow for me. ;-(
```
 0
Reply esobchenko (4) 11/5/2004 7:36:37 AM

```esobchenko@gmail.com (Eugen J. Sobchenko) writes:
> Giorgos Keramidas <keramida@ceid.upatras.gr> wrote
> in message news:<20041104152619.T6871@orion>...
> >
> > static void
> > swapnodes(struct node *na, struct node *nb)
> > {
> >          struct nodeinfo *tmp;
> >
> >          assert(na != NULL && nb != NULL);
> >          tmp = na->n_info;
> >          na->n_info = nb->n_info;
> >          nb->n_info = tmp;
> > }
>
> Good solution. But what should we do when
> we have more then one information field ( e.g. 20 )?

You can use structure assignment with a temporary struct, instead of a
pointer, which can waste a bit of space on the stack of the program for
the allocation of an automatic struct.

You can redesign the structures, so that n_info is the *only*
information a node struct keeps, and make sure all the fields you
consider 'attributes' of the node are fields of nodeinfo.

```
 0
Reply keramida (465) 11/5/2004 8:04:22 AM

```"Eugen J. Sobchenko" <esobchenko@gmail.com> wrote in message
> > Just swap the data instead of all the pointers:
> >
> > void swap ( struct node *a1, struct node *a2 ) {
> >    int temp;
> >    temp = a1->i;
> >    a1->i = a2->i;
> >    a2->i = temp;
> > }
> >
>
> Good. But what should I do when I have tens of informational
> fields?

Then I would question the design. You can allocate a struct to encapsulate
all your data, and then just swap those struct pointers. For example:

struct data {
/* your fields of data */
}

struct node {
struct data* i;
struct node* p;
struct node* n;
}

void swap ( struct node *a1, struct node *a2 ) {
struct data* temp;
temp = a1->i;
a1->i = a2->i;
a2->i = temp;
}

```
 0

```Eugen J. Sobchenko wrote:
>
> > If you swap the head of the list with another node,
> > then it might be simpler to return the address of the new head.
> >
> >     list = swap(list, list -> next);
> >     l_print(list);
> >     list = swap(list -> next, list);
> >     l_print(list);
> > vs.
> >     swap(list -> next, list -> next -> next);
> >     l_print(list);
> >
> >
> > struct node *swap(struct node *a1, struct node *a2)
> > {
> >     struct node *temp;
> >
> >     temp = a1 -> next;
> >     a1 -> next = a2 -> next;
> >     a2 -> next = temp;
> >     if (a1 -> next != NULL) {
> >         a1 -> next -> prev = a1;
> >     }
> >     if (a2 -> next != NULL) {
> >         a2 -> next -> prev = a2;
> >     }
> >     temp = a1 -> prev;
> >     a1 -> prev = a2 -> prev;
> >     a2 -> prev = temp;
> >     if (a1 -> prev != NULL) {
> >         a1 -> prev -> next = a1;
> >     }
> >     if (a2 -> prev != NULL) {
> >         a2 -> prev -> next = a2;
> >         return a1;
> >     } else {
> >      return a2;
> >     }
> > }
> >
> > I modified the program in the below refered to post, to test it.
>
> Thanks. But I'm swapping two arbitrary elements of very long
> double linked list. This one seems to be very slow for me. ;-(

I don't understand what you mean.
What's too slow?

--
pete
```
 0
Reply pfiland (6614) 11/5/2004 10:44:33 AM

```pete wrote:
>
> Eugen J. Sobchenko wrote:

> > > struct node *swap(struct node *a1, struct node *a2)

> > Thanks. But I'm swapping two arbitrary elements of very long
> > double linked list. This one seems to be very slow for me. ;-(

This is what the job comes down to:
1   swap the values of the prev pointers in a1 and a2
2   swap the values of the next pointers in a1 and a2
3   change a1 -> prev -> next, to a1
4   change a1 -> next -> prev, to a1
5   change a2 -> prev -> next, to a2
6   change a2 -> next -> prev, to a2

Obviously if any of the a->prev or a->next pointers are NULL
then some of steps 3 through 6 must be omitted.

If the head of the list is swapped,
then you need to accommodate that somehow.

Unless you just want to swap your int type data
swapping double linked nodes doesn't get any simpler than that.

--
pete
```
 0
Reply pfiland (6614) 11/5/2004 12:14:48 PM

```"Eugen J. Sobchenko" wrote:
>
.... snip ...
>
> Thanks. But I'm swapping two arbitrary elements of very long
> double linked list. This one seems to be very slow for me. ;-(

I think you are all missing a critical point.  We can all see very
easily how to swap pointers when the nodes are in the middle of the
list, the complications come about when one or both of the swapees
are at the ends.

So you just eliminate the ends, and use a dummy node both for list
access and to signal the list ends.  From that node you can either
go forward to the list beginning, or backward to the list end, and
its value is known and can be detected by testing equality of
pointers (which is always possible).

So you work with something like:

struct node {
struct node *next;
struct node *prev;
somedata_t   thedata;
}
....
struct node listroot;
#define nil &listroot
....
nil->next = nil; nil->prev = nil;
.... build the list ....

now nil.next and nil.prev will always point to the head and tail of
the list.  root is not dynamically assigned storage (i.e. not
malloc'd).  Now the swapping of nodes is always the same, as long
as the swapee itself is not nil.  The swapping code doesn't have to
know about nil or NULL.  However list walkers have to know where
the root lies, to detect list ends by a pointer to root (i.e. nil).

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.

```
 0
Reply cbfalconer (19194) 11/5/2004 2:24:03 PM

12 Replies
52 Views

Similar Articles

12/18/2013 11:26:42 PM
[PageSpeed]

Similar Artilces:

I have a double-linked list. I need to know if it is possible to remove just one of an item, instead of all that match the given criteria with the remove() command. Any thoughts? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] deanfamily wrote: > I have a double-linked list. I need to know if it is possible to remove just > one of an item, instead of all that match the given criteria with the > remove() command. Any thoughts? cont.erase(find_if(cont.begin(), cont.end(), your_predicate_ftor...

I am re-posting my second problem. I have a double-linked list. I need to know if it is possible to remove just one of an item, instead of all that match the given criteria with the remove() command. Any thoughts? deanfamily wrote: > I am re-posting my second problem. > > I have a double-linked list. Assuming you mean std::list (in context with the remaining part of the message where you talk about remove() ) - >I need to know if it is possible to remove just > one of an item, instead of all that match the given criteria with the > remove() command. Any thoughts? No...

Does anyone know where I could take a look on an implementation of a double linked list in ada? thanks kara wrote: > Does anyone know where I could take a look on an implementation of a double > linked list in ada? > > thanks > > You can visit my webiste at http://adrianhoe.com -- Adrian Hoe m a i l b o x AT a d r i a n h o e . c o m kara wrote: > Does anyone know where I could take a look on an implementation of a > double linked list in ada? The PragmAda Reusable Components contain implementations of both bounded and unbounded doubly linked lists. http:/...

Could someone help me get started on this program or where to look to get information, I am not sure how to put things together. 1=2E Create 4 double linked lists as follows: (a) A double linked list called NAMES which will contain all C like identifiers of less than 256 characters long identified in the input file F. Each identifier will be represented by a triple (I, length, string) where I is used to identify the type of the object as being an identifier, length is an integer representing the length of the identifier in characters, and string is a string of characters representing the ide...

Hello everyone. I have a problem with my program... and i kinda dunno what to do.. everything seems to work ok, but i'm getting corrupted double-linked list error =\. *** glibc detected *** corrupted double-linked list: 0x080aff40 *** Program received signal SIGABRT, Aborted. 0xaf7037b2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2 (gdb) bt #0 0xaf7037b2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2 #1 0xaf5b4f41 in raise () from /lib/tls/libc.so.6 #2 0xaf5b66e7 in abort () from /lib/tls/libc.so.6 #3 0xaf5e857e in __fsetlocking () from /lib/tls/libc.so.6 #4 0xaf5f2297 in mallop...

pointers to elements in a Linked-List?
I have a Linked-List and would like to create pointers to elements in this list. e.g I would like two pointers that point to each of their elements in the Linked-List. But there should always be exactly 5 nodes between these pointers. Does this make any sense or are there some more efficient way to access certain elements in a Linked-List? Paminu wrote On 10/12/05 15:26,: > I have a Linked-List and would like to create pointers to elements in this > list. > > e.g I would like two pointers that point to each of their elements in the > Linked-List. But there should alway...

deleting an element from the linked list
Hi.. really I need some help... I trying to delet an element from a linked list, where the head of this list is inside of an array of pointers... the big problem, is because when i am deleting the current element I verify that the element was really deleted, but if I access the head of the list and considering that for this case I have just one element the head of the list ISN'T empty... why is it happening???? here is some parts of my subroutine, perhaps someone can help me... Subroutine flagbadtop Implicit None Type listI Integer::ii0,ii1 Type(listI), Pointer :: nexti End Typ...