1.1 數組為什么需要指定長度
想象一下密浑，如果不指定長度的話，內存空間一次性得開辟多少連續(xù)的空間粗井，系統是不確定的尔破。因為數組是內存中連續(xù)的空間，這樣是為了數組的連續(xù)編號性浇衬。所以到哪里截止就是一個需要確定的問題懒构。
優(yōu)點：快速查詢，所以數組最好應用于索引有語義的情形耘擂。
缺點：不能動態(tài)的開辟空間胆剧，每次開辟空間都得進行一輪復制操作。
1.2 實現動態(tài)數組
動態(tài)數組醉冤，底層數據結構就是數組類秩霍，在java中對應著ArrayList類。我們一起來看看具體的實現原理（部分細節(jié)肯定不能和java標準庫中的完全一樣蚁阳，主要講實現的原理）
1.2.1 添加元素add方法
如下圖铃绒，在數組中size指向的是第一個空位的地址，相當于一個指針螺捐，我們添加元素時颠悬，就是在size所標記的索引進行添加就可以了矮燎。
添加元素代碼如下：
private T[] data;
private int size;
public void add(T t){
data[size] = t;
size++;
}
相信以上代碼很簡單，大伙應該很容易就能理解椿疗，不過上面這樣實現的問題也是顯而易見的漏峰。因為數組的長度是固定的，容易發(fā)生數組越界異常届榄，所以就自然而然想到了動態(tài)改變數組長度浅乔。由此產生了所謂的動態(tài)數組。
具體動態(tài)改變數組長度的過程也是很簡單铝条，每次添加元素時靖苇，先進行判斷是否當前元素個數size是否等于數組的長度。如果大于等于班缰，則進行一次擴容操作贤壁，增至為當前數組2倍的數據量。
public void add(int index, T t) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index illegal exception");
}
// 當前元素個數大于等于數組長度
if (size >= data.length) {
resizeCapacity(2 * data.length);
}
// 當前元素個數小于數組長度的四分之一埠忘，避免一開始數據過少浪費空間
if (size <= data.length / 4 && data.length / 2 != 0) {
resizeCapacity(data.length / 2);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = t;
size++;
}
擴容的代碼也很簡單脾拆，就是開辟一個新空間，然后進行一輪賦值操作莹妒。
private void resizeCapacity(int newCapacity) {
if (size > newCapacity) {
throw new IllegalArgumentException("size is bigger than newCapacity");
}
T[] newT = (T[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newT[i] = data[i];
}
data = newT;
}
1.2.2 移除元素remove方法
同理名船，移除元素也是一樣的對元素個數進行判斷。
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index illegal exception");
}
T delete = data[index];
System.arraycopy(data, index + 1, data, index, size - 1 - index);
size--;
data[size] = null;
// 當前元素個數小于數組長度的四分之一時旨怠，進行縮容
if (size <= data.length / 4 && data.length / 2 != 0) {
resizeCapacity(data.length / 2);
}
return delete;
}
這里你可能會問渠驼，為啥是當前元素小于四分之一才縮容一半呢，為啥不是二分之一時進行縮容呢鉴腻？
其中原因很簡單迷扇，我們想象一下，如果每次元素個數小于當前數組容積的一半時爽哎，我們就縮容蜓席，那么此時如果剛好又得add元素，那又得擴容课锌，這樣來回縮容擴容相當耗費性能厨内，這種現象成為復雜度的震蕩。
1.2.2 改變元素set方法
針對某個索引對元素進行修改产镐。
public void set(int index, T t) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index illegal exception");
}
data[index] = t;
}
1.2.3 查找某個元素find方法
對數組做一次遍歷隘庄，當equals為true時，返回當前元素癣亚，否則返回-1丑掺。
public int find(T t) {
for (int i = 0; i < size; i++) {
if (data[i].equals(t)) {
return i;
}
}
return -1;
}
1.3 復雜度的分析
1.3.1 增
其實增的操作就是插入元素，復雜度和插入元素的位置有相當大的關系述雾。
最后插入元素（我們習慣叫添加元素）
那么復雜度為O(1)級別街州，因為不用做元素的后移操作兼丰。
其余位置插入元素，復雜度為O(n)級別唆缴，需要移動元素鳍征。
基于鏈表和數組的數據結構比較
我們經常說，基于鏈表的數據結構插入元素比基于數組的數據結構快面徽，其實這是有條件的艳丛。我們來看一下如下一段代碼：
ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
int count = 5000 * 10;
Random randomIndex = new Random();
long startTime = System.nanoTime();
for (int i = 0; i < count; i++) {
arrayList.add(randomIndex.nextInt(arrayList.size() + 1), i);
}
long endTime = System.nanoTime();
System.out.println("array: " + (endTime - startTime) / 1000000000.0);
startTime = System.nanoTime();
for (int i = 0; i < count; i++) {
linkedList.add(randomIndex.nextInt(linkedList.size() + 1), i);
}
endTime = System.nanoTime();
System.out.println("linked: " + (endTime - startTime) / 1000000000.0);
運行結果：
array: 0.156862527
linked: 5.517377045
是不是很驚喜！趟紊？是不是很刺激５？??
如果是隨機插入到ArrayList和LinkedList霎匈，雖然鏈表在插入元素時戴差，只需要改變插入節(jié)點頭尾指針的指向，但是這里的耗時操作存在兩點：
第一铛嘱，找尋插入節(jié)點的位置暖释；
第二，不斷的new出新的node節(jié)點（鏈表節(jié)點）
所以就得出了以上的結果墨吓，鏈表的主要優(yōu)勢場景：在于頭尾兩個節(jié)點進行頻繁操作球匕。
其余刪，改肛真，查谐丢，基本上分析的方法和增差不多爽航，這里就不贅述了蚓让。
