singly link list backward

[sparsh610]

hello friends,
i have some problem with the concept of singly link list,,, don't know how to read it backward
pls help

[TrustyTony]

You do not read singly linked list backward, that is why it is called singly linked. You would basically need to build another singly linked list reversed while reading the list from front to back. The process would be same as not in place reversing the linked list function uses.

[Ancient Dragon]

linked lists that can be read backwards are called double liked lists because they have both a next and previous pointers. The previous pointer at the head is NULL so that you can detect the end of the list, and the next pointer at the tail is NULL for the same reason. Lists can also have no head or tail and are called circular linked lists.

[sparsh610]

if i m not wrong it means , i have to create a reverse link list and then read it , in order to read a link list in backward fashion

[Ancient Dragon]

If you need to read the list backwards then you need a double linked list not a single linked list. Either that or just simply insert each node in reverse order.

[Sokurenko]

Maybe it is stack ? you push new to first and then pop from first till last ? :) that will be reverse

[mike_2000_17]

if i m not wrong it means , i have to create a reverse link list and then read it , in order to read a link list in backward fashion

No. You understood AD and pyTony correctly (I think), that's what they suggested. But that is certainly not a good way to traverse a single linked-list in reverse, it's pretty much the worse thing you could do. And if you also have to modify the linked list while you are traversing it, then that solution becomes a nightmare.

There are a number of ways to traverse a single linked list in reverse (if you cannot use a double linked list). The actual technique you use depends on your requirements (mostly the size of the list, and your desired running time vs. memory usage trade-off). Here are the main options:

1. You can do an in-place reversal of the list while you are going through it in forward direction, then follow those links to go through the list in the backward direction (and do whatever operation you wanted to do in the first place), and at the same time, you do another in-place reversal of the list to bring the linkages back to the original. The advantage of this is that it uses no additional memory, the disadvantages are the double traversal (forward and back), the overhead of the in-place reversals, and temporary re-linking of the list (which you may not want to do).

2. You can create an array of node-pointers that you initialize by traversing the linked-list in the forward direction while filling in the node-pointers backward-going in the array, and afterwards, you traverse that array from start to finish. The advantage here is that there is very little overhead during the forward traversal and you don't modify the original list linkages. However, it costs you the extra storage for the array of reversed-layout node-pointers. And you still have to do two traversals, one forward in the list and one forward in the array of node-pointers.

3. The final option is to do a recursive traversal with a postorder of the operation on the nodes. This means that your recursive function first makes the recursive call on the "next" pointer, and then, does the operation on the current node. This will have the effect of recursing down to the end of the list before any node operation is done, and all the node operations will happen on the way back from the recursions, and thus, will happen in reverse order. In effect, this is equivalent to option 2, except that the array of node-pointers is constructed on the stack (as opposed to dynamically allocated memory), and that is the only advantage of this approach. The disadvantage is obviously that the size of the list must be moderate (not to overflow the stack). In C99, you can also achieve the same effect by using option 2 with a Variable-Length Array (and other forms of stack-based dynamic memory allocation).

And in response to pyTony and AD, not very cool guys... the only solution you both suggested is to create another, reversed, linked-list. That's a horrible solution, inefficient and unnecessary. As for the argument that you simply shouldn't use a single linked-list if you need to do reverse traversals, well that's reasonable, at least, the question "should I use a double-linked list for this?" should come up and be considered when writing the code. But there certainly can be cases in which you could prefer a single linked-list, but would still like to have the possibility for reverse traversal (albeit very inefficient compared to a double linked-list), whether it is for very occasional (or debugging) use, to comply to some given interface, or just for the challenge of the task itself (or course assignment). In any case, the question is about reverse traversal of a single linked list, so at least, try to answer that with a serious answer (not the ludicrous "create a reverse list" solution).

[Schol-R-LEA]

There is another approach to this, which would not require you to rebuild the list; however, the technique needed is not that different from that used to reverse the list, so which would be the most useful would depend on the overall goal. In essence, what you would do is recurse down the length of the list, then apply the operation you need to perform on the list:

struct Node 
{
    int data;
    struct Node* next;
};

void printReverse(struct Node* list)
{
    if (list == NULL)
        return;
    else
    {
        printReverse(list->next);
        printf("%d ", data);
    }
}

This is jut a quick-and-dirty example; you'd need to apply the technique as appropriate.

[Sokurenko]

there is no problem to do backward or frontward in single linked, as long as it is only one way to go needed, is more needed is both or one ? or you just go from start agayn to that spot you need. Or depends how much back you whant to go if it is by one to delete then you delete element-next not element and you good to go

[Trentacle]

there is no problem to do backward or frontward in single linked, as long as it is only one way to go needed, is more needed is both or one ? or you just go from start agayn to that spot you need. Or depends how much back you whant to go if it is by one to delete then you delete element-next not element and you good to go

I feel you're sincerely trying to help, but your post does not make sense. I imagine English is not your native language, so I have avoided being unnecessarily critical -- but as a native speaker, I have trouble following your train of thought every time I read one of your posts.

For starters, try to use complete sentences, and use more specific words than "do" and "go" -- I think you're probably talking about traversing the list (i.e., examining each element in order), but then it doesn't make sense to say that it's not a problem to traverse it backwards -- because there is, in fact, no way to traverse a singly linked list in reverse. If there were, it would be doubly linked.

[Sokurenko]

@Trentacle
so if i use stack as singly linked list i dont travel reverse when i pop it ? even link Click Here

[TrustyTony]

@mike

create another, reversed, linked-list. That's a horrible solution, inefficient and unnecessary

That is dependent what you think about the linked list, I was thinking in terms of conses of pointers like Lisp lists, with only next pointer, pointer to data. It is very clear solution as we have clean new list of pointers (sometimes hacked like least significant bits signing the type, with 30 bit data instead of pointer). This means that data is allways indirect and blocks of data can appear in many linked lists. This could of course lead complications in reference counting of data blocks. I do not however like the monolithic blocks of data, however cache friendly they may be.

In this case of data pointer, my solution is basically same as your point 2, except it would produce clear regularly traversable list, but array of pointers would refer to overlapping tails of the lists. So it would be "Here is node of this list, but do not touch it's next pointer data, just use as single node."

[Trentacle]

so if i use stack as singly linked list i dont travel reverse when i pop it ?

You traverse the list, pushing each item (or a pointer to it) onto the stack as you reach it, then pop each item off the stack. You've added a new data structure (the stack), to which you copy the information in your linked list and read it out backwards. Conceptually this is the same as creating a new, reversed list.

I didn't say there is no way to reverse a singly linked list -- there obviously is. But there is no way to traverse a singly linked list backwards.

[deceptikon]

But there is no way to traverse a singly linked list backwards.

Incorrect, and if you had read this thread more carefully you'd see at least two replies (one from mike_2000_17 describing the process and one from Schol-R-LEA with sample code) showing an easy way of doing what you say isn't possible.

Now, there's certainly a case for calling a recursive traversal reversing the linked list, but since the structure of the list isn't being altered and no extra storage is used, I'd say such an argument is dubious at best. ;)

On a side note, I'll say that I'm strongly against recursive solutions for linked lists most of the time because it's a linear process. In my opinion each recursive step should significantly shrink the problem set, and linear algorithms only shrink the set by 1. Thus they're better solved by loops.

[Trentacle]

Incorrect, and if you had read this thread more carefully you'd see at least two replies (one from mike_2000_17 describing the process and one from Schol-R-LEA with sample code) showing an easy way of doing what you say isn't possible.

I saw the replies, and I stand by my former statement.

[Schol-R-LEA]

Deceptikon: While that argument in favor of iterative solutions has merit in general (much though it pains the Schemer in me to admit it), in this particular case, the recursion is used less as a way of performing a loop than for the purpose of building up a stack with which the information about the list elements' positions is held at run time. The alternatives, either using an explicit stack or creating a separate reversed list, involve additional explicit data structures which have to be manually manipulated by the coder. Thus, I would argue that the recursive solution is the more elegant approach in this instance.

As for when one would want to generate a list in reverse order from the original, as opposed to traversing the existing list in reverse, it would depend on whether the reversed list needs to be persistent independent of the original. If you need the reverse of a list several times over, it makes sense to use a copy of the original in reverse order rather than performing the traversal repeatedly.

PyTony: While I too tend to have a bit of a Lisper's viewpoint on these matters, it is useful to recall that a Lisp style cons cell differs from most C linked lists in that the data is not bound to the cons cell directly; both the CAR and CDR of the cell can point to either an atom or a list, and more than one cons pointer can point to the same atom. This contrasts with your typical C list node, where both the data and the next pointer (the equivalent of the CDR in Lisp) are part of a single structure, and there is, generally speaking, no sharing of data between lists. The cons cell thus is a more lightweight list structure, with regards to multiple lists holding the same data, so creating a reversed list is a relatively low-cost operation compared to the equivalent in C. While there is no reason why you couldn't create a general-purpose list node structure in C - most Lisp implementations written in C do just that - it is relatively uncommon practice, as it means an extra dereference for each data access, something most C programmers have good reason to avoid.

[deceptikon]

I saw the replies, and I stand by my former statement.

Then I'd ask you to explain your rationale for making a provably incorrect statement and then stubbornly sticking to it. I assume you'll go with the "recursion is just an implicit stack" route?

Deceptikon: While that argument in favor of iterative solutions has merit in general (much though it pains the Schemer in me to admit it), in this particular case, the recursion is used less as a way of performing a loop than for the purpose of building up a stack with which the information about the list elements' positions is held at run time. The alternatives, either using an explicit stack or creating a separate reversed list, involve additional explicit data structures which have to be manually manipulated by the coder. Thus, I would argue that the recursive solution is the more elegant approach in this instance.

Generally the elegance of linear algorithms is close to identical between recursion and iteration. And given the higher chances of stack overflow in a linear algorithm with recursion, iteration is far more robust. I'm a fan of recursion too, but it's important to recognize where it's not the best practical option.

By the way, my side note was in general, not for this specific case. It should go without saying that if you can't use an iterative approach in-place (as in the case of traversing a singly linked list in reverse) and don't want to explicitly use another structure to handle the data, then even though it's a linear algorithm, recursion is appropriate for shorter lists. Did I cover all of the exceptions with that long sentence? ;)

Ultimately the OP's question stems from using the wrong data structure. If you need the data in both forward and reverse order then a singly linked list is the wrong choice. It's like asking how to pound in a nail with a screwdriver. You can do it, but a hammer would be the better choice of tool.

[mike_2000_17]

I assume you'll go with the "recursion is just an implicit stack" route?

Isn't that your opinion too, deceptikon? Once you are aware that a recursion stacks up memory on the stack (stack frames) (assuming no tail-call optimizations), then you see a recursion as just a way to implicitly create a stack on the stack. Unless you think recursions are magical, I don't see any other way to see them as. I would only question the "implicit" part, I would say "automatic" instead.

To me, using a recursion is only an elegant way of using a stack-based auxiliary storage, as in this:

// Recursive version of "Option 3" (by Schol-R-LEA):
void printReverseRecursive(struct Node* list)
{
    if (list)
    {
        printReverseRecursive(list->next);
        printf("%d ", list->data);
    };
};

// Iterative version of "Option 3":
void printReverseIterative(struct Node* list)
{
    if (!list)
        return;
    unsigned int list_size = 0;
    struct Node* current = list;
    while(current)               // --- get the size ---
    {
        current = current->next;
        ++list_size;
    };
    struct Node* node_stack[list_size];  // <-- VLA (C99)
    unsigned int i = list_size;
    for(current = list; current; current = current->next) 
        node_stack[--i] = current;       // <-- stack the node pointers.
    for(i = 0; i < list_size; ++i)       // --- reverse traversal ---
        printf("%d ", node_stack[i]->data);
};

Except for the obvious difference that it is much easier to grow a stack on the stack through recursion than it is via a variable-length array (or other stack-based dynamic allocation), and it is also more efficient. So, I don't see this as an implicit stack, but rather as an automatic stack (allocation is automatic). Of course, the above is what I described as "option 3". And I said, clearly (I think), that this applies only to small lists for which the stack will not be overwhelmed!

Option 2 is very similar, except that freestore is nicer to work with (albeit not as fast if the list is very small):

void printReverseOption2(struct Node* list)
{
    if (!list)
        return;
    unsigned int list_size = 0;
    unsigned int node_stack_size = 32;
    struct Node** node_stack = (struct Node**) malloc(
        node_stack_size * sizeof(struct Node*));
    for(struct Node* current = list; current; current = current->next) 
    {
        if(list_size >= node_stack_size)        // --- dynamic growth ---
            node_stack = (struct Node**) realloc(node_stack, 
                (node_stack_size *= 2) * sizeof(struct Node*));
        node_stack[list_size] = current;        // <-- fill node-stack
        ++list_size;
    };
    while(list_size > 0)                        // --- reverse traversal ---
        printf("%d ", node_stack[--list_size]->data);
    free(node_stack);
};

Which is quite a bit more elegant than option 3 without recursion. As for Option 1, well, I'll leave that open.

@pyTony:

That is dependent what you think about the linked list, I was thinking in terms of conses of pointers like Lisp lists

Ohh.. well.. if we can think about linked lists in other languages / paradigms, then we can dream up just about anything: in my magical programming language called mikutopia, linked-lists are made of ice-cream, so creating more copies just leads to more ice-cream for everyone! Without details on the linked-list implementation by the OP, we ought to assume the standard (idiomatic) linked-list implementation in C, which would be like in Schol-R-LEA's code (next-pointer and data (by value) in one Node struct). And, btw, the Lisp linked-list, as indirects to indirects, is exactly the kind of thing you would specifically avoid in C/C++ (that is, if you are concerned at all about performance, if not, then why are we talking about this).

[deceptikon]

Isn't that your opinion too, deceptikon?

As usual, it depends. In this thread we're bouncing around a lot between conceptual and concrete, and I'm not the only one guilty of switching at one's convenience.

Programmer A: You can traverse a linked list with recursion.
Programmer B: No you can't! Recursion is a stack!
Programmer A: But you're still traversing the linked list without any explicit storage.
Programmer B: Explicit shmexplicit, storage is storage.
Programmer A: But it's under the hood.
Programmer B: How does that matter?
Programmer A: Technically recursion doesn't need to be implemented with a stack.
Programmer B: Whatever, it's still not a traversal. Recursion is an elegant solution though.
Programmer A: Be careful, it's elegant but not robust because the stack can overflow.
Programmer B: Dafuq?

;)

[mike_2000_17]

Well, you can look at it the other way around:

Programmer A: I have a problem, I would like to create an efficient stack-based dynamically-sized stack..
Programmer B: Well, that's a tough one... let me think.. you could use a VLA, but then you'd need to know the size in advance.. so, uhmm, euhh.. let me ask Dennis Ritchie.. wait, he passed away (RIP)... are you sure you need this? You know the stack can overflow, right?
Programmer A: Yes, and yes... Now that I think about it, I could build the stack using a recursion!
Programmer B: But... but... that's not a stack, that's a recursion!
Programmer A: What's the difference?
Programmer B: Euhh.. uhmm, nothing?
Programmer A: Exactly!
Programmer B: Ahh, the Force is strong in this one!
;)

Just another duality programmers have to live with. When you need recursion, you have to worry about the stack piling up (e.g., when implementing quick-sort). When you want to pile things up on the stack, you need to use recursion.

[TrustyTony]

Without details on the linked-list implementation by the OP, we ought to assume

Hmmm.... I would not call it exactly implementation: http://www.daniweb.com/members/955352/sparsh610/posts#post1823799

[sparsh610]

it is good that there is discussion going on here.
but as a beginer i want to say it is very difficult to understand what my seniors are talking about.
experience makes a huge difference :) :)

[mike_2000_17]

Sorry about that, we tend to go astray when interesting issues are raised.

We can bring the conversation back down to your level (no offense), if you just give us more specific questions about what you would like clarifications on. And if you have code for this problem that you would like checked, please post it.