Doubly Link List

[sudhirlko2001]

How to swap two nodes of doubly Linklist

 

[Jaspreet]

How to swap two nodes of doubly Linklist

Dont expect us to do your homework. Please tell us what you tried and
if you are stuck at some point we would be glad to help you out.

OR better still try searching for a 'college.homework' newsgroup.

 

[Michael Thomas Cassady]

Dont expect us to do your homework. Please tell us what you tried and
if you are stuck at some point we would be glad to help you out.

OR better still try searching for a 'college.homework' newsgroup.

Yeah try the problem first, at least.

 

[sudhirlko2001]

ya i tried it but i am unable to get proper algo for that .Sorry but
this not my assignment actually i asked this in a interview.

Thanks
Sudhir

 

[Ed Prochak]

ya i tried it but i am unable to get proper algo for that .Sorry but
this not my assignment actually i asked this in a interview.

Thanks
Sudhir

hopefully you did not get the job.

The algorithm is so trivial.
valueholder = nodeA.value
nodeA.value = nodeB.value
nodeB.value = valueholder

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.

Get a text book and study some fundamental algorithms.
Ed.

 

[Lawrence Kirby]

hopefully you did not get the job.

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.

Lawrence

 

[Ed Prochak]

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.

yes that does mess him up, but if he is at the level of job interviews,
he needs to think about such things himself. He should likely go back
to school. The fact he didn't even define the question clearly was one
reason why I even suggested that "solution".

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.

Lawrence

But it is so simple it usually isn't even included in fundamental
algorithms texts. Other than the terminal node case, there is nothing
really different, and in fact it is easier since you likely have at
least one pointer to one of the nodes (iow, the temp holder). How can
he hope to get a programming job an not know this?

Bottom line is, this might be a comp.programming question, but it
really has nothing to do with C programming.

Have a great day Lawrence.

ed

 

[Friedhelm Usenet Waitzmann]

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.

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;
}

 

[sudhirlko2001]

Thanks Friedhelm