AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |
Back to Blog
Reading linked list stack backwards11/24/2023 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. That's a horrible solution, inefficient and unnecessary. the only solution you both suggested is to create another, reversed, linked-list. 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).Īnd in response to pyTony and AD, not very cool guys. The disadvantage is obviously that the size of the list must be moderate (not to overflow the stack). 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. 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. This means that your recursive function first makes the recursive call on the "next" pointer, and then, does the operation on the current node. The final option is to do a recursive traversal with a postorder of the operation on the nodes. And you still have to do two traversals, one forward in the list and one forward in the array of node-pointers. However, it costs you the extra storage for the array of reversed-layout node-pointers. The advantage here is that there is very little overhead during the forward traversal and you don't modify the original list linkages. 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 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). 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 actual technique you use depends on your requirements (mostly the size of the list, and your desired running time vs. There are a number of ways to traverse a single linked list in reverse (if you cannot use a double linked list). And if you also have to modify the linked list while you are traversing it, then that solution becomes a nightmare. 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. You understood AD and pyTony correctly (I think), that's what they suggested. 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
0 Comments
Read More
Leave a Reply. |