Print linked list backwards

[joshc]

In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.

I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn't provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?

Thanks,

Josh

[Ben Bacarisse]

"joshc" <jo********@gmail.comwrites:

In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.

I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn't provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?

The only thing that springs to mind is to build a new one, "pushing"
items onto it as the original list is traversed. You can then print
the new one, or print it as you de-allocate it if you won't need it
again.

Of course, this is essentially the recursive solution -- the new list
playing the role of the call stack -- so it may also be frowned on in
embedded systems.

BTW, may I suggest comp.programming rather than c.l.c -- you will get
wider experience there and your question is really an algorithm one?

--
Ben. } ((C, "yoda")invented) if

[CBFalconer]

joshc wrote:

>
In an interview for an embedded software position recently I was
asked to write code, in C, for printing the contents of a linked
list backwards. After a few minutes I came up with the recursive
solution. Being that recursion is frowned upon in embedded
software, the answer was not what the interviewer expected, but
alas it was correct. I asked some friends how they would have
answered and another answer is to reverse the list and then print
the contents as you reverse the list a second time.

I was searching for any other possible solutions and it seems
these 2 are the most common solutions. However, someone mentioned
that if there is a constraint that the list is unmodifiable, there
is another solution but didn't provide that solution. Can anyone
provide a solution besides the 2 I mentioned, especially one that
would work without modifying the list?

This might eat up a lot of stack space (on stack systems) for a
long list, but it should work (untested)

#include <stdio.h>

struct node {
struct node *next;
char *data;
};

void revprint(struct node *root) {

if (root->next) revprint(root->next);
puts(root->data);
}

int main(void) {

struct node *root;

root = makelist(whatever); /* code to taste */

revprint(root);
return 0;
}

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[Sourcerer]

"joshc" <jo********@gmail.comwrote in message
news:11**********************@n67g2000cwd.googlegr oups.com...

In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.

I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn't provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?

Thanks,

Josh

I believe the only reason the interviewer did not like your solution is because
you have made the problem O(n) in both temporal and spatial complexity. Thus,
the best solution given was by your friends. It remains O(n) in temporal, but it
is O(1) in spatial complexity.

Basically, there IS another way to solve the problem if you must not modify the
list, and that is by building the new list. However, if you build the new list
as you iterate through the given one, it is questionable if such a solution
would be accepted, because it also uses up memory - not on stack, but on heap.
So, while it doesn't fill the stack up in proportion to the length of the list,
it fills the heap - and both are memory consuming.

Less memory-consuming solution, but still proportional to the length of the
list, is if you only save memory addresses of the structures while iterating
through the list, rather than building a second list. You would need a new
structure for that, as you do not know how many elements the first list has, but
it could be considerably smaller (only 8 bytes per structure, for you would need
a pointer to the structure elements you need to print out, and the second
pointer which would point to the previous element in this new list). You could
also make an array sized say 80 bytes, and each time you fill it out, you do a
realloc on it and make it 80 bytes larger. This could, however, significantly
slow down the program if the original list is large.

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

[Sourcerer]

"CBFalconer" <cb********@yahoo.comwrote in message
news:45***************@yahoo.com...

>
This might eat up a lot of stack space (on stack systems) for a
long list, but it should work (untested)

#include <stdio.h>

struct node {
struct node *next;
char *data;
};

void revprint(struct node *root) {

if (root->next) revprint(root->next);
puts(root->data);
}

int main(void) {

struct node *root;

root = makelist(whatever); /* code to taste */

revprint(root);
return 0;
}

This is the recursive solution. He said this didn't pass by the interviewer. :)

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

[Ben Pfaff]

"joshc" <jo********@gmail.comwrites:

In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.

I was searching for any other possible solutions and it seems these 2
are the most common solutions.

The best solution is to design the data structure correctly from
the beginning. A data structure that needs to be traversed in
two directions should have pointers that go in both directions.
So: use a doubly linked list instead.
--
"Given that computing power increases exponentially with time,
algorithms with exponential or better O-notations
are actually linear with a large constant."
--Mike Lee

[Sourcerer]

"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...

>
The best solution is to design the data structure correctly from
the beginning. A data structure that needs to be traversed in
two directions should have pointers that go in both directions.
So: use a doubly linked list instead.

That's not a solution to the current problem. This problem involves a singly
linked list. Besides, who says that a doubly linked list is more correct than an
ordinary linked list?

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

[Ben Pfaff]

"Sourcerer" <en****@MAKNIgmail.comwrites:

"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...

>>
The best solution is to design the data structure correctly from
the beginning. A data structure that needs to be traversed in
two directions should have pointers that go in both directions.
So: use a doubly linked list instead.

That's not a solution to the current problem. This problem involves a
singly linked list.

It's a question about software design. I gave a software design
answer.

There's more to life than homework problems.

Besides, who says that a doubly linked list is more correct
than an ordinary linked list?

Whoever decided that it needed to be traversed in both
directions.
--
"In My Egotistical Opinion, most people's C programs should be indented six
feet downward and covered with dirt." -- Blair P. Houghton

[joshc]

Ben Bacarisse wrote:

"joshc" <jo********@gmail.comwrites:

In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.

I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn't provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?

The only thing that springs to mind is to build a new one, "pushing"
items onto it as the original list is traversed. You can then print
the new one, or print it as you de-allocate it if you won't need it
again.

Of course, this is essentially the recursive solution -- the new list
playing the role of the call stack -- so it may also be frowned on in
embedded systems.

BTW, may I suggest comp.programming rather than c.l.c -- you will get
wider experience there and your question is really an algorithm one?

--
Ben. } ((C, "yoda")invented) if

Yes, I thought about posting this to comp.programming since that is
where I found a majority of threads on this topic. However, I figured I
wanted a "standard C" solution so I'd try here first. I didn't mention
stack, etc. in my original question because I wanted to keep this about
the C language and not particular to an implementation. I'm just
seeking solutions that don't modify the original list however
efficient/inefficent they may end up being.

[joshc]

Ben Pfaff wrote:

"Sourcerer" <en****@MAKNIgmail.comwrites:

"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...

>
The best solution is to design the data structure correctly from
the beginning. A data structure that needs to be traversed in
two directions should have pointers that go in both directions.
So: use a doubly linked list instead.

That's not a solution to the current problem. This problem involves a
singly linked list.

It's a question about software design. I gave a software design
answer.

There's more to life than homework problems.

It was an interview question; I'd love to see you give the above answer
during an interview.

[Keith Thompson]

"Sourcerer" <en****@MAKNIgmail.comwrites:

"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...

>>
The best solution is to design the data structure correctly from
the beginning. A data structure that needs to be traversed in
two directions should have pointers that go in both directions.
So: use a doubly linked list instead.

That's not a solution to the current problem. This problem involves a
singly linked list.

Perhaps, but in the real world, actual requirements hardly ever
include terms like "singly linked list". Real-world requirements tend
to be things like "Do such-and-such within these specified time and
space contraints." Why should the person setting the requirements
care whether you use a singly linked list, an array, or a hash table?

Homework problems can be a different matter, though; the actual goal
of a homework assignment might be to learn how to use singly linked
lists.

Besides, who says that a doubly linked list is
more correct than an ordinary linked list?

It lets you easily traverse it in either direction. If that's what
you need to do, and if the overhead of one extra pointer per node is
acceptable, then a doubly linked list is just the thing.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

"Sourcerer" <en****@MAKNIgmail.comwrites:
[...]

I believe the only reason the interviewer did not like your solution
is because you have made the problem O(n) in both temporal and spatial
complexity. Thus, the best solution given was by your friends. It
remains O(n) in temporal, but it is O(1) in spatial complexity.

Basically, there IS another way to solve the problem if you must not
modify the list, and that is by building the new list. However, if you
build the new list as you iterate through the given one, it is
questionable if such a solution would be accepted, because it also
uses up memory - not on stack, but on heap. So, while it doesn't fill
the stack up in proportion to the length of the list, it fills the
heap - and both are memory consuming.

Less memory-consuming solution, but still proportional to the length
of the list, is if you only save memory addresses of the structures
while iterating through the list, rather than building a second
list. You would need a new structure for that, as you do not know how
many elements the first list has, but it could be considerably smaller
(only 8 bytes per structure, for you would need a pointer to the
structure elements you need to print out, and the second pointer which
would point to the previous element in this new list). You could also
make an array sized say 80 bytes, and each time you fill it out, you
do a realloc on it and make it 80 bytes larger. This could, however,
significantly slow down the program if the original list is large.

You're assuming that pointer are 4 bytes. That's not always the case.

Here's another approach. Traverse the list once to determine the
number of elements. (You can avoid this step by keeping track of the
length as you build the list.) Allocate an array of pointers, using
malloc() (or perhaps a VLA if your compiler supports it). Traverse
the list a second time, assigning the address of each node into the
appropriate element of the array. You can now traverse the array in
any order you like.

You *could* avoid the first traversal by using realloc() to expand the
array as needed, but that's likely to be much more expensive than just
traversing the list to count the elements.

By building an array, you're likely to save at least 50% of the memory
requirement -- and the allocated memory is in one contiguous chunk.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Ian Collins]

Keith Thompson wrote:

"Sourcerer" <en****@MAKNIgmail.comwrites:

>>
Besides, who says that a doubly linked list is
more correct than an ordinary linked list?

It lets you easily traverse it in either direction. If that's what
you need to do, and if the overhead of one extra pointer per node is
acceptable, then a doubly linked list is just the thing.

More so when other solutions to the problem require at least one extra
pointer per element to build another list, or call stack for a recursive
solution.

--
Ian Collins.

[Ben Pfaff]

"joshc" <jo********@gmail.comwrites:

Ben Pfaff wrote:

>"Sourcerer" <en****@MAKNIgmail.comwrites:

"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...

The best solution is to design the data structure correctly from
the beginning. A data structure that needs to be traversed in
two directions should have pointers that go in both directions.
So: use a doubly linked list instead.

That's not a solution to the current problem. This problem involves a
singly linked list.

It's a question about software design. I gave a software design
answer.

There's more to life than homework problems.

It was an interview question; I'd love to see you give the above answer
during an interview.

I'd have no problem giving it during an interview. I'd say,
"Well, the 'obvious' solution is to change the linked list to be
doubly linked. Usually a doubly linked list is a better choice
anyway, because they make many operations easier or more
efficient. However, if the memory for the second link is too
expensive, or if there's some other kind of constraint, we can
solve it these other ways too..."

You need to have some flexibility.
--
"C has its problems, but a language designed from scratch would have some too,
and we know C's problems."
--Bjarne Stroustrup

[Chris Torek]

>>"Ben Pfaff" <bl*@cs.stanford.eduwrote in message

>>news:87************@blp.benpfaff.org...
The best solution is to design the data structure correctly from
the beginning. A data structure that needs to be traversed in
two directions should have pointers that go in both directions.
So: use a doubly linked list instead.

Indeed (or some other equivalent more-suitable structure).

>"Sourcerer" <en****@MAKNIgmail.comwrites:

>>That's not a solution to the current problem. This problem involves a
singly linked list.

>Ben Pfaff wrote:

>It's a question about software design. I gave a software design
answer.

There's more to life than homework problems.

In article <11*********************@80g2000cwy.googlegroups.c om>
joshc <jo********@gmail.comwrote:

>It was an interview question; I'd love to see you give the above answer
during an interview.

I am not exactly a fan of "interview questions" (which tend to
have "interview answers" instead of *good* answers), but in such
a situation I would suggest a number of possibilities, from
"fix the software design" to "throw memory at the problem" (use
recursion or a second list) to "throw CPU time at the problem".
The last one:

/* beware, O(n**2) runtime where n = list_length(head) */
void list_print_reverse_very_slowly(struct list *head) {
size_t len = list_length(head);
size_t i;

for (i = 0; i < len; i++) {
list_print_item(list_ith(head, i));
}
}

where list_length is the obvious:

size_t list_length(struct list *head) {
size_t len;

for (len = 0; head; head = head->next)
len++;
return len;
}

and list_ith is the equally obvious:

struct list *list_ith(struct list *head, size_t i) {
struct list *p;

for (p = head; /* optional: p != NULL && */ i 0; i--)
p = p->next;
return p;
}

and of course list_print_item is whatever it takes to print
one list element.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Chris Torek]

In article <el********@news1.newsguy.comI wrote, in part:

/* beware, O(n**2) runtime where n = list_length(head) */
void list_print_reverse_very_slowly(struct list *head) {
size_t len = list_length(head);
size_t i;

for (i = 0; i < len; i++) {
list_print_item(list_ith(head, i));
}

Oops, this is of course supposed to count i down:

for (i = len; i-- != 0;)
list_print_item(list_ith(head, i));

(or, equivalently, change the argument to list_ith).

The technique should be clear enough. The effect is to treat the
list as if it were an array, which gives random access.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Stephen Sprunk]

"Ian Collins" <ia******@hotmail.comwrote in message
news:4u*************@mid.individual.net...

Keith Thompson wrote:

>"Sourcerer" <en****@MAKNIgmail.comwrites:

>> Besides, who says that a doubly linked list is
more correct than an ordinary linked list?

It lets you easily traverse it in either direction. If that's what
you need to do, and if the overhead of one extra pointer per node is
acceptable, then a doubly linked list is just the thing.

More so when other solutions to the problem require at least one extra
pointer per element to build another list, or call stack for a
recursive
solution.

OTOH, switching to a doubly-linked list involves a runtime cost and
maintenance cost for every other bit of code which touches that list.
If this were the _only_ place where one needed to traverse it backwards,
using a doubly-linked list may not be the best answer overall.

The recursive solution is cleanest code-wise, but an embedded system may
not have the stack space sufficient to deal with arbitrary-length lists,
i.e. the call depth often has a very low limit. Likewise, the solution
that requires reversing the list (or any other type of modification) may
be suboptimal because there's other threads using the list, which is
possible if it's protected with a reader lock (or, say, RCU); getting a
writer lock may block those threads and violate real-time performance
targets. Building an array of pointers or a second reversed list
requires additional memory, but it's at least proportional to what's
already being used (and probably smaller) so it's probably safe.

It's all trade-offs, though; the "correct" answer will vary. When I ask
these types of questions, it's never to see what answer the person comes
up with -- it's to see how they go about finding the solution and what
questions they ask along the way. Watching someone work is often far
more enlightening than just reviewing the results when they're done.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking
--
Posted via a free Usenet account from http://www.teranews.com

[Sourcerer]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

>
You're assuming that pointer are 4 bytes. That's not always the case.

Yes, that is my default assumption, because this is the most common in my
experience. I'm not trying to be infinitely accurate.

Here's another approach. Traverse the list once to determine the
number of elements. (You can avoid this step by keeping track of the
length as you build the list.) Allocate an array of pointers, using
malloc() (or perhaps a VLA if your compiler supports it). Traverse
the list a second time, assigning the address of each node into the
appropriate element of the array. You can now traverse the array in
any order you like.

You *could* avoid the first traversal by using realloc() to expand the
array as needed, but that's likely to be much more expensive than just
traversing the list to count the elements.

By building an array, you're likely to save at least 50% of the memory
requirement -- and the allocated memory is in one contiguous chunk.

True, you save memory and it can be faster than realloc(), but still memory
consumption remains proportional to the length of the list. But these are the
only options - either modify the list, or consume memory. So, which will it be
is purely an engineering decision - weigh the alternatives and choose the best
one.

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

[CBFalconer]

Sourcerer wrote:

"Keith Thompson" <ks***@mib.orgwrote in message

>You're assuming that pointer are 4 bytes. That's not always the
case.

Yes, that is my default assumption, because this is the most common
in my experience. I'm not trying to be infinitely accurate.

>Here's another approach. Traverse the list once to determine the
number of elements. (You can avoid this step by keeping track of
the length as you build the list.) Allocate an array of pointers,
using malloc() (or perhaps a VLA if your compiler supports it).
Traverse the list a second time, assigning the address of each
node into the appropriate element of the array. You can now
traverse the array in any order you like.

You *could* avoid the first traversal by using realloc() to expand
the array as needed, but that's likely to be much more expensive
than just traversing the list to count the elements.

By building an array, you're likely to save at least 50% of the
memory requirement -- and the allocated memory is in one
contiguous chunk.

True, you save memory and it can be faster than realloc(), but still
memory consumption remains proportional to the length of the list.
But these are the only options - either modify the list, or consume
memory. So, which will it be is purely an engineering decision -
weigh the alternatives and choose the best one.

A further option is to define the list nodes with a spare pointer,
such as:

struct node {
struct node *next, *xtrap;
char *data;
}

Now build and manipulate the list as you wish, ignoring xtrap. To
reverse the list in place, without disturbing anything, walk the
list, setting xtrap as you wish. This can do the reversal with the
efficient iterative method. Whenever you wish you can sort the
list using xtrap. Etc. The only thing you have to handle as an
indivisible whole is the operations on xtrap. You can also
instantaneously convert the list into a doubly linked list
(actually the reversal operation) whenever you wish.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[Barry]

"Sourcerer" <en****@MAKNIgmail.comwrote in message
news:el**********@ss408.t-com.hr...

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

You're assuming that pointer are 4 bytes. That's not always the case.

Yes, that is my default assumption, because this is the most common in my
experience. I'm not trying to be infinitely accurate.

Here's another approach. Traverse the list once to determine the
number of elements. (You can avoid this step by keeping track of the
length as you build the list.) Allocate an array of pointers, using
malloc() (or perhaps a VLA if your compiler supports it). Traverse
the list a second time, assigning the address of each node into the
appropriate element of the array. You can now traverse the array in
any order you like.

You *could* avoid the first traversal by using realloc() to expand the
array as needed, but that's likely to be much more expensive than just
traversing the list to count the elements.

By building an array, you're likely to save at least 50% of the memory
requirement -- and the allocated memory is in one contiguous chunk.

True, you save memory and it can be faster than realloc(), but still

memory

consumption remains proportional to the length of the list. But these are

the

only options - either modify the list, or consume memory. So, which will

it be

is purely an engineering decision - weigh the alternatives and choose the

best

one.

These are the NOT the only options based upon the OPs original post which
didn't say anything about O(n). Obviously there is a trivial n-squared
solution.

--
"It is easy in the world to live after the world's oppinion; it easy in

solitude

to live after our own; but the great man is he who in the midst of the

crowd

keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

[Keith Thompson]

"Sourcerer" <en****@MAKNIgmail.comwrites:

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

>>
You're assuming that pointer are 4 bytes. That's not always the case.

Yes, that is my default assumption, because this is the most common in
my experience. I'm not trying to be infinitely accurate.

There's no need to be "infinitely accurate". Just acknowledge the
assumption. For example, something like "This requires 8 bytes per
node (assuming 4-byte pointers)" is perfectly fine.

[...]

True, you save memory and it can be faster than realloc(), but still
memory consumption remains proportional to the length of the list. But
these are the only options - either modify the list, or consume
memory. So, which will it be is purely an engineering decision - weigh
the alternatives and choose the best one.

As it turns out, those aren't the only options. Chris Torek posted a
solution that neither modifies the list nor allocates O(n) memory --
but it requires O(n**2) time. (I think you could speed up Chris's
method by a constant factor by allocating a fixed-size array of
pointers, reversing the list in chunks rather than one element at a
time.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Sourcerer]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

>
As it turns out, those aren't the only options. Chris Torek posted a
solution that neither modifies the list nor allocates O(n) memory --
but it requires O(n**2) time. (I think you could speed up Chris's
method by a constant factor by allocating a fixed-size array of
pointers, reversing the list in chunks rather than one element at a
time.)

Yes, sorry. I forgot about it.

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

[Richard Harter]

On 9 Dec 2006 14:32:43 -0800, "joshc" <jo********@gmail.comwrote:

>In an interview for an embedded software position recently I was asked
to write code, in C, for printing the contents of a linked list
backwards. After a few minutes I came up with the recursive solution.
Being that recursion is frowned upon in embedded software, the answer
was not what the interviewer expected, but alas it was correct. I asked
some friends how they would have answered and another answer is to
reverse the list and then print the contents as you reverse the list a
second time.

I was searching for any other possible solutions and it seems these 2
are the most common solutions. However, someone mentioned that if there
is a constraint that the list is unmodifiable, there is another
solution but didn't provide that solution. Can anyone provide a
solution besides the 2 I mentioned, especially one that would work
without modifying the list?

A third solution, which no one seems to have mentioned, is to partition
the list. You can use the double pointer technique to find the midpoint
of the list. Process the last half recursively, then the first half.
The time cost is O(n*log n) and the space cost is O(log n). This gives
us three classes of solution:

Walk to last then to next last etc: time O(n*n), space O(1)
Partition the list: time O(n*log n), space O(log n)
Reverse copy the list: time O(n), space O(n)

Which to choose depends on circumstances.

Considered as an interview question, a "good" answer is to give all
three solutions, and explain the tradeoffs. Just answering with
whatever occurs to you first is not quite as good. Part of good
software design is knowing what your options are.

Followups set to comp.programming.