Java Reference
In-Depth Information
4.26
Searching a bag for a given entry.
The method
contains
, given in Segment 3.17 of Chapter 3,
searches a chain of nodes for a given entry:
public boolean
contains(T anEntry)
{
boolean
found =
false
;
Node currentNode = firstNode;
while
(!found && (currentNode !=
null
))
{
if
(anEntry.equals(currentNode.data))
found =
true
;
else
currentNode = currentNode.next;
}
// end while
return
found;
}
// end contains
The best case occurs when the desired entry is in the first node of the chain of nodes. Since the
method has a reference to the chain's first node, no traversal is needed. Thus, the method is O(1) in
this case.
In the worst case, the traversal of the chain continues to the last node. The operation is O(
n
) in
this case. Finally, in the typical, or average, case, the traversal would examine
n
/ 2 nodes, making
it an O(
n
) operation.
Note:
Searching a bag that has a linked implementation
Searching for an item that is at the beginning of a chain of nodes is an O(1) operation. It takes
the least time of any search of the chain, making this case the best case. If the item is in the
last node of the chain, searching for it is O(
n
). This search takes the most time among the
searches for an item that is in one of the nodes, and so this is the worst case. The actual time
required to find an entry in a chain of nodes depends on which node contains it.
Question 12
What is the Big Oh of the method
contains
when it searches for an entry that
is not in the bag? Assume that a chain of linked nodes represents the bag.
Question 13
What is the Big Oh of the bag's
remove
methods? Assume that a chain of linked
nodes represents the bag, and use an argument similar to the one you just made for
contains
.
Question 14
Repeat Question 13, but instead analyze the method
getFrequencyOf
.
Question 15
Repeat Question 13, but instead analyze the method
toArray
.
Using Big Oh notation, Figure 4-11 summarizes the time complexities of the operations of the ADT
bag for the implementations that use a fixed-size array and a chain of linked nodes. For some oper-
ations, multiple time requirements indicate the best, worst, and average cases.
