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]

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?

 

[CBFalconer]

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

 

[Sourcerer]

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]

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]

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.

 

[Sourcerer]

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]

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.

 

[joshc]

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?

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]

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]

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]

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.

 

[Chris Torek]

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

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.

 

[Ian Collins]

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.

 

[Ben Pfaff]

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.

 

[Chris Torek]

/* 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.

 

[Stephen Sprunk]

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

 

[Sourcerer]

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]

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


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.

 

[Barry]

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


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.