< Back

Lecture 19 - More Linked Lists

As usual, create a directory to hold today's activities:

  $ mkdir ~/cs170/labs/lab19 
  $ cd ~/cs170/labs/lab19 

Using Linked Lists

You should, by this point, have a fairly well functioning linked list object. Today, we are going to start looking at how and why you might use a linked list. Obviously you are using a linked list for the assignment, but what about other examples. One example of why you would use them is in the creation of a different class of data-structure, known as a Stack.

Lab Activity 1

A Stack is known as a Last-In, First-Out (LIFO) data structure. That means that the data that was most recently added to the structure is the first and only thing that can be removed. In order to get to data that was added earlier to the stack, you have to remove all of the things that are above it. The interesting thing about stacks are that you have been implicity using one, without even knowing it.


First things first, you need to copy your LinkedList class into your current directory.

$ cd ~/cs170/labs/lab19 
$ cp ~/cs170/labs/lab18/linked_list.py .

Create a new file called stack.py. In this file, you should define a class Stack, which will inherit your linked list class. You will need to import linked_list at the top of your file so that you can have access to your LinkedList class.

Your class must have the five key methods for a stack, plus one additional method for testing purposes:

Make sure that your methods work appropriately. Think about special cases you might need to handle for pop and peek!


>>> my_stack = Stack()
>>> my_stack.push(1)
>>> my_stack.push(2)
>>> my_stack.push(3)
>>> print(my_stack)
top -> 3 -> 2 -> 1 -> bottom
>>> print(my_stack.size())
>>> print(my_stack.pop())
>>> print(my_stack)
top -> 2 -> 1 -> bottom
>>> my_stack.pop()
>>> my_stack.pop()
>>> my_stack.pop()
No more elements in the stack.


  • Your operations here are pretty straight forward. A majority of them you already have written, you just need to "re-name" them through inheritance.

  • push is essentially insert, where the location to insert is ALWAYS 0. To simplify your size computation, however, you should maintain a size attribute that increments with every push.

  • pop is really the only new method. You need to essentially remove the front element, and return the data from that element. To remove the front element, you just need to move the head reference. You will need to store the data in that node before you remove it, so that you can return it later. Don't forget to decrement your size attribute!



You would be able to do the next portion of the lab pretty easily with just the built in python list. However, there is this notion of Abstract Data Types (ADTs). An ADT is simply an interface that the data type must follow to be representative of this type. We explicity followed the ADT for a Stack above. However, the built in python list does not explicitly follow the ADT.

Write a class class called StackList, which inherits the built in list class (notice the punctuation). This class should have the same methods as the linked list Stack class. The methods you use, however, will be different.

Lab Activity 2
Paint Bucket

A very useful tool for a majority of paint programs is the paint bucket tool. The paint bucket tool allows the user to click on an enclosed area, and it fills that enclosed area with the current fill color. A very common way that this is accomplished is by using a stack to keep track of the locations of the image that need to be filled.

You are given a program that has a recursive method to solve the paint bucket problem. However, this program will crash if you select certain regions of the image to fill. This is because there are a lot of pixels to fill, and the recursion limiter of python prevents the program from running.

As it turns out, any recursive method can be rewritten using a stack. This is because Python uses a stack (referred to as the "call stack") to keep track of where in the program to return when the program finishes executing. The call stack also stores local variables of a method so that their values can be restored after a method call. What you will do today, is modify this program so that it uses a loop and a stack instead.


The file paint_bucket.py (You will also need the file ovals.gif) contains a program that draws an image with several overlapping ovals. There are a lot of methods already defined for you. The method you are modifying is fill_region_loop. You should read over the Pre and Post conditions of the built in helper file carefully, so that you can understand how to use them effectively.

fill_region_loop will be using a stack in order to accomplish its goal.


  • You should initialize the stack with the coordinate the user clicked on. Then, while the stack is not empty, you pop the item off the top of the stack and process it. The processing portion is essentially the same: if the current pixel color is the color to fill, color it in. The only difference is that instead of making a recursive call, you will simply push all of the neighbor's coordinates onto the stack.

  • You should be able to use the size attribute of the stack to determine whether there are still elements in the stack to process.



Tk can load any ".gif" image directly onto the canvas. Find an image that is not a black and white image, and load it onto the canvas. Pick a region of this image, and modify the program that you can click on the region and color it in. Do you notice anything peculiar about this behavior?

This program relies on the pixel colors to be exactly the same in order to fill them in. However, in real images this property is extremely rare. Instead, we can use a process known as "fuzzing" in order to get around this.

Define a global parameter FUZZ_FACTOR which is some integer value that you can modify easily. For a decent start, choose a value 10. If the euclidean distance of the color of the current pixel and the color to fill is less than the fuzz factor, go ahead a fill that pixel in.


When you have finished, create a tar file of your lab19 directory. To create a tar file, execute the following commands:

  cd ~/cs170/labs
  tar czvf lab19.tgz lab19/

To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 19. Make sure you include a header listing the authors of the file.