Python Linear Data Structures: A Trip to Hanoi Tower Part 2— Linked List
Linked lists are one of the basic data structures used in computer science. They have many direct applications, and serve as the foundation for more complex data structures.
There are different types of list, for example stacks which work on a first-in-last-out principle (FILO). Imagine setting a stack of dishes. The one you can see is the last dish added on top of the stack (known as the head node), and to get to the last dish you’ll have to traverse down the stack to the last node (tail node).
Another type of list is the queues list, which much like a grocery line is a first-in-first-out principle (FIFO).
For my Hanoi Tower I’ll be using the stack-list type since this makes more sense with the premise of the game (larger disk sizes can’t be placed on smaller disk sizes).
So what kind of functionalities would I want a list to have? The most basic operations are, adding nodes, removing nodes, finding a node, and traversing (or traveling through) the linked list.
So let’s build programmers.
First how should my class look? Let’s think about it. We know a stack runs FIFO so it’s kinda like starting at the top floor of a building and in order to get out I have to go down each level to the bottom. I’ll want to know what the top_node is, and I’ll at least want to know the size of the building/how many nodes do I have. It’s also a pretty good idea to have a limit to my list size. If a building is too tall at some point it will collapse. Remember it’s always good to plan ahead, and think about how you want your data set to look. It’ll make it easier to manage once you’re working with large data sets.
Pretty basic. You see the only value I take is the name value since that’s all I’ll need to initialize my Stack.
So I’m going to create some basic functions that will retrieve me information about my Stack. Some basic things to know about my list is if it has space, is empty, what’s the size, and name. Fairly straight forward.
So let’s add (push) my first node onto the list. First I’ll check that it has space to add a node. I’ll then set the next node to the current top_node -which would be None at the moment - making this the first/tail node. The following node will then point to this current node being added, and away it goes till I reach the limit of my stack. I’ll set the top_node to the added node so the top_node is no longer a None value. I’ll then add 1 to the size of my Stack.
If I am well into my List construction, and do not have space I’ll return an else statement stating so.
Note: You’ll notice I’m using my Node class from the last article to set the item variable. I’ve imported it from another file to use here.
Next I’ll want to remove (pop) an item off the list. I’ll check that the list isn’t empty, otherwise it’s an error ’cause what am I pop’n — nuthin? I’ll then grab the node to remove, and set the top_node to the next node in line. I’ll minus 1 from the Stack size, and return the removed node.
Now I’ll just want to be able to look at my top node. I’ll implement a peek() function for that, and all it’ll do is return the value of the top node. As long as my Stack isn’t empty of course.
Alright, for my last trick I’d like to get a print out of all the nodes in my Stack. This part sometimes gives me the woozy, so I’ll break it down best I can. I’ll first make a pointer that points me to the top node until it reaches the tail node, and hits the None value. I’ll also set up an empty list to append all the nodes I come back with.
So running a while loop on the pointer variable I’ll append the pointer’s value, which is the same as the top_node’s value. I’ll then change the pointer to the next node using my Node class get_next_node() function. This will run till my pointer value reaches the None pumpkin value of the tail node.
I’ll then run a python reverse() function on my list, and print out the node information.
And with all that I’ve got a functioning Stack list. This Stack will follow the principles of my Hanoi Tower game -FILO, so I’m ready to write the script to make my game.
So let’s try it out, and see if I’m working without errors.
Houston we have lift off.