Java Reference
In-Depth Information
INSERT 23:
13
12
20
8
3
13
12
20
8
3
0
1
2
3
4
5
0
1
2
3
4
5
(A)
(B)
23
13
12
20
8
3
0
1
2
3
4
5
(C)
Figure4.3
Inserting an element at the head of an array-based list requires shift-
ing all existing elements in the array by one position toward the tail. (a) A list
containing five elements before inserting an element with value 23. (b) The list
after shifting all existing elements one position to the right. (c) The list after 23
has been inserted in array position 0.
Shading indicates the unused part of the
array.
maintain this property. Inserting or removing elements at the tail of the list is easy,
so the
append
operation takes (1) time. But if we wish to insert an element at
the head of the list, all elements currently in the list must shift one position toward
the tail to make room, as illustrated by Figure 4.3. This process takes (n) time
if there are n elements already in the list. If we wish to insert at position i within
a list of n elements, then ni elements must shift toward the tail. Removing an
element from the head of the list is similar in that all remaining elements must shift
toward the head by one position to fill in the gap. To remove the element at position
i, ni 1 elements must shift toward the head. In the average case, insertion or
removal requires moving half of the elements, which is (n).
Most of the other member functions for Class
AList
simply access the current
list element or move the current position. Such operations all require (1) time.
Aside from
insert
and
remove
, the only other operations that might require
more than constant time are the constructor, the destructor, and
clear
. These
three member functions each make use of the system free-store operation
new
. As
discussed further in Section 4.1.2, system free-store operations can be expensive.
4.1.2
Linked Lists
The second traditional approach to implementing lists makes use of pointers and is
usually called a linked list. The linked list uses dynamic memory allocation, that
is, it allocates memory for new list elements as needed.
A linked list is made up of a series of objects, called the nodes of the list.
Because a list node is a distinct object (as opposed to simply a cell in an array), it is
good practice to make a separate list node class. An additional benefit to creating a
