CPSC 170 A

Lecture 17 - Data Structures

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

$ mkdir ~/cs170/labs/lab17 
$ cd ~/cs170/labs/lab17

Test Results

You will get a chance to look over your test results before we get into our main topic for today. Overall, this test average was higher than previous years, by about 10 points. Log into inquire to see comments on your tests.

Average: 73.84
Median: 76.5
Mode: 50
Standard Deviation: 18.22

Data Structures!

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 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_next_node = LinkedList.Node()
>>> my_linked_list.head.next = my_next_node
>>> my_next_node.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
```
That being said, a common cause of issues with getting an attribute error or None type error is by abusing this ability to string many attribute accesses together as possible. It will be much easier to debug if you create intermediate variables for statements that need more than one additional level of access.

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 Activity 2

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 end 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 -> Hello -> World -> None

Hint

You need to create a new node inside of your insert 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 data for this new node should be whatever got passed to insert as the data parameter.
If the list is currently empty, you can simply set the head reference to the newly created node. If it is not empty, you need to find the node at the end of the list. The node at the end of the list is the first node which has "None" as its next reference.
To add something to the list, you change the next reference of the last node in the list to the new node.
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.

Submission

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

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

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