Linked List Stack in Python
Data Structures: Learning CompSci by Coding
We have been completing modules on computer science topics in the course of my General Assembly bootcamp, and I have been making a point to implement some of the most famous data structures and algorithms from scratch, using actual code. This process continues to be super helpful in understanding the concepts at a deeper level, and I'd recommend it to anyone learning (or relearning) these ideas.
- Push: Adds the item in the stack at the top.
- Pop: Removes the top item from the stack and returns it.
- Peek: Shows the top item from the stack.
- toArray: Convert the stack to the array.
- size: Returns the size of the stack.
- isEmpty: Returns true if stack is empty, false other wise.
- clear: Clears the stack.
Two classes: Stack and Node
In any case, this low-level concept of a linked list seemed a good opportunity for using classes, and I assumed Python must use them as a true object-oriented language. In object-oriented programming (OOP), you can define a class for each conceptual entity in your program (similar to how we define our models/schemas when working with MongoDB). In a stack implemented using a linked list, there's the stack at the top level, and then the links of the linked list (usually referred to as 'nodes').
Python Class Idiosyncrasies:
This one took some careful copy-pasting 😂, but eventually it became clear what was actually going on: the constructor method (the one that automatically runs once any time a member of a class is instantiated) is called
Also interesting was how we need to explicitly include
self as an argument within the definition of every class method.
this, but must be present in those incoming arguments.
Beyond the actual coding differences, it's been a small challenge to try and maintain a pythonic style: for instance using the word
list instead of
array, and naming variables and functions with snake_case and not camelCase (e.g.
to_list() in Python vs.
Stack, it's time to flesh out the "verbs" using class methods.
This was the first method I implemented, as the logic from several other methods would depend on the state of the stack. It was also pretty simple: check if the current
head is equal to
None, and if so it's empty! Note:
None in Python is similar (but not identical) to the ideas of
I'll admit I needed to frequently reference the tutorial to get these working; I just had a bit of trouble wrapping my head around the syntax and how
value were all connected. Here's what I ended up with:
self: the current stack
head: the "top" of the stack
next: the pointer that connects the current node to the next one
value: the data or item that is being stored in each node
The processes for
pop() are very similar, and require care to not break the links of the chain. It actuals reminds me of rock-climbing, when you are switching from secure anchor #1 to secure anchor #2, you must assure #2 is connected before you disconnect from #1. Similarly, when you create a new node, you set its
next to point to the current head first, and then swap the value of
head to reference this new node after.
Also related, these methods allow you to view the first and the entire stack respectively.
peek() simply returns the
head.value if the stack isn't empty, while
display() continues to walk through each node->next->node->next->node and display each node's value as it gets there.
These two methods both involve keeping track of a variable outside of your node-traverse, and updating that variable as you walk through: the integer
size(), and the list
stack_as_list for the
to_list() method (described as
I also needed to reverse the final list before returning from the method; since the items are extracted one-by-one from the last item added and added to the end of the tally list using
append(), I needed to do a final
stack_as_list.reverse() to put items in the correct order. Another approach would be to directly place the items into beginning of the tally list using
stack_as_list.insert(0, item) where
0 specifies the first position (
stack_as_list since Python lists are zero-indexed ).
To finish the set of methods listed at the beginning, we'll finish as simply as we began by simply clearing the array. This mimics the behavior of the stack's
__init__() method, by simply setting the
None. I suspect this might require some sort of garbage collection since all those nodes are still in memory, just simply no longer connected to our stack. If anyone has answers please let me know, and I'll update as I learn more!
Thanks again for reading; I will be attempting some more data structure implementations using Python in future blog posts so stayed tuned. Here are some more of the pages I referenced while learning this material: