CPSC 225, Spring 2019
Lab 5: Linked List Exercises

There are two programs for Lab 5, both dealing with linked lists. In the first exercise, you will program a simple linked list of strings. In the second, more substantial exercise, you will use a linked list to implement a simple "Snake" game.

For this lab, you are encouraged but not required to work with a partner. If you do work with someone, then you and your partner should implement "apples" and scoring for the Snake game, as discussed at the end of this web page.

You will need the two files from the folder /classes/cs225/Lab5-files: SimpleList.java and Snake.java.

The lab is due, as usual, next Tuesday. You should turn in the files SimpleList.java and Snake.java to your homework folder, in a directory named lab5. If you work with a partner, only one of you needs to turn in the programs, but you should make sure that both names are on both programs.

Warmup Exercise: Basic Linked List Operations

As a warmup, you will implement a basic linked list. You will work in the file SimpleList.java. Except for the missing list implementation, this is already a complete program. The work that you will have to do on this exercise is almost identical to examples that you have seen in the book and on the board. Hopefully, typing in the code and getting it to work will help you to understand linked lists.

You will need to define a class to represent a node in the list. You can define a "private static class" inside the file SimpleList.java for that purpose. The items in the list are of type String. Use a global static variable to represent the head of the list. You can just add the following code to the program:

private static class ListNode {
    String item;
    ListNode next;
}

private static ListNode head;

Then, you just need to complete the methods named add and find. Read the comments on those methods. The add() method just adds the word at the head of the list. The find method needs to return the position of the word in the list, if it finds the word. The positions are not stored in the list. You have to count the nodes as you traverse the list, searching for the specified word. (This counting is something new.)

Here is the input/output from a run of my completed version of the program:

Type some words, one to a line.  Press return to end.
? fred
? wilma
? barney
? betty
? pebbles
? 

Your words have been added to the list.
Enter words to be tested, one to a line.  Press return to end,
? bambam
   bambam was not found in the list.
? pebbles
   pebbles was found in the list at postion 1.
? fred
   fred was found in the list at postion 5.
? 

Linked Snake

A "snake" is made up of a series of "segments". (It's more of a millipede than a snake.) Each segment is a circle. The snake's head, at one end, is a different color from the rest of the snake. Initially a snake is short—say, five segments as shown—but it grows as it moves. The snake head can move right, left, up, or down, and the rest of the snake has to follow. In the Snake game, the user controls the direction of motion by pressing the left, right, up, and down arrow keys. The game ends when the user lets the head of the snake crash into the boundary of the game board or into one of the snake's body segments.

Note that the game board is made up rows and columns of squares, where each square is the same size as a snake segment. The snake moves ahead one full square in each frame. This means that the position of a segment can be given by two integers, row and column, that tell which row and column that segment is in.

The file Snake.java is a starting point for the game. It implements the basic animation, but instead of a snake, it only draws a single circle. Your job is to modify the program to implement a multi-segment snake. You are required to represent the snake as a linked list. Each node in the list will correspond to one snake segment. The node should store the row and column numbers for the corresponding segment. You need to work on the following things:

Here's a snake that has been around for a while:

Improvements

The snake game needs improvement. You should certainly make it possible for the user to start a new game after a game ends. That's very easy: Just add some code to the doKeyEvent() method to start a new game when the game is over and user presses the "N" key (which has code KeyCode.N). If you are working on the game alone, that's all you need to do.

If you are working with a partner, you should implement "apples" and scoring. In the usual Snake game, an apple appears from time to time in some square on the board. The snake gets points for eating the apple. However, the apple will disappear after a while if it is not eaten. You could also give points just for staying alive.

Another possibility is to add walls the the board. If the snake crashes into the wall, that's Game Over. You just need to keep an array listing the positions of all the squares that are part of a wall.