我們知道ArrayList是基于Array的，所以它擁有Array的優(yōu)點，適用于按索引取值的場合，但是它不適合插入數(shù)據(jù)和刪除數(shù)據(jù)，因為每插入或刪除一次就會產(chǎn)生一次大量數(shù)組內(nèi)容Copy的操作。而LinkedList正好與ArrayList相反，它比較適合與插入刪除操作，不適合于索引取值，因為它不可以像數(shù)組一樣根據(jù)索引值直接就可以定位元素的地址，而需要從頭至尾一個一個的來數(shù)位置。
那么有沒有一種數(shù)據(jù)結(jié)構(gòu)既擁有數(shù)據(jù)索引取值快速的特性，又擁有快速刪除元素的優(yōu)點呢？當(dāng)然有，下面我介紹的就是其中的一種方式，我稱之為無序數(shù)組（概念可能與數(shù)組的概念有些沖突，因為數(shù)組本身是有序的），這種數(shù)組包裝方法是基于數(shù)組的，所以擁有數(shù)組快速索引取值的特點；并且在刪除元素的時候并不移動（Copy）數(shù)組內(nèi)部元素，所以刪除元素的時候速度很快。缺點就是損失了數(shù)組的有序性，同時因為該數(shù)組是無序的，所以沒有必要提供數(shù)據(jù)中間插入操作，只可以向數(shù)據(jù)的末尾添加數(shù)據(jù)。
這個數(shù)據(jù)結(jié)構(gòu)的設(shè)計是基于效率的，所以它只適合于對數(shù)組的按索引取值和隨機刪除元素的效率要求都比較高，同時對數(shù)組的有序性（這里的有序性不是指數(shù)組元素的排序順序，而是指數(shù)組元素的索引順序）沒有任何要求的場合。
這個數(shù)據(jù)結(jié)構(gòu)的一個使用示例場合就是隨機取數(shù)據(jù)。可以用該數(shù)組存儲數(shù)據(jù)源，然后隨機生成一個索引，并將該索引對應(yīng)的元素remove掉。而且還能保證數(shù)據(jù)不被重復(fù)讀取。
下面提供的示例代碼抽取了這個數(shù)組的最基本功能，很清晰，沒有什么需要解釋的地方。導(dǎo)致數(shù)組無序和快速刪除的根源就在于 remove(int index) 方法中，大家自己看吧。
1 public class NoOrderArray
2 {
3 private Object[] values = null;
4
5 private int size = 0;
6
7 /**
8 * 數(shù)組 NoOrderArray 的構(gòu)造函數(shù)。 <br>
9 *
10 * @param capacity int - 數(shù)組的初始容量。
11 */
12 public NoOrderArray(int capacity)
13 {
14 if (capacity < 0)
15 throw new IllegalArgumentException("Illegal Capacity: " + capacity);
16
17 values = new Object[capacity];
18 }
19
20 /**
21 * 數(shù)組 NoOrderArray 的構(gòu)造函數(shù)，初始容量為 8.<br>
22 */
23 public NoOrderArray()
24 {
25 this(10);
26 }
27
28 /**
29 * 設(shè)定數(shù)組的容量大小，使其至少滿足 minCapacity 所指的大小。 <br>
30 *
31 * @param minCapacity int - 新的容量值。
32 */
33 public void ensureCapacity(int minCapacity)
34 {
35 int oldCapacity = values.length;
36
37 if (minCapacity > oldCapacity)
38 {
39 Object[] oldValues = values;
40
41 int newCapacity = (oldCapacity * 3) / 2 + 1;
42
43 if (newCapacity < minCapacity)
44 newCapacity = minCapacity;
45
46 values = new Object[newCapacity];
47
48 System.arraycopy(oldValues, 0, values, 0, size);
49 }
50 }
51
52 /**
53 * 向數(shù)組 NoOrderArray 中添加元素內(nèi)容。 <br>
54 *
55 * @param value - 添加的內(nèi)容。
56 */
57 public void add(Object value)
58 {
59 ensureCapacity(size + 1);
60
61 values[size] = value;
62
63 size ++;
64 }
65
66 /**
67 * 清除數(shù)組 NoOrderArray 中的全部元素。 <br>
68 */
69 public void clear()
70 {
71 // 釋放內(nèi)存
72 for (int i = 0; i < size; i ++)
73 values[i] = null;
74
75 size = 0;
76 }
77
78 /**
79 * 返回數(shù)組 NoOrderArray 中指定索引的元素。 <br>
80 *
81 * @param index int - 索引值。
82 *
83 * @return Object - 對應(yīng)的元素。
84 */
85 public Object get(int index)
86 {
87 if (index >= size || index < 0)
88 throw new IndexOutOfBoundsException("Index out of bounds.");
89
90 return values[index];
91 }
92
93 /**
94 * 判斷當(dāng)前 NoOrderArray 數(shù)組是否為空。 <br>
95 *
96 * @return boolean - 如果為空返回 <code>true</code>.
97 */
98 public boolean isEmpty()
99 {
100 return (size == 0);
101 }
102
103 /**
104 * 移除 NoOrderArray 數(shù)組中指定位置的元素。 <br>
105 *
106 * @param index int - 索引值。
107 *
108 * @return Object - 被移除的元素。
109 */
110 public Object remove(int index)
111 {
112 if (index >= size || index < 0)
113 throw new IndexOutOfBoundsException("Index out of bounds.");
114
115 Object value = values[index];
116
117 if (index != size - 1)
118 {
119 // 將數(shù)組最后一個值補充到被移除的位置。
120 values[index] = values[size - 1];
121 }
122 values[size - 1] = null; // 防止該位置永久持有對象的引用
123 size --;
124
125 return value;
126 }
127
128 /**
129 * 判斷指定的數(shù)據(jù)是否在 NoOrderArray 數(shù)組中。 <br>
130 *
131 * @param value Object - 需要判斷的數(shù)據(jù)。
132 *
133 * @return boolean - 如果包含返回 <code>true</code>.
134 */
135 public boolean contains(Object value)
136 {
137 if (value == null)
138 {
139 for (int i = 0; i < size; i ++)
140 if (values[i] == null)
141 return true;
142 }
143 else
144 {
145 for (int i = 0; i < size; i ++)
146 if (value.equals(values[i]))
147 return true;
148 }
149
150 return false;
151 }
152
153 /**
154 * 返回當(dāng)前數(shù)組的大小。 <br>
155 *
156 * @return int - 當(dāng)前數(shù)組的大小。
157 */
158 public int size()
159 {
160 return size;
161 }
162
163 /*
164 * (non-Javadoc)
165 *
166 * @see java.lang.Object#toString()
167 */
168 public String toString()
169 {
170 StringBuffer buffer = new StringBuffer();
171
172 buffer.append('[');
173
174 for (int index = 0; index < size; index ++)
175 {
176 Object value = values[index];
177
178 if (index > 0)
179 buffer.append(',');
180
181 buffer.append(value);
182 }
183
184 buffer.append(']');
185
186 return buffer.toString();
187 }
188
189 /**
190 * @param args
191 */
192 public static void main(String[] args)
193 {
194 // TODO 自動生成方法存根
195 }
196 }