Linked Lists - A Concise and Practical Introduction to Programming Algorithms in Java - page 147

Program 7.1 Declaration of a linked list

class List
{ int container ;
List next; }

We now need to provide:

- A proper constructor to initialize various objects of type List ,and

- A few functions implementing the basic operations defined by the abstract
framework of

§ 7.2.2.

Program 7.2 Linked list class with constructor and basic functions
public class List
int container ;
List next ;

// Constructor List(head, tail)
List( int element , List tail )
{ this .container=element;
this .next=tail; }

static boolean isEmpty(List list )
{ if (list== null ) return true ;
else return false ; }

static int head( List l i s t )

{ return list . container ; }

static List tail (List list )

{ return list .next; }

}

In Java, we do not need to explicitly free memory of cells not pointed by any
other variables (meaning unreachable) as the garbage collector takes care of
that. The type of the class List is recursive since it has one field next that
defines a reference to the same type. That is, a recursive type is a data type
with fields that may contain other values of the same type. The recursive type
is self-referential.

7.2.4 Traversing linked lists

To search whether a given query element belongs to the elements stored in
the list or not, we first start the exploration from the head cell of the list and
compare the integer field of the cell with the query. If these integers match then
we successfully have found the element and return true . Otherwise, we chain