Print linked list backwards

Discussion in 'C Programming' started by joshc, Dec 9, 2006.

  1. joshc

    joshc Guest

    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
    joshc, Dec 9, 2006
    #1
    1. Advertising

  2. "joshc" <> writes:

    > 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
    Ben Bacarisse, Dec 9, 2006
    #2
    1. Advertising

  3. joshc

    CBFalconer Guest

    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>
    CBFalconer, Dec 9, 2006
    #3
  4. joshc

    Sourcerer Guest

    "joshc" <> wrote in message
    news:...
    > 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, Dec 10, 2006
    #4
  5. joshc

    Sourcerer Guest

    "CBFalconer" <> wrote in message
    news:...
    >
    > 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/
    Sourcerer, Dec 10, 2006
    #5
  6. joshc

    Ben Pfaff Guest

    "joshc" <> writes:

    > 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
    Ben Pfaff, Dec 10, 2006
    #6
  7. joshc

    Sourcerer Guest

    "Ben Pfaff" <> wrote in message
    news:...
    >
    > 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/
    Sourcerer, Dec 10, 2006
    #7
  8. joshc

    Ben Pfaff Guest

    "Sourcerer" <> writes:

    > "Ben Pfaff" <> wrote in message
    > news:...
    >>
    >> 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
    Ben Pfaff, Dec 10, 2006
    #8
  9. joshc

    joshc Guest

    Ben Bacarisse wrote:
    > "joshc" <> writes:
    >
    > > 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, Dec 10, 2006
    #9
  10. joshc

    joshc Guest

    Ben Pfaff wrote:
    > "Sourcerer" <> writes:
    >
    > > "Ben Pfaff" <> wrote in message
    > > news:...
    > >>
    > >> 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.
    joshc, Dec 10, 2006
    #10
  11. "Sourcerer" <> writes:
    > "Ben Pfaff" <> wrote in message
    > news:...
    >>
    >> 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) <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, Dec 10, 2006
    #11
  12. "Sourcerer" <> writes:
    [...]
    > 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) <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, Dec 10, 2006
    #12
  13. joshc

    Chris Torek Guest

    >>> "Ben Pfaff" <> wrote in message
    >>> news:...
    >>>> 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" <> writes:
    >>> 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 <>
    joshc <> wrote:
    >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) +1 801 277 2603
    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, Dec 10, 2006
    #13
  14. joshc

    Ian Collins Guest

    Keith Thompson wrote:
    > "Sourcerer" <> writes:
    >>
    >> 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.
    Ian Collins, Dec 10, 2006
    #14
  15. joshc

    Ben Pfaff Guest

    "joshc" <> writes:

    > Ben Pfaff wrote:
    >> "Sourcerer" <> writes:
    >>
    >> > "Ben Pfaff" <> wrote in message
    >> > news:...
    >> >>
    >> >> 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
    Ben Pfaff, Dec 10, 2006
    #15
  16. joshc

    Chris Torek Guest

    In article <> I 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) +1 801 277 2603
    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, Dec 10, 2006
    #16
  17. "Ian Collins" <> wrote in message
    news:...
    > Keith Thompson wrote:
    >> "Sourcerer" <> writes:
    >>> 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
    Stephen Sprunk, Dec 10, 2006
    #17
  18. joshc

    Sourcerer Guest

    "Keith Thompson" <> wrote in message
    news:...
    >
    > 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/
    Sourcerer, Dec 10, 2006
    #18
  19. joshc

    CBFalconer Guest

    Sourcerer wrote:
    > "Keith Thompson" <> wrote 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>
    CBFalconer, Dec 10, 2006
    #19
  20. joshc

    Barry Guest

    "Sourcerer" <> wrote in message
    news:elgsnm$26t$-com.hr...
    > "Keith Thompson" <> wrote in message
    > news:...
    > >
    > > 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/
    >
    Barry, Dec 10, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    475
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    463
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    501
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    664
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    747
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page