CPSC 225, Spring 2016
Lab 4: Linked Lists

There are two exercises for Lab 4, both dealing with linked lists. In the first, first exercise, you will program a simple linked list of strings. In the second, more substantial exercise, you will use a doubly-linked list to implement the tape in a Turing machine.

Start the lab by creating a new Eclipse project (or folder) named Lab4. You should add the contents of the folder /classes/cs225/Lab4-files to the src folder in your project. There are two things in the folder: a file, SimpleList.java, which you will use for the first exercise; and a folder turing which you will use for the second exercise. Copy each of these things into the src folder of your Lab4 folder. (The turing folder is a "package," and it contains sub-packages. There are a bunch of files in it. Be sure to copy the entire turing folder into your project, not just the contents of the folder. If you want to get a copy of this folder from the Web, download the zip file turing.zip and unzip it.)

The lab is due, as usual, next Thursday.

Warmup Exercise: Simple Linked List

As a warmup, you will implement a simple 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 need to complete the methods named add and find. Read the comments on those methods. The add() method can add 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. Just count the nodes as you traverse the list.

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.

About Turing Machines

In the second exercise for the lab, you will write one part of a program that simulates Turing machines. To do the exercise, you need to know just a little about them. A Turing machine is an abstract computing machine, not a physical device. Turing machines are named after the British mathematician Alan Turing, who invented them to use as a simple model of mechanical computation. Although Turing machines are very simple, they can be used to solve the same set of problems as any computer—or they could if they existed. (In fact, a Turing Machine can solve more problems than any real computer, since it has unlimited memory.)

A Turing machine has several parts:

  1. A "tape" made up of "cells," where each cell can contain one character. Conceptually, the tape is infinite in both directions, but cells that have never been assigned any data are considered to contain a blank character, and only the finite non-blank part of the tape really needs to be represented. The tape is the main memory of the machine.
  2. The "CPU" of the machine, which can move back and forth on the tape, reading and writing characters. The CPU can only see one cell at a time, and it has no memory of previous cells that it has seen. The CPU has one number in its internal memory, which is called its "state." The state can be a non-negative integer, or it can have a special value called the "halt state".
  3. A set of "rules," which constitute the program for the machine. In each step of its computation, the machine applies one rule. Which rule it applies depends on what its current state is and what character it sees in the current cell. The rule has a three-part action that tells the machine what character to write in the current cell (possibly the one that is already there), what state to change to (possibly stay in the same state), and which direction to move (left or right). The machine always moves one cell to the left or to the right when it executes a rule.

When the Turing machine runs, it will start in state number zero and then execute rules until it enters the halt state; if that never happens, then it will run forever. To perform a computation with a Turing machine, you should write the input for the machine on the tape, with the machine placed, by convention, on the right end of the input string. Start the machine in state 0. Start the machine and let it run until it halts. The output of the computation is whatever is written on the tape at that time.

You can find a runnable version of the Turing machine program that you will be working on in the executable jar file /classes/cs225/SimpleTuringMachine.jar. When you run the program, you will find a "Load Example" menu. There are several example machines in the menu. After loading an example, click on "Step" to get the machine to do one step of its computation. Click on "Run" to get the machine to run, rather slowly, until it halts.

Doubly-linked List Exercise: Tape for a Turing Machine

The Turing Machine program is defined in the package named turing. The program is incomplete. The only part that is missing is the code that implements the tape of the Turing Machine, in the file Tape.java, in the package turning.machine. The class has a constructor and four methods, but none of them do anything. Your assignment is to complete this class. You do not have to make any changes to the program outside the the file Tape.java.

A tape should be represented as a doubly linked list. A Turing machine tape consists of a sequence of cells. In the Tape class, each cell of the tape will be represented by one node in the doubly linked list. The item in the node is a single char value, which represents the character in the cell. The node must be linked to the preceding cell and to the following cell in the list. You have to create the class that represents the individual nodes in the list. You can create it as a "private static class" inside Tape.java.

You won't need pointers to the beginning or to the end of the list (although keeping a pointer to the left end of the list would make it easier to implement one of the methods). What you will definitely need is a pointer that points to the "current cell," which will generally be somewhere in the middle of the list. The current cell is the cell where the Turing machine is located; it is the only cell that the Turing machine can "see" at a given time. The list that represents a tape containing the word "Hello", with the current cell being the one that contains the 'e', could look like this:

TM tape as a doubly-linked list.

The cells at the two ends that contain blank characters might or might not be there. Conceptually, the tape contains an infinite number of blanks in both directions, but those blanks don't have to be represented explicitly in the linked list.

When the Turing machine moves left or right, the current cell pointer has to be moved to the preceding node or to the next node in the list. This leads to one problem: Although the tape is conceptually infinite, the list is not actually infinite. If the current cell pointer is at the beginning of the list, and the machine wants to move left, you have to add a new node to the left end of the list before moving. Similarly, for the right end of the list. A newly created node should contain the blank character, ' '. (Note: the blank character is written in Java as a space between two single quotes; there has to be a character between the two single quotes, even if it's a blank.)

To work with the rest of the program, the methods in the Tape class should perform as follows:

The last three methods are not trivial to write! You will have to think carefully about what you want to do with the list, especially when you need to add new nodes. Draw some pictures! It is especially important when constructing the list that all the pointers are set up correctly. Remember that you need pointers pointing in both directions!

Once you have the class written, you can test it by running the programs TestTape and TestTuringMachine in the package turing.test. These programs might help you to discover errors in your implementation. You can also run the actual Turing Machine program, which is called TuringMachineGUI and is in the package turing.

The file Tape.java does not have any Javadoc comments. You should add comments before you submit your work.