I$$d like to ask an expert

The LISP language, created in $1958$by John McCarthy $($MIT$),$implements linked lists in a very elegant way. You will explore a Java analog in this additional part. Conceptually, the tail of a list $--$that is$,$the list with its head node removed $--$is also a list. The tail of that list is again a list and so on$,$until you reach the empty list.

Here is a tentative Java interface for such a list:

$/**$A list of entries of some number of $($homogenously$)$typed elements $\{$@code A$\}.*/$public interface LispList $\{//$a "static factory" method for producing an empty list instance static boolean empty$()\{$return new EmptyList$()$; $\}$boolean isEmpty$()$; String head$()$; $//$NOTE: unlike your BST above, our LispList can only hold Strings LispList tail$()$; $//...\}$

There are two kinds$/$varieties of a LispList, empty and non$-$empty lists:

public class EmptyList implements LispList $\{...\}$public class NonEmptyList implements LispList $\{...\}$

These classes are pretty trivial. The EmptyList has no instance variables$/$fields$.$Its head and tail methods simply throw an UnsupportedOperationException and its empty method returns true. The NonEmptyList class will need to store fields to track the head and tail.

Here is one way of making a LISP list with three elements:

LispList list $=$new NonEmptyList$("$A$",$new NonEmptyList$("$B$",$new NonEmptyList$("$C$",$new EmptyList$())))$;

This is a bit tedious, and it is a good idea to supply a convenience method, cons that calls the constructor, as well a static variable Nil that is an instance of the empty list.

Then the list construction code becomes:

$//$toString will ideally give: $[$A$,$B$,$C$]$LispList list $=$LispList$.$empty$().$cons$("$C$").$cons$("$B$").$cons$("$A$")$;

breaking down what's going on above:

We'll look at the construction of the above list:

So$,$starting with the empty list we get:

new EmptyList$()$

A new list is constructed with C as the head and Nil as the tail:

$[$C$]->$EmptyList $//"$high level view" new LispList$("$C$",$new EmptyList$())//"$structure view"

Next, a new list is constructed with B as the head and the previous list:

$[$B$]->[$C$]->$Nil new LispList$("$B$",$new LispList$("$C$",$new EmptyList$()))$

Next the A gets tacked on the front, etc.

Some exercises

These should all be done in a separate file called LispListExercises and the methods should all be marked static. Use recursion for all of these $--$write the unit tests as you work through these.

method: length

Takes a LispList as a parameter and computes and returns the length of the list.

length$([$A$,$B$,$C$])//3$

method: contains

Takes a LispList and some String key and and returns true only if key appears in the list; false otherwise.

contains$([$A$,$B$,$C$],"$B$")//$true

method: delete

Takes a LispList as well as the item to be removed and returns a LispList with the item removed.

delete$([$A$,$B$,$C$],"$B$")//$returned list: $[$A$,$C$]$delete$([$A$,$B$,$C$],"$D$")//$returned list: $[$A$,$B$,$C$]$

method: cat

Takes two LispLists and appends them together and returns the resulting $($concatenated$)$list$.$

cat$([$A$,$B$],[$C$,$D$])//[$A$,$B$,$C$,$D$]$cat$([],[$X$,$Y$])//[$X$,$Y$]$

method: merge

Takes two LispLists and alternates between the elements, adding the remainder to the end.

merge$([$A$,$C$,$E$],[$B$,$D$,$F$])//[$A$,$B$,$C$,$D$,$E$,$F$]$merge$([$A$,$B$],[1,2,3,4])//[$A$,1,$B$,2,3,4]$

$($note: the numbers in the second example will just be strings, i$.$e$.$: $"1")$

in java