Java Reference
In-Depth Information
An array list is implemented using an array.
Key
Point
An array is a fixed-size data structure. Once an array is created, its size cannot be changed.
Nevertheless, you can still use arrays to implement dynamic data structures. The trick is to
create a larger new array to replace the current array, if the current array cannot hold new
elements in the list.
Initially, an array, say
data
of
E[]
type, is created with a default size. When inserting a
new element into the array, first make sure that there is enough room in the array. If not, cre-
ate a new array twice as large as the current one. Copy the elements from the current array to
the new array. The new array now becomes the current array. Before inserting a new element
at a specified index, shift all the elements after the index to the right and increase the list size
by
1
, as shown in Figure 24.4.
01
…
…
Before inserting
e
at insertion point
i
ii
+1
k
-1
k
k +
1
e
0
e
1
…
…
e
i
e
k
e
i
-1
e
i
+1
e
k
-1
data.length - 1
e
Insertion point
…shift…
01
…
After inserting
e
at insertion point
i
,
list size is
incremented by 1
…
ii
+1
i
+2
k
+1
k
…
e
0
e
1
…
e
e
i
-1
e
i
e
i
+1
e
k
-1
e
k
e
inserted here
data.length - 1
F
IGURE
24.4
Inserting a new element into the array requires that all the elements after the
insertion point be shifted one position to the right, so that the new element can be inserted at
the insertion point.
Note
The data array is of type
E[]
. Each cell in the array actually stores the reference of an object.
To remove an element at a specified index, shift all the elements after the index to the left
by one position and decrease the list size by
1
, as shown in Figure 24.5.
…
…
…
0
1
ii
+1
k
- 1
k
Before deleting the
element at index
i
e
0
e
1
…
e
i
-1
e
i
e
i
+1
e
k
-1
e
k
Delete this element
...shift...
data.length - 1
…
…
0
1
i
k
- 2
e
k
-1
k
- 1
k
After deleting the
element, list size is
decremented by 1
e
0
e
1
…
e
i
-1
e
i
+1
…
e
k
data.length - 1
F
IGURE
24.5
Deleting an element from the array requires that all the elements after the
deletion point be shifted one position to the left.
MyArrayList
uses an array to implement
MyAbstractList
, as shown in Figure 24.6. Its
implementation is given in Listing 24.3.
Search WWH ::
Custom Search