Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 73

top

36 15 52 23

curr points to (the node containing) 36 . Since curr is not null , it is set to point to
whatever 36 is pointing to, that is, (the node containing) 15 .

• Initially,

while condition is tested again. Since curr is not null , curr = curr.next is executed,
setting curr to point to whatever 15 is pointing to, that is, 52 .

• The

while condition is tested again. Since curr is not null , curr = curr.next is executed,
setting curr to point to whatever 52 is pointing to, that is, 23 .

• The

while condition is tested again. Since curr is not null , curr = curr.next is executed,
setting curr to point to whatever 23 is pointing to, that is, null .

• The

while condition is tested again. Since curr is null , the while loop is no longer executed.
Note that each time curr is not null , we enter the while loop. But the number of times that curr is not null is
exactly the same as the number of items in the list. So, in order to count the number of items in the list, we just have to
count how many times the while body is executed.
To do this, we use a counter initialized to 0 and increment it by 1 inside the while loop. We can now write the
function as follows (we call it length ):

• The

public static int length(Node top) {
int n = 0;
Node curr = top;
while (curr != null) {
n++;
curr = curr.next;
}
return n;
}

Note that if the list is empty, curr will be null the first time, and the while loop will not be executed. The function
will return 0 , the correct result.
Strictly speaking, the variable curr is not necessary. The function will work fine if we omit curr and replace curr
by top in the function. At the end of the execution of the function, top will be null .
You may be worried that you have lost access to the list, but do not be. Remember that top in length is a copy of
whatever variable ( head , say) is pointing to the list in the calling function. Changing top has no effect whatsoever on
head . When length returns, head is still pointing to the first item in the list.

3.2.2 Searching a Linked List
Another common operation is to search a linked list for a given item. For example, given the following list, we may
want to search for the number 52 :

top

36 15 52 23