Lecture 21 - Linked Lists

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

$ mkdir ~/cs170/labs/lab21
$ cd ~/cs170/labs/lab21

Class Invariants

Up to now, we have not been documenting the constructor for a particular class. This is because up to now there hasn't been much of a need to do so: all of our classes were specified simply for one program, and that one program alone. However, now our classes are going to be used in a lot of different projects. Documenting that constructor just became a lot more important. We will talk about class invariants, and how to document them properly.

Linked Lists

We saw the very simple form of creating linked lists on Wednesday, but there were still some lingering questions: Where are these nodes being stored? Why do we need this internal class? Where do thse object exist and go during run time? etc. Today, I want to clear that up a little bit, as well as introduce how we can remove things from the linked list.

Lab Activity 1
Indexing

One of the nice things about the built in list in python is the ability to access an arbitrary element by specifying its index. For the built in python list, this operation is O(1). For our linked list, the only element we have immediate access to is at the head of the list. How would we get access to items deeper in the list?

Details

Copy your linked_list.py file from lab20: 

$ cd ~/cs170/labs/lab21
$ cp ../lab20/linked_list.py .

Add a method to your LinkedList class called get. This method will take a single parameter: an integer in the range [0, size of the linked list). This method will return the data contained in the element specified by the integer parameter.

Think about the Big-Oh complexity of this operation. Write your expected big-oh complexity in the comments of the get method.

Example

>>> linked_list = LinkedList()
>>> for i in range(1, 11):
...    linked_list.append(i)
...
>>> print(linked_list.get(0))
10
>>> print(linked_list.get(9))
1

Hint

  • The code for this is very similar to the search code that is in the textbook. Instead of looking for a particular element, you need to iterate through the list a fixed number of times.

  • In the previous lab, we couldn't use a for loop to iterate over the elements of the linked list. However, for this method we can use a for loop. This is because we know the exact number of iterations we want to execute.

 

Challenge

We know that python implements its lists using a linked list in the background. So it seems that large lists should be pretty slow at accessing elements of the list. Use the TimeIt module, to time accessing the first element of a python list vs. accessing the last element of a python list. Do the same thing for your linked list class. Do you notice anything iteresting about these results? Include your findings in the comments of the linked_list.py file.

Notice: You do not need to plot anything for this.

Lab Assignment 21
Insertion and Deletion

Another nice thing about python lists is that we can insert data into arbitrary locations within the list. However, right now we can only add to the front of the linked list. We should definitely add a mechanism to add to arbitrary locations in the linked list.

Another thing we like to do with python lists are removing elements from the list. Removing elements from a linked list is interesting, because we essentially just have to re-order the list so that the node we removed is skipped over when we traverse over the list.

Details

You will need to write two new methods for your LinkedList class: insert and delete.

insert takes two parameters: the first is the data that you want to add to the list, and the second is the location in the list that you want to add that element. This method will create a new node, and rearrange the references to include that node in the correct location of the linked list.

delete takes one parameter: the data that the node you want to delete contains. This method will find the first node that contains the specified data, and removes it from the list.

Make sure you test your methods carefully. Think about what the edge cases are, and how to handle them appropriately.

Example

>>> linked_list = LinkedList()
>>> for i in range(1, 11):
...     linked_list.append(i)
...
>>> linked_list.insert(0, 1)
>>> print(linked_list)
head -> 10 -> 0 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> None
>>> linked_list.delete(2)
>>> print(linked_list)
head -> 10 -> 0 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 1 -> None

Hint

  • While it seems complicated, inserting to an arbitrary location is very similar to inserting into the front of the list. You first create a new node for the specified data. Then, you iterate through the linked list the number of times specified as a parameter. This finds the node that should point to the new node. But first, you need to set the new nodes next pointer to be that of the node you just found. Then you set the found node's next to the new node.

  • For deletion, consider the following linked list:

    Assume we want to remove the node containing the data "4" from this list. We simply want to make any node that "points" to that node to point around that node:

    First, you need to find the node that "points" to the node that contains the specified data. You can do this by performing a linear search through the list, until the data of next is the element to be remove. Then, you set the next pointer of your found node to be the same as the deleted nodes next pointer.

 

Challenge

Now that you have insertion into arbitrary locations in the list, you can now write sorting algorithms for linked lists. The most simplified sorting algorithm you can write for a linked list is insertion sort.

Write a function called insertion_sort_linked_list, which takes a linked list as a parameter, and returns a copy of that linked list in sorted order.

If you finish that one up early enough, give selection_sort_linked_list a shot as well.

Submission

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

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

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

Last modified: Fri Mar 14 08:54:59 EDT 2014