Java Reference
In-Depth Information
The efficiency of a sequential search of a chain is really the same as that of a sequential search of an
array. In the best case, the desired item will be first in the chain. Thus, at best the search will be
O(1), since you will have made only one comparison. In the worst case, you will search the entire
chain, making
n
comparisons for a chain of
n
nodes. Therefore, the sequential search in the worst
case is O(
n
). Typically, you will look at about half of the nodes in the chain. Thus, the average-case
search is O(
n
/
2), which is just O(
n
).
Note:
The time efficiency of a sequential search of a chain of linked nodes
Best case:
O(1)
Wor st ca se:
O(
n
)
Average case:
O(
n
)
We now search a chain whose data is sorted. Such a chain would occur in a linked implementation
of the ADT sorted list.
Searching a chain of linked nodes whose data is sorted is similar to sequentially searching a sorted
array, as described in Segment 18.8. Here, we incorporate that logic into the following implementa-
tion of
contains
:
public boolean
contains(T anEntry)
{
Node currentNode = firstNode;
while
( (currentNode !=
null
) &&
(anEntry.compareTo(currentNode.getData()) > 0) )
{
currentNode = currentNode.getNextNode();
}
// end while
return
(currentNode !=
null
) &&
anEntry.equals(currentNode.getData());
}
// end contains
The method traverses the chain until it either reaches a node that could contain the desired
object or examines all nodes without success. Following the traversal, a final test is necessary to
draw a conclusion.
A binary search of an array looks first at the element that is at or near the middle of the array. It is easy
to determine the index
mid
of this element by computing
first
+
(last
-
first)
/
2
, where
first
and
last
are the indices of the first and last elements, respectively, in the array. Accessing this middle
element is also easy: For an array
a
, it is simply
a[mid]
.
Now consider searching a chain of linked nodes, such as the one you saw earlier in
Figure 18-7, whose nodes are sorted. How would you access the entry in the middle node?
Since this chain has only three nodes, you can get to the middle node quickly, but what if the
