Lecture 20 - Linked Lists


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

$ mkdir ~/cs170/labs/lab20
$ cd ~/cs170/labs/lab20

Reading Quiz

On Inquire. It is only 5 questions long, is multiple choice, and should be very short for those who read through the chapter. However, if you have your book with you, you may use it as a reference duing the quiz. No other materials are allowed.


Tk Colors

Up to this point, you all have been using the names for colors when using Tk. However, that is not very helpful with the current definition for the mandelbrot set, where you need 255 shades of gray. We should probably cover how you can specify arbitrary colors in Tk, so you don't have to have a list of 255 entries just to represent your colors.


Linked Lists

Today we begin our journey down the rabbit hole of data structures. You have been using data structures for a while now, even if you might not have realised it. For example, lists are a data structure, just like dictionaries and tuples. Even the objects you have been creating are technically data structures.

Linked lists belong to a class known as linear data structures. They store a collection of data in a linear fashion, where access to an arbitrary element is restricted to a traversal through all of the previous elements. This is accomplished by having each node in the structure have a reference to another node of the same type.


Lab Activity 1
A Singly Linked List

A linked list is a sequential collection of data. A singly linked list is a sequential collection of data that can only be traversed in one direction. This may seem like it might be very restrictive. However, these types of lists are very powerful.

Details

Create a file called linked_list.py in your lab20 directory. This file will contain everything you do with a linked list. The goal is to flesh this file out over the next couple of days, so that you will have a good linked list definition for future activities and assignments that will be using the linked list class.

In this file, create a class called LinkedList. This class needs at least one attribute: head. This attribute will operate under the invariant that it always points to either the first element of the list, or None if the linked list is currently empty.

Inside this class, create a new class called Node. Notice that this class is defined inside of LinkedList, meaning to access the Node class you have to go through the LinkedList class. This inner class should have at least two attributes: data and next. Data can be anything, but we are going to operate under the invariant that next either refers to another instance of Node, or is None.

Once you have these classes set up, you should be able to manually construct a linked list like you see in the example below.

Example

>>> my_linked_list = LinkedList()
>>> my_linked_list.head = LinkedList.Node()
>>> my_linked_list.head.data = "Hello"
>>> my_linked_list.head.next = LinkedList.Node()
>>> my_linked_list.head.next.data = "World"
>>> print(my_linked_list.head.data)
Hello
>>> print(my_linked_list.head.next.data)
World

Hint

  • Notice that my constructor for both a Node and the LinkedList don't take any parameters. you need to define default values for all of the attributes, so that the attributes definitely exist, but contain their associated default values.

  • The inner class Node can only be accessed through the LinkedList class. This means you have to specify the name of the enclosing class to get access to the inner class definition.

  • We can string together an arbitrary number of attribute accesses, without needing to specify an intermediate variable to hold the value of the first access. This is because the "." operator is left-associative:

          my_linked_list.head.next.data == (((my_linked_list.head).next).data)
    
    Which is also equivalent to:
          head = my_linked_list.head
          heads_next = head.next
          heads_next_data = heads_next.data
    

 

Challenge

As you may have noticed, our singly linked list is very similar to a doubly linked list. The only difference is that nodes should have a previous reference as well. We already know of one mechanism that will make creating these new lists and nodes much easier: inheritance!

Create a DoublyLinkedList class in the same file. This class should inherit your LinkedList class. No real changes need to be made to the DoublyLinkedList class at this point. The only thing that needs to be updated is the Node for a DoublyLinkedList. This Node should inherit LinkedList's node, and simply add a prev reference.

Example

  >>> my_doubly_list = DoublyLinkedList()
  >>> my_doubly_list.head = DoublyLinkedList.Node()
  >>> my_doubly_list.head.data = "Hello"
  >>> my_doubly_list.head.next = DoublyLinkedList.Node()
  >>> my_doubly_list.head.next.prev = my_doubly_list.head
  >>> my_doubly_list.head.next.data = "World"
  >>> print(my_doubly_list.head.data)
  Hello
  >>> print(my_doubly_list.head.next.data)
  World
  >>> print(my_doubly_list.head.next.prev.data)
  Hello

Lab Assignment 20
Inserting and Printing

It is going to get very tiring very quickly if we have to build our linked lists manually like in the examples above. Instead of doing that, we should have a functionality that can just add things to our list. However, testing this will also be a pain, unless we write a method that will also print our list out.

Details

In your linked_list.py file, you are going to add at least two methods to your LinkedList class. The first is a method called append, which takes a piece of data and adds a new node with that data to the beginning of the list. The other method you need to write is called __str__, which returns a string that will allow us to print the list a little more easily.

Make sure you test these functions very carefully. What are the border cases you need to test?

Example

>>> my_linked_list = LinkedList()
>>> my_linked_list.append("Hello")
>>> my_linked_list.append("World")
>>> print(my_linked_list)
head -> World -> Hello -> None

Hint

  • You need to create a new node inside of your append method for the data that gets passed in. You can access the Node class from within LinkedList by using the self reference:

          new_node = self.Node()
          

  • The next reference for the new node should be whatever is currently the head of the list. The data for this new node should be whatever got passed to append as the data parameter.

  • To add something to the list, you simply need to change the head attribute of the LinkedList class. Make sure the next reference for the new head of the list is already set!

  • There are two ways to go about the __str__ method: a loop within the method, or by writing a recursive __str__ method for your Node. Either is acceptable, as long as your functions produce the correct output.

 

Challenge

If you did the previous challenge, then you should also modify these methods for your doubly linked list class. The edge cases for this linked list are a little bit more complicated, but are not too terribly difficult.

 

Challenge

While appending to the front of the list is pretty easy, it is not how you perceived lists working. Create a method append_end for your LinkedList classes, which appends the data at the end of the list.

The Big-Oh class of the normal append function is described in the book. What is the Big-Oh class of this method? Is there a way to improve that?


Submission

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

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

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



Last modified: Wed Mar 12 09:48:16 EDT 2014