< Back

Lecture 21 - More Linked Lists

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

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

Mandelbrot Art Project

The Computer Science club has a grand plan of making some of the walls in the CS lab a little bit less barren. They want to make a mosaic of the mandelbrot set usings images generated from your programs! If you are interested, please sign up in the form Thomas created for this purpose. More information will be sent to those who are interested by the end of the weekend.

Sign-up Form

Analysis of Insertion Sort

We continue our brief jaunt down the world of analysis by looking at insertion sort today. You probably have a decent idea of the runtime of Insertion sort, but we need to go through the math to determine what the true Big-Oh class is today.

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 these objects 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.

    The one issue you need to worry about with using a for loop is if the user puts an integer index that is out of range of your list. So you can't use a for loop, you will only mimic a for loop. If the index the user specified is out of range of the list print an error message and return -1.

 

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 Activity 2
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 operation we have used a lot for python lists is "remove". Remove takes a value from the list, and removes the first instance of that value. 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 inquire.roanoke.edu. You should see an available assignment called Lab Assignment 21. Make sure you include a header listing the authors of the file.