Java Reference
In-Depth Information
685
Table 1 Efficiency of Operations for Arrays and Lists
Operation
Array
List
Random access
O(1)
O(n)
Linear traversal step
O(1)
O(1)
Add/remove an element
O(n)
O(1)
In a linked list, an element can be added or removed in constant time (assuming that
the iterator is already in the right position). A fixed number of node references need
to be modified to add or remove a node, regardless of the size of the list. Using the
big-Oh notation, an operation that requires a bounded amount of time, regardless of
the total number of elements in the structure, is denoted as O(1). Random access in an
array list also takes O(1) time.
An abstract list is an ordered sequence of items that can be traversed sequentially
and that allows for insertion and removal of elements at any position.
Adding or removing an arbitrary element in an array takes O(n) time, where n is the
size of the array list, because on average n/2 elements need to be moved. Random
access in a linked list takes O(n) time because on average n/2 elements need to be
skipped.
An abstract array is an ordered sequence of items with random access via an
integer index.
Table 1
shows this information for arrays and lists.
Why consider abstract types at all? If you implement a particular algorithm, you can
tell what operations you need to carry out on the data structures that your algorithm
manipulates. You can then determine the abstract type that supports those operations
efficiently, without being distracted by implementation details.
For example, suppose you have a sorted collection of items and you want to locate
items using the binary search algorithm (see
Section 14.7
). That algorithm makes a
random access to the middle of the collection, followed by other random accesses.
Thus, fast random access is essential for the algorithm to work correctly. Once you
know that an array supports fast random access and a linked list does not, you then
