Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 101

/ ** Singlylinkedlistnode * /
classLink<E>{
privateEelement; //Valueforthisnode
privateLink<E>next; //Pointertonextnodeinlist

//Constructors
Link(Eit,Link<E>nextval)
{element=it;next=nextval;}
Link(Link<E>nextval){next=nextval;}

Link<E>next(){returnnext;}//Returnnextfield
Link<E>setNext(Link<E>nextval)//Setnextfield
{returnnext=nextval;} //Returnelementfield
Eelement(){returnelement;}//Setelementfield
EsetElement(Eit){returnelement=it;}

}

Figure4.4 A simple singly linked list node implementation.

list node class is that it can be reused by the linked implementations for the stack
and queue data structures presented later in this chapter. Figure 4.4 shows the
implementation for list nodes, called the Link class. Objects in the Link class
contain an element field to store the element value, and a next field to store a
pointer to the next node on the list. The list built from such nodes is called a singly
linked list, or a one-way list, because each list node has a single pointer to the next
node on the list.
The Link class is quite simple. There are two forms for its constructor, one
with an initial element value and one without. Member functions allow the link

user to get or set the element and link fields.
Figure 4.5(a) shows a graphical depiction for a linked list storing four integers.
The value stored in a pointer variable is indicated by an arrow “pointing” to some-
thing. Java uses the special symbol null for a pointer value that points nowhere,
such as for the last list node's next field. A null pointer is indicated graphically
by a diagonal slash through a pointer variable's box. The vertical line between the
nodes labeled 23 and 12 in Figure 4.5(a) indicates the current position (immediately
to the right of this line).
The list's first node is accessed from a pointer named head . To speed access
to the end of the list, and to allow the append method to be performed in constant
time, a pointer named tail is also kept to the last link of the list. The position of
the current element is indicated by another pointer, named curr . Finally, because
there is no simple way to compute the length of the list simply from these three
pointers, the list length must be stored explicitly, and updated by every operation
that modifies the list size. The value cnt stores the length of the list.
Note that LList 's constructor maintains the optional parameter for minimum
list size introduced for Class AList . This is done simply to keep the calls to the