$ mkdir ~/cs170/labs/lab20 $ cd ~/cs170/labs/lab20
On Monday we began our journey down the world of algorithmic analysis using both linear and binary searches. Today, we begin trying to answer the larger question: Which sort should I use and why?
To start, we will simply analyze the selection sort algorithm for time. However, time won't be the only component to our choice. We will continue to go over these sorting techniques as we continue our discussions of new topics.
Today we begin our journey down the 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.
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 . This may seem like it might be very restrictive. However, these types of lists are very powerful.
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.
>>> 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
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.
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.
>>> 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
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.
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?
>>> my_linked_list = LinkedList()
>>> my_linked_list.append("Hello")
>>> my_linked_list.append("World")
>>> print(my_linked_list)
head -> World -> Hello -> None
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.
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.
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?
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 inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
20. Make sure you include a header
listing the authors of the file.