Java Reference
In-Depth Information
4.
Typically,
add
must shift array entries to make room for a new entry, and
remove
must shift array entries to avoid
a vacancy within the array. These shifts of data are O(
n
) operations in the worst case. The best case occurs when
the addition or removal is at the end of the array. These operations are O(1).
5.
No. Replacing the entry to be removed with the last entry in a chain would require a traversal of the chain. We
would need references to both the last node and the next-to-last node so that we could delete the last node.
Although we can ignore the last entry in an array, we should shorten the chain by setting the link portion of the
next-to-last node to
null
. Note that having a tail reference does not eliminate the need for a traversal, since we
need but do not have a reference to the next-to-last node. The strategy for an unsorted array-based dictionary
avoids shifting any of the other entries. No shifting is needed in a linked implementation. After locating the node
to delete, you simply adjust either the head reference or the reference in the preceding node.
