Lab 1: Linked Lists (4 Points)

Chris Tralie

Overview / Logistics

The purpose of this lab is to get you used to programming with objects in python in the service of one of the most important data structures of all time: a linked list. A linked list has many uses, but at the end of the lab, students will use the linked list they made to implement the stack ADT

Learning Objectives

  • Use python OOP to implement a data structure
  • Implement linked list operations
  • Practice telling the difference between an abstract data type (ADT) and a data structure

What To Submit

When you are finished, submit linkedlist.py to canvas

Programming Tasks

Click here to download the starter code for this lab.

Traversing a linked list is just a matter of chasing some arrows, starting at the head (though we have to be careful maintaining these arrows properly). In the worst case, the element we want to find/remove/change is at the end, or it isn't there at all, in which case we have to walk through all N link nodes.

I've provided implementations of pop_front to remove the first node and return its object, as well as __str__ to traverse the list and turn it into a string.

Task 1: __contains__

Your Task: Fill in the __contains__ method that returns True if a particular object is in at least one of the nodes, or False otherwise.

Task 2: push_front

Your Task: Fill in a method that adds a LinkedNode object to the front of the list that wraps around the data we're trying to add. To do this, we just make the element we want to add the new head

Specifically, after making a new linked node called new, the steps are

  1. new.next = head
  2. head = new

NOTE: A common pitfall here is to do these two steps in the opposite order, but this ends up creating an infinite loop from the head to itself, disconnecting the rest of the list!

Task 3: remove

Your Task: Fill in a method to remove the first node that contains a particular object, or do nothing if none of the nodes contain that object.

This is a little bit trickier, but the basics are the same. We have to find the element and then reassign pointers to circumvent the element we're trying to remove (assuming there's a garbag collector around to clean up the orphaned node). Let's assume that it's actually there (otherwise, we just get to the end and don't do anything). Let's also assume that it's not at the beginning (I've handled the case where it's at the beginning using pop_front(), which I've already provided). Then the picture below depics what has to happen: find the node right before the node we want to remove, and then set its pointer to jump past:

class

If all of the methods in your linkedlist class work properly and you run the main in linkedlist.py, you should get the following outputs indicated in comments below:

Task 4: Stack ADT

A stack abstract data type is a so-called "last in first out" collection, where the last thing that we push (add) onto the top of the stack is the first thing that we pop (remove) from the top of the stack. The picture below shows an example:

A linked list turns out to be an excellent data structure to use to implement a stack.

Your Task: Fill in the push and pop methods in stack.py to push and pop from the stack, using the list LinkedList object that belongs to the Stack class. If you do this properly, you should have to write very little code! You can use all of the hard work that we've already done in the LinkedList class