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

to the next cell using the reference stored in field next . We proceed cell-wise
until we eventually find the element, or we reach the tail cell of the list that
has its next field set to null .

Program 7.3 Checking whether an element belongs to the list by traversing
it
static boolean belongTo( int element , List l i s t )

{ while (list!= null )
{ if (element==list . container)
return true ;
list=list .next;
return false ;

}

The time complexity of searching in a linked list of n cells is therefore linear
( O ( n ) using the big Oh-notation) since we need to fully explore the list to
report that it is not inside. Note that since Java is pass-by-value only (with a
pass-by-reference for non-primitive objects), at the end of calling static function
belongTo the reference of list remains unchanged.

7.2.5 Linked lists storing String elements

List can store arbitrary types of objects. For example, the list declaration of
storing String inside an individual cell is given below:

Program 7.4 Linked list storing String elements
class ListString
{ String name;
ListString next; // reference

// Constructor
ListString(String tname, ListString tail )
{ this .name=tname; this .next=tail; }

static boolean isEmpty(ListString list )

{ return (list== null ); }

static String head( ListString list )

{ return list .name; }

static ListString tail (ListString list )

{ return list .next; }

}