< Back

Lecture 18 - More Linked Lists

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

  $ mkdir ~/cs170/labs/lab18 
  $ cd ~/cs170/labs/lab18

Linked Lists

We saw the very simple form of creating linked lists last class, 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
Insertion

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. Adding this functionality is not terribly difficult, So let's take some time to add that functionality.

Details

You will need to write one new method for your LinkedList class: insert.

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.

Assume for now that insert will always be given a location in 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)
  ...
  >>> print(linked_list)
  front -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> None
  >>> linked_list.insert(0, 1)
  >>> print(linked_list)
  front -> 1 -> 0 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> None
  >>> linked_list.insert(-1, 5)
  >>> print(linked_list)
  front -> 1 -> 0 -> 2 -> 3 -> 4 -> -1 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> None

Hint

  • While it seems complicated, inserting to an arbitrary location is very similar to inserting into the end 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.

  • There is only one edge case you should really need to consider. What happens if index is 0? In this case, you are really inserting at the front of the list. Therefore, you only need to update head.

 

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.

Lab Activity 2
Deletion

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 one new methods for your LinkedList class: delete. 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.

For now, assume that the data provided to delete is guaranteed to be in 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)
  ...
  >>> print(linked_list)
  front -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> None
  >>> linked_list.delete(2)
  >>> print(linked_list)
  front -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> None
  >>> linked_list.delete(10)
  >>> print(linked_list)
  front -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> None

Hint

  • 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 removed. Then, you set the next pointer of your found node to be the same as the deleted node's next pointer.

  • Again, our edge case is when the node we are trying to delete is the front of the list. If this is the case, you simply want to make the head attribute point to the next node.

 

Challenge

One operation that we have not implemented so far is pop. Pop takes an index, and removes the item at that index from the list. Write a method called pop, which takes an integer as a parameter. It should remove the node stored in that location from the list.

Submission

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

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

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

Notes