ArrayList
底層實現是數組，訪問元素效率高 (查詢快，插入、修改、刪除元素慢)
與LinkedList相比，它效率高，但線程不安全。
ArrayList數組是一個可變數組，可以存取包括null在內的所有元素
- 每個ArrayList實例都有一個容量，該容量是指用來存儲列表元素的數組的大小
- 隨著向ArrayList中不斷增加元素，其容量自動增長
- 在添加大量元素前，應用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這樣可以減少遞增式再分配的數量。
- 所以如果我們明確所插入元素的多少，最好指定一個初始容量值，避免過多進行擴容操作而浪費時間、效率
- 源碼分析
底層使用數組實現
|
1
|
transient Object[] elementData; |
構造方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData;private int size; // 構造一個空列表public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ; } // 構造一個指定初始容量的空列表public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } // 構造一個指定Collection元素的列表，這些元素按照Connection元素的迭代返回順序進行排列public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } |
存儲
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
// 在列表的指定位置的元素用element替代，并且返回該位置原來的元素public E set(int index, E element) { rangeCheck(index); // 檢查數組容量，拋出：IndexOutOfBoundsException E oldValue = elementData(index); elementData[index] = element; return oldValue; } // 在列表的尾部添加指定元素public boolean add(E e) { ensureCapacityInternal(size + 1); // 數組擴容 elementData[size++] = e; return true; } // 在列表的指定位置添加元素public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! // src:源數組,srcPro:源數組中的起始位置 // dest:目標數組，destPost:目標數組的起始位置，length:要復制的數組元素數量 // 將當前位于該位置的元素以及所有后續元素后移一個位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 用element替換index位置的元素 elementData[index] = element; size++; } // 在列表的尾部添加Connection中的元素，元素順序按照Connection迭代器返回的順序public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); // 轉化為一個數組 int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount // Increments modCount!! System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } // 在列表的指定位置添加Connection中的元素，元素順序按照Connection迭代器返回的順序public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; } |
讀取
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
// 移除此列表指定位置上的元素public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } // 移除此列表中的某個元素public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } |
數組擴容
每當向數組中添加元素時，都需要去檢查添加元素后元素的個數是否超出當前數組的長度，如果超出，數組將會進行擴容，以滿足添加數據的需求。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } |
手寫ArrayList
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
public class MyArrayList /*implements List<E>*/{ private transient Object[] elementData; private int size; //元素個數 public MyArrayList(){ this(10); } public MyArrayList(int initialCapacity) { if (initialCapacity<0) { try { throw new Exception(); } catch (Exception e) { e.printStackTrace(); } } elementData = new Object[initialCapacity]; } public int size() { return size; } public boolean isEmpty(){ return size == 0; } //根據index刪掉對象 public void remove(int index) throws Exception { rangeCheck(index); int numMoved = size-index-1; if (numMoved > 0) { System.arraycopy(elementData, index+1, elementData, index, numMoved); } elementData[--size] = null; } //刪掉對象 public boolean remove(Object obj) throws Exception { for (int i = 0; i < size; i++) { if (get(i).equals(obj)) { remove(i); } return true; } return true; } //修改元素 public Object set(int index , Object obj ) throws Exception{ rangeCheck(index); Object oldValue = elementData[index]; elementData[index] = obj; return oldValue; } //在指定位置插入元素 public void add(int index,Object obj) throws Exception { rangeCheck(index); ensureCapacity(); System.arraycopy(elementData, index, elementData, index+1, size-index); elementData[index] = obj; size ++; } public void add(Object object) { ensureCapacity(); /*elementData[size] = object; size ++;*/ elementData[size++] = object; //先賦值，后自增 } public Object get(int index) throws Exception { rangeCheck(index); return elementData[index]; } public void rangeCheck(int index) throws Exception { if (index<0 || index >=size) { throw new Exception(); } } //擴容 public void ensureCapacity() { //數組擴容和內容拷貝 if (size==elementData.length) { //elementData = new Object[size*2+1]; 這么寫原來數組里的內容丟失 Object[] newArray = new Object[size*2+1]; //拷貝數組里的內容 /*for (int i = 0; i < newArray.length; i++) { newArray[i] = elementData[i]; }*/ System.arraycopy(elementData, 0, newArray, 0, elementData.length); elementData = newArray; } } // 測試 public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(3); myArrayList.add("111"); myArrayList.add("222"); myArrayList.add("333"); myArrayList.add("444"); myArrayList.add("555"); try { myArrayList.remove(2); myArrayList.add(3, "新值"); myArrayList.set(1, "修改"); } catch (Exception e1) { // TODO Auto-generated catch block e1.printStackTrace(); } System.out.println(myArrayList.size()); for (int i = 0; i < myArrayList.size(); i++) { try { System.out.println(myArrayList.get(i)); } catch (Exception e) { e.printStackTrace(); } } }} |
原文鏈接：https://segmentfault.com/a/1190000015015669
