Reverse() a Stack with Python.
Change direction of a singly-linked list without dropping the rope!
Having created a stack using a linked list in Python (more details in my previous blog post ), I was excited to expand on the functionality and add a
reverse() method to this data structure class. Again, as with many of these basic computer science concepts, the idea is easy to understand, but the actual code can be challenging to write, and presents severals "gotchas" along the way that might trip you up.
A stack is a collection of data where items are added and removed according to the "LIFO" acronym: Last In, First Out. Meaning, the last item that was pushed to the stack will be the first one to be popped off. I think of it like a Pez dispenser.
So what would we do if we needed to turn the whole thing around? A simple singly-linked list contains a series of nodes, and those nodes only contain 2 piece of information: the node's
value, and the location of the
next node in the list. To reverse, we would have to make all of our
next pointers point to the previous node. This is where things get tricky however, because we can simply swap them or we would lose track of the
next, and the remainder of the list would just be floating around our computer somewhere, untethered and unreachable.
Don't Drop the Rope!
I've used this rock climbing metaphor previously but it's so fitting: when a climber leads and reaches the top of a pitch, they need to be able to get back down to the ground. Their belayer can lower them, but now they've left a carabiner at the top of the pitch (the one that's functioned as their "pulley" and allowed them to be softly lowered to the ground). A common solution to this problem is rappelling down (a.k.a. abseiling), instead of belaying; rather than the climber leaving gear at the top, they actually thread their rope through the fixed-bolt into the mountainside, and then are able to use specialized gear to carefully lower themselves down the fixed rope, finally pulling the rope free from it's threaded anchor once they're safely on the ground.
Climbing specifics aside, this switch over from belay to rappel is extremely dangerous if done incorrectly, and requires careful attention to each simply step. At some point between untying their knot from their harness (on belay) and tying it back on (on rappel), the climber will be unprotected by their safety line, and could easily fall and be killed. For this reason, climbers carry small loops of nylon and extra carabiners, and are able to go "in direct" and have a 2nd, temporary connection to the mountainside that will protect them if they fall. To stretch this metaphor further, a climber will literally tie the end of their safety rope to their harness somewhere, to prevent the untied rope from slipping through the hands or gear and falling to the ground, leaving them stranded on the pitch.
Though far less dramatic, the same applies when reversing a linked-list; you must have a temporary variable to hold the "rope" of your remaining list, while you switch the current node's
next pointer to reference the
previous node, and the
next to reference the current node.
temporary = current.next current.next = previous previous = current current = temporary
Notice how at each step, the 2nd variable becomes the first variable of the next line. This also reminds me of how you swap the primitive values of two variables:
# task: swap the values of variables a and b a=1 b=2 # you can't just use a = b or b = a to start because then you'll lose the value stored in the overwritten variable # instead, use a temporary variable x = a a = b b = x
We are doing basically the same thing in our linked-list loop, but each variable is instead a node with a
value and a pointer to
next; this loop continues until you reach the end of the linked list;
Linked List Reversal: Function vs Class Method
There is one final step left: assign the list's
head value to point to the last item you found in the list, which would be our
previous. I followed along with a great blog post in working through this concept, and this last step was what tripped me up the most; I couldn't quite figure out why they were sending in the
head node and returning just the last
previous node. Some experimenting allowed me to discover the missing step (for my implementation) of explicitly assigning the new
head. As you can read in the comment's of their post; their particular case was not adding a
reverse() method to a listed link stack class like mine, instead they were making a function which would reverse a linked list given that list's first node. In that case you'd presumably want the result of the function to be the new "first" node (the
head) of this newly reversed linked list.
# reverse: reverse the linked list def reverse(self): # start at the top of the stack current = self.head # initialize temporary = None previous = None # walk through the linked list while (current != None): # don't let go of your rope (the rest of your linked list)! temporary = current.next # swap the link direction current.next = previous # attach current to the next nodes "previous" previous = current # step to what used to be the "next" node; which is stored in temp current = temporary # once reached the end/bottom of the stack # it's important to make that bottom item the new head self.head = previous
Thanks for following along! Hopefully you didn't get too lost on my rock climbing analogies, and hopefully you will do some more research before implementing my rock climbing advice in real life! No warranties or guarantees implied of the performance of your climbing or data structure performance.