In week 2 you worked out the logic of stacks and linked lists using pseudocode. Now that you have been introduced to object-oriented programming, you are in a position to actually start coding classes to represent stacks and linked lists.
Here are some solutions for the stack and linked list pseudocode from week 2, which you can use this week in preference to your own, should you wish to:
STACK
=====
The stack will need various variables:
1. the internal array ("array")
2. the index to add the current item of data to. ("index")
3. the total capacity of the internal array ("capacity")
Push pseudocode:
----------------
Takes one parameter, "item", the item we wish to add.
If index is less than capacity
Set position "index" within the internal_array to "item"
Increase "index" by one
Else
Inform user that the stack is full
Pop pseudocode:
---------------
Pops the top item from the stack and returns it.
If "index" is 0
Inform the user that the stack is empty
Else
Set the array at index-1 to "None"
Reduce "index" by one
Return the value that was removed from the stack
//////////////////////////////////////////////////////////////////
LINKED LIST
===========
The linked list will need to hold these items of data:
- the start node ("start")
- the end node ("end")
Add pseudocode:
---------------
Adds an item to the end of the linked list.
Takes one parameter, "item", the item we wish to add.
Create a new node, containing the item
Link the existing last node forward to the new node
Link the new node backward to the existing last node
Set the last node to the new node
Get pseudocode:
---------------
Looks up an item by index.
Takes one parameter, "index", the index we wish to look up.
Returns the item at that index.
Set variable "current_node" equal to the start node
Set variable "current_index" equal to 0
While "current_index" is not equal to "index"
Move "current_node" on by one by following the link to the next node
If "current_node" is None
Display an error to indicate that the index could not be found
Return None from our get() method/function to indicate to the main code that the index could not be found.
Increase "current_index" by one
Return the value within "current_node"
Having looked at a simple Cat class, we are now going to do something a bit more practical and look at how we might create a Stack class.
Note that it does not actually act as
a stack at the moment, but it provides the framework for how a stack operates;
notice how it contains an array and push() and pop() methods.
class Stack:
def __init__(self):
self.internalArray = []
def push(self, item):
# Code to add an item to the stack will go here
pass # ends the method when it's empty
def pop(self):
# Code to remove an item from the top of the stack will go here
pass # ends the method when it's empty
def __str__(self):
return self.internalArray.__str__()
How is this working?
Note how we define three methods again. We have push() and pop() to define the most fundamental operations of a stack. The __init__() method for a stack will, like the cat equivalent, run when the stack is first created. We are using it to create the underlying array associated with the stack (see below for more detail).
So, going back to __init__(), note how we are attaching an attribute array to the current object, with this code:
self.internalArray = []
Note the [] syntax. This creates an empty array. (Well actually, it doesn't; it creates an empty Python list, as we saw last week, but we are treating the list as an array.).
Note how the push() method contains not just self but also another parameter, item. This is the item we want to add to the internal array.
Note the fourth method, __str__(). This is another special method, rather like __init__(). This is a method which defines how objects of a class are printed. We might want to print our stack with:
print(stack)
What happens though when we try to print an object? By default we just get its memory address. Adding a __str__() method to a class allows us to return a string representation which can be understood. Here, we return the string representation of the internal array, so when we print the stack, we see the contents of the internal array.
stack.py), write the Stack class as shown above, and try and complete the push() method of your Stack so that it takes the value passed to it, and appends it to the internal array. To do this you will need to use the list's append() method. Use your pseudocode from Week 2 to help you (or my "model answer" pseudocode above). Here is a simple example of appending to a list:list1 = []
list1.append("John")
Stack as follows by adding this code in a main.py:
stack1 = Stack()
stack1.push(1)
stack1.push(4)
stack1.push(9)
print(stack1)
pop() method.
Does this work as you would expect a pop operation to? Test it by adding these lines to your test code (the code where you created the stack and pushed items
onto it), which pops the stack twice and prints the value returned from each pop() operation:
popped1 = stack1.pop()
print(popped1)
popped2 = stack1.pop()
print(popped2)
You will find it does not. Why? Try and fix the code yourself to get it to work!
Linux
Windows
Mac OS X
Again, print the stack and pop items off the stack. Does it work with strings as well as integers?
You need to display an error if you pop an empty stack.
Using an if statement (you are doing these in COM411 this week), display an error message in pop() if the stack is empty.
How can you tell whether the stack is empty?
peek() method for your Stack. Remember a peek operation should
return the top item of the stack without removing it.Advanced optional exercise: If you are coping with this module and COM411 well so far, and keen to do more programming, and want something to do in your own time, read about exceptions and handle the error instead by raising an exception. This would be how errors are handled in real-world implementations of stacks. Feel free to implement your stack using exceptions and send it to me for checking.
We'll now move on to implementing the other data structure we looked at in week 2 - the linked list - in code. As you may remember, linked lists are a bit more complex than stacks so require a bit more effort to implement. In particular, we will now need two classes, not one. Put each class in its own file and import them into your main.py.
a Node class to represent an individual node. Each item of data is contained within a node, along with the links to the previous and next item.
a LinkedList class to represent the linked list as a whole. Remember that
this needs to contain references to the first and last nodes in the linked
list.
Node class. It should contain an __init__() method which looks like this:def __init__(self, data):
self.data = data
self.prev = None
self.next = None
What does this do? Remember we use __init__() to initialise an object of the class. A node needs to contain data. So this __init__() method allows us to create a node, and pass the data to it. The data then gets attached to the current node we're working with, using self.data = data.
Note how we initialise the prev and next attributes to None. These attributes represent the previous and next node. None is a special data type indicating that nothing exists yet; it will be appropriate here as we haven't linked this node to any others yet.
link() method to your Node. This should link another node to the current node. Using the code examples you have seen so far, try to figure out how to pass the new node into the method. Then, link the new node with the current node using this code. Note how it sets the next attribute of the current node to the new node, and the prev attribute of the new node to the current node.self.next = newNode
newNode.prev = self
Add a __str__() method to Node which returns a string containing the value associated with the node.
Create some test code in main.py which creates two nodes, n1 and n2, for example;
n1 = Node("Fred")
n2 = Node("Tom")
Note how we pass the data associated with each node ("Fred" and "Tom" here) when we create it. This will call our Node class's __init__() method, and set the variable data equal to whatever was passed in (Fred or Tom).
Now try printing n1 and n2 to prove that the nodes have been created separately.
Now link n2 to n1. To prove that the link has worked, try printing out all of these:
n1.prev
n1.next
n2.prev
n2.next
We have now created our Node class. We are now going to use it in a complete LinkedList class which will allow you to add nodes to a linked list, and access the linked list's first and last members.
Create a separate file for your LinkedList class and import it into main.py again. You will need to import Node into LinkedList.
Create a LinkedList class. Its __init__() method should initialise two attributes, self.first and self.last to None. (These are the references to the first and last node in the list).
add() method to your linked list. This should add a Node to your linked list. Use the pseudocode from Week 2, or my pseudocode above, to help you.get() method to your linked list. This should take an index as a parameter, i.e. write it as:def get(self, index):
and should search the linked list for the node at that index. Having found it, it should return it. Use your pseudocode from week 2, or my pseudocode above, to help you.
Test out your linked list by creating three Node objects and adding them to your LinkedList. Once you've added them, try searching for them within the linked list using their index.
Try searching for an index which does not exist in the linked list, such as index 10 for example. Is the error handled correctly?