448,805 Members | 1,645 Online Need help? Post your question and get tips & solutions from a community of 448,805 IT Pros & Developers. It's quick & easy.

 P: n/a 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! Nov 14 '05 #1
12 Replies

 P: n/a "Eugen J. Sobchenko" wrote in message news:b7**************************@posting.google.c om... 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; } Nov 14 '05 #2

 P: n/a 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. http://groups.google.com/groups?selm...mindspring.com -- pete Nov 14 '05 #5

 P: n/a Giorgos Keramidas 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 Nov 14 '05 #6

 P: n/a > 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? Nov 14 '05 #7

 P: n/a > 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. http://groups.google.com/groups?selm...mindspring.com Thanks. But I'm swapping two arbitrary elements of very long double linked list. This one seems to be very slow for me. ;-( Nov 14 '05 #8

 P: n/a es********@gmail.com (Eugen J. Sobchenko) writes: Giorgos Keramidas 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. Nov 14 '05 #9

 P: n/a "Eugen J. Sobchenko" wrote in message news:b7*************************@posting.google.co m... 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; } Nov 14 '05 #10

 P: n/a 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. http://groups.google.com/groups?selm...mindspring.com 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 Nov 14 '05 #11

 P: n/a 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 as shown in your example, swapping double linked nodes doesn't get any simpler than that. -- pete Nov 14 '05 #12

 P: n/a "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 (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 14 '05 #13

### This discussion thread is closed

Replies have been disabled for this discussion. 