ArrayList
當我們在代碼中建立一個Array時，計算機實際上會在記憶體中開辟一塊連續的位址，每個位址都可以直接通路，通路任意一個元素的時間複雜度都是相同的，也就是O(1)。但是如果我們要增加或者删除元素時，因為位址連續的緣故，就需要做比較多的事情了。
假設有個數組長度為10，現在要插入一個元素下标為4，那麼則需要将原來index>=4的所有元素都向後移一位，将index=4的位址空間讓出來給新增的元素，這樣的操作導緻時間複雜度上升為O(n)，删除操作也同理。
源碼分析
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
這個add方法的作用是在數組的末端插入一個元素，ensureCapacityInternal(size + 1)保證數組的size有size+1這麼大，然後在數組末尾添加上e這個元素，最後size++。
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
這個重載的add方法的作用就是在數組中間插入元素，首先會檢查上下界，同時保證數組的大小，然後調用arrayCopy複制數組，這個方法的意思是，從elementData這個數組的下标index的元素開始，複制到目标數組elementData（第二個）的index+1的地方，總共複制size-index個元素。簡單的來說就是将數組中下标從index開始的元素全部向後移動一個機關，将index的位址讓出來。然後elementData[index] = element，将新元素插入到數組裡，最後size++。
LinkedList
在插入和删除操作比較頻繁的情況下，數組并不好用。而連結清單這個數組結構就是為了彌補數組的缺點。
LinkedList每個節點都有value和next，next指向下一個節點所在的位址，最後一個節點指向null，如果指向第一個節點，則這個連結清單就是循環連結清單。
在Java中的連結清單是雙向連結清單，在源碼中提供了一個prev來指向前一個節點。
假設我們需要在連結清單的第二個和第三個節點之間，插入一個新節點，隻需要将第二個節點的next指向新插入的節點，然後将新插入的節點的next指向原來的第三個節點，即可完成插入操作，不需要操作其他節點，是以連結清單的插入效率非常高，時間複雜度為O(1)，删除節點同理。
而正是因為連結清單的位址空間不連續，導緻通路某個節點，隻能一個個疊代過去，效率比較差，時間複雜度為O(n)。
SkipList
連結清單的優點是插入快而定位慢，但當連結清單内的元素都是按照一定的順序排列的情況下，就可以使用一些方法來加速定位，再使用疊代器定位元素就顯得很蠢，是以就出現了SkipList跳表，在一些熱門項目裡替代了平衡樹，如Redis。
跳表的插入、删除、搜尋的時間複雜度都是O(logn)。
優勢：原理簡單，友善實作，容易拓展，效率更高。
跳表的使用隻能在連結清單的元素都是有序的情況下！！
跳表加速的方式
加速一維的數組結構經常采用的方式就是升維，如圖
索引的元素并沒有指向nxet元素，而是指向了距離更遠的元素，這樣劃分出一個個區間來，定位元素的時候先通過進階索引來定位元素在哪個區間，然後逐漸縮小區間，最後在原始連結清單中疊代定位元素，如果在原始連結清單中沒找到則代表該元素不存在。
比如說要定位元素5，第一步在二級索引中，确定要定位的元素在1到7這兩個元素之間，然後再通過一級索引，發現元素5在4和7之間，然後從元素4開始一個個查找，很快就能定位出元素。