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:

• Add a class to represent one node in the linked list. That class can be a static nested class (but non-static would also work).
• Currently, the position of the snake is given by two variables, currentRow and currentCol. You should delete those variables and replace them with a new variable that points to the head of the snake list. The row and column of the head of the snake will be stored in the head node of that list.
• In the startGame() method, you need to create the initial five-segment snake. The segments are lines up horizontally in the center of the board, with the head on the right. That is, you have to make a list that represents the snake. If the head of the snake is at row=20, column=25, then the second segment of the snake is at row=20, column=24; the third segment is at row=20,column=23; the fourth segment is at row=20,column=22; and the last segment is at row=20,column=21.
• In the draw() method, you have to draw all segments of the snake.
• In the crash() method, you will need to add code to check whether the given row and column are the location of one of the segments of the snake.
• In the moveSnake() method, you have to move the snake. That is, you have to modify the linked list so that it represents the snake in its new position. Also, sometimes, the snake needs to grow. That is, a new segment has to be added at the end. I believe that the easiest approach is to do the following: Do not modify any of the rows/columns in the current list. Instead, just make a new head node and copy newRow and newCol into that node. If you want the snake to grow, leave it at that—the snake has grown by one segment. However, most of the time, you don't want the length of the snake to change, so you need to delete the last node in the list. Note that the segments do not actually move; instead, the snake gets a new head and, most of the time, loses its last segment. For growing the snake, you might just let it grow in every N-th frame for some N; alternatively, you could base the decision whether or not to grow on a random number.

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.