CS 214 Lab 11: Self-Referential (Linked) Structures

We have seen the Array construct of our various languages, which allows a sequence of values (of the same type) to be stored in a single container. The memory allocated to this container is contiguous, meaning that any values in the array are stored in adjacent memory locations. This contiguous storage allows an index / subscript operation to be performed in O(1) time, but it is a drawback when one wishes to insert (or delete) a value at the beginning or middle of the sequence, since extensive copying (O(N) assignments) is required to open (or close) the space to store the value.

Non-Contiguous Storage. This week, we examine the list construct of our various languages. Lists differ from arrays in being made up of nodes that are linked together using pointers. This linked structure eliminates the adjacency of contiguous storage, making it possible to perform insertions and deletions in constant time (O(1) assignments). To define a node type, the definition must contain a data member (or field) that is a pointer to a node. That is, the type-name must be used to define the fields of the type being defined! Since the definition of a node type refers to itself, such a node is called a self-referential type.

As before, we will work on the same problem in each of our four languages, to compare their particular features. This week's exercise will involve three steps:

1. Examining how a list is defined in a given language. For simplicity, we will define a list of integers.
2. Writing a function to display a list. The specification of this problem is:

      Receive: aList, a list;
               out, an output channel (stream, buffer, etc.).
      Output: the values in aList, to out.  

3. Writing a function to find the maximum value in a list. The specification of this problem is:

      Receive: aList, a list.
      Precondition: aList is not empty.
      Return: the maximum value in aList.  

Also as usual, we will introduce the exercise using Java, after which you will apply similar techiques to solve the problem in the other three languages. Also as usual, the order in which you do the three exercises does not matter.

Begin by making a new directory for this lab exercise and changing directory to that new directory.

1. Java Introduction
2. Ada Exercise
3. Clojure Exercise
4. Ruby Exercise

Turn in. Each of the four parts requires you to create files containing source code and execution traces. When you have completed them, use cat to create a single file that contains all of your results:

   cat java/script.java ada/script.ada clojure/script.clojure ruby/script.ruby > lab11-results

   cp lab11-results /home/cs/214/current/yourUserName

Calvin > CS > 214 > Labs > 11