Java Collection(一)：Array-based Data Structure

2018-03-20

Brief

底层数据结构基于数组的集合，可以通过“下标”快速定位到指定元素；数组的增、删元素时需要进行数据移动拷贝；数据扩容时，需要进行Arrays.copyOf()。

Basic Opertions

Indexing:

  • An obvious choice for implementing the list ADT is to use an array, A, where A[i] stores (a reference to) the element with index i.
  • With a representation based on an array A, the get(i) and set(i, e) methods are easy to implement by accessing A[i] (assuming i is a legitimate index).

Indexing

Insertion:

  • In an operation add(i, o), we need to make room for the new element by shifting forward the n - i elements A[i], …, A[n - 1]
  • In the worst case (i = 0), this takes O(n) time

In an add operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one.

Indexing

Removal:

  • In an operation remove(i), we need to fill the hole left by the removed element by shifting backward the n - i - 1 elements A[i + 1], …, A[n - 1]
  • In the worst case (i = 0), this takes O(n) time

Categories

  • Fixed-Array : Array
  • Resizable-Array: ArrayList, Vector(thread-safe)
  • Immutable-Array: ImmutableList(Google Guaua)
Collection thread-safe grow rule init size
ArrayList not 50% of its size 10
Vector yes doubles its array size 10
ImmutableList yes no

通过Collections.synchronizedCollection()可以将ArrayList转换为线程安全的List。

Performance

In an array-based implementation of a dynamic list:

  • The space used by the data structure is O(n)
  • Indexing the element at i takes O(1) time
  • add and remove run in O(n) time in the worst case

Appendix

  • System.arraycopy() VS Arrays.copyOf(): The difference is that Arrays.copyOf does not only copy elements, it also creates a new array. System.arrayCopy copies into an existing array.
  • 为什么concurrent包下没有ArrayList的实现？
▲