Lawrence Kirby <lk****@netactive.co.uk>:
On Tue, 06 Sep 2005 10:51:42 -0700, Ed Prochak wrote: The algorithm is so trivial.
valueholder = nodeA.value
nodeA.value = nodeB.value
nodeB.value = valueholder
Which of course may fail if there are other pointers to nodeA or
nodeB in the system. Even if there aren't any now there might be
in the future.
if the "value" portion of the node is too complex to handle
this way (maybe it is many fields), then you swap link
pointers but the method is the same. And totally independent
of C programming.
That would be the usual method, the nice thing about a doubly
linked list is that all the pointers you have to change at
easily accessible. Although the method is easy it isn't trivial.
There are a number of pointers to update and you have to
consider cases where forwards and backwards links are null. It
is easy to get wrong.
I would try swapping node A and node B this way:
In order to leave the structure of the list unchanged, I suggest
to not simply remove the nodes A and B from the list and reinsert
them afterwards but to use a temporary node Temp:
1) replace node A with node Temp
2) replace node B with node A
3) replace node Temp with node B
Note: If A and B are elements not of the same but of distinct
lists listA and listB respectively, then afterwards A will be in
listB where B was and vice versa.
Replacing a node C with a node D can be done by
1) inserting node D after node C
2) removing node C from the list.
This approach has the advantage that it works even if node C is
the only element of the list, regardless, whether the list is a
ring list or has a head and a tail.
C code (untested):
#include <stdlib.h> /* NULL, EXIT_SUCCESS */
#include <stdio.h> /* printf() */
struct link
{
struct link * prev, * next;
};
void insertAfter(struct link * where, struct link * what)
/* Note: *what need not be initialized but may not be part of
* any list, because that list would be corrupted.
*/
{
struct link * succ = where->next;
/* Note: If *where is the last link in the list, then
* where->next == NULL.
*/
/* Update next and prev pointers in *what:
* After the insertion *succ will be the successor of *what.
* After the insertion *where will be the predecessor of
* *what:
*/
what->next = succ;
what->prev = where;
/* Update both the next pointer in *where and the prev pointer
* in *succ to point to *what:
*/
where->next = what;
if (succ != NULL)
succ->prev = what;
}
void removeLink(struct link * what)
{
struct link * pred = what->prev; /* may be NULL or even what */
struct link * succ = what->next; /* may be NULL or even what */
if (pred != NULL) pred->next = succ;
if (succ != NULL) succ->prev = pred;
/* prevent next and prev ptr.s in *what from dangling around:
*/
what->next = NULL;
what->prev = NULL;
}
void replaceWith(struct link * what, struct link * substitute)
/* Note: *substitute need not be initialized but may not be
* part of any list, because that list would be corrupted.
*/
{
insertAfter(what, substitute);
removeLink(what);
}
void swap(struct link * a, struct link * b)
{
struct link temp;
/* .next and .prev need not be initialized, because
* replaceWith() does that already.
*/
replaceWith(a, &temp);
replaceWith(b, a);
replaceWith(&temp, b);
}
/* Example: Create a list of three strings and exchange the first
* and the third elements.
*/
struct stringListElem
{
struct link link; /* must be first component of this struct */
const char *data;
};
struct stringListElem * elemFromLink(const struct link * l)
{
/* This ptr type cast is legal if and only if l points to the
* .link of a struct stringListElem object and .link is the first
* component of struct stringListElem.
*/
return (struct stringListElem *)l;
}
int main(void)
{
struct stringListElem a, b, c;
a.data = "a";
b.data = "b";
c.data = "c";
{
struct link tempHandle = { NULL, NULL };
/* Initialize tempHandle to { &tempHandle, &tempHandle } if
* you want a ring list.
*/
/* Initialize a.link by inserting a.link in tempHandle's list
* and therewith expelling tempHandle from its own list. Thus,
* tempHandle may cease to exist afterwards.
*/
replaceWith(&tempHandle, &a.link);
}
insertAfter(&a.link, &b.link);
insertAfter(&b.link, &c.link);
printf("List is\n");
{
unsigned i; struct link *l;
for (i = 1, l = &a.link; i <= 3; i++, l = l.next)
printf("%u: %s\n", i, elemFromLink(l)->data);
}
printf("exchanging...\n");
swap(&a.link, &c.link);
printf("List is\n");
{
unsigned i; struct link *l;
for (i = 1, l = &c.link; i <= 3; i++, l = l.next)
printf("%u: %s\n", i, elemFromLink(l)->data);
}
/* remove the three elements from the list before their
* lifetime ends.
*/
removeLink(&a.link);
removeLink(&b.link);
removeLink(&c.link);
return EXIT_SUCCESS;
}
