Carnegie Mellon University Website Home Page
Spring 2018

15-121 Homework 5: Implementing Interfaces (Lists & Queues) - Due 3/26 at midnight

Download and unzip, which contains all the files you will need for this assignment. You will be writing code in the file until you get the base game working. The goals of this assignment are:

  • to familiarize you with how to write a class that implements an interface (with an eye toward efficiency of the operations)
  • to implement and use a queue
  • to get some additional practice with linked lists, as you will be implementing both interfaces with a linked list

In addition to the code files, I have also provided you with documentation files (created with javadoc). These can be found in

Note: You will be graded in part on your coding style. Your code should be easy to read, well organized, and concise. You should avoid duplicate code.

Background: The Game

This assignment involves a computer game called Snakes. In Snakes, two players each control a snake to move around in a grid in which there are small green pellets of food. The two players race to eat as many pellets as possible. When all of the pellets are gone, the player who has managed to eat the most pellets is the winner.

The Interfaces

MyList implements both the SimpleList and SimpleQueue interfaces. Recall that a class can implement more than one Interface. Since I want you to get additional practice with linked lists, you will use a linked list as the underlying data structure and implementation. As a result, you will likely refer to (and use) code that we developed in class for MyLinkedList as well as the code you wrote in the last assignment. This is perfectly fine, but some of that code will need to be adapted for the methods that must be implemented in the SimpleList and SimpleQueue interfaces, given the specifications provided.

As an example, in order for the add operation in SimpleList and the enqueue operation in SimpleQueue to be implemented efficiently, we will need to keep (and update) a last reference, in addition to the start (now called first) reference we maintained for the singly linked list that we wrote in MyLinkedList. Note that last must be updated appropriately and consistently in any methods that could possibly alter it. Doing so allows the last ListNode to be accessible in constant time!

In general, I would encourage you to look at the Java API as you think about this assignment. In particular, the List, Iterable, and Iterator interfaces.


When a class implements an interface, it must implement all of the methods that the interface specifies. So the first thing to do will be to create "stub" public methods (since interface methods are default public access) with the appropriate headers copy pasted from the interfaces into the class file. I have done this for you already.

Since both SimpleList and SimpleQueue extend Iterable, implementing these interfaces requires that you provide a method that returns an Iterator that iterates over the collection. This is most easily done with a private inner class that implements all of the Iterator methods in a manner similar to the code from Lecture 13. Feel free to throw the same UnsupportedOperationException for the Iterator remove method, as remove is not required for Snakes.

All the queue methods should run in constant time (hence the need for a last reference). All but the list remove method should run in constant time (again, hence the need for the last reference). As you implement the methods in MyList you can test them with the main method provided in that class. You will likely want to add additional test code to what I have provided. :-)

Do not compile and run the SnakesGame class until you have all the methods and the iterator written and tested in isolation in MyList. Since all the SimpleList and SimpleQueue methods are used by SnakesGame, they all need to be working before SnakesGame will work. Also, you should make sure all the non-Iterator methods work correctly before implementing the Iterator. You should also test the Iterator by creating a for-each loop inside the main method before going on to run SnakesGame.

Modifying the game code

Once you have the basic game working, you need to modify the game code (you have to determine where) in the following ways:

  • grow the snake by one cell each time it eats a pellet
  • wrap the snake around to the other side of the grid once it reaches an edge (top/bottom/left/right)
  • determine if a snake can no longer move and force a win for the other player


The following bonus points are available on this assignment:

  • 5 point bonus: implement the MyList class with a doubly linked list
  • additional 2 point bonus: correctly implement the remove method of the Iterator interface (look at the Iterator API to determine what it needs to do). Note 1, you have to have the doubly linked list implementation already working in order to attempt this bonus. Note 2, all functionality as specified in the API must be implemented to earn this bonus.
  • if you want to make your own modification to the game that is not in the list above, come to my office to discuss

Note: you should only attempt the bonus once you have all the other methods working correctly!

Submitting Your Work

When you have completed the assignment and tested your code thoroughly, create a .zip file with your work (including and any other files that you modified if you got the bonus working). Name the zip file "your-andrew-id".zip and upload it to the HW5 folder on Box.

Make sure to keep a copy of your work just in case!