LinkedList作為一個常用的集合在我們項目開發(fā)當中經(jīng)常會用到愿题，它經(jīng)常會拿來和ArrayList做比較搁宾，那我們今天就通過源碼來解析下它內(nèi)部的實現(xiàn)原理
構(gòu)造方法
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
new了一個Link類撕捍，這個Link類包括：添加的數(shù)據(jù)data，鏈表上個對象和下個對象的引用；因為是初始化所以它的數(shù)據(jù)是null，對上一個和下一個的引用也是自己本身健霹。
添加方法
@Override
public void add(int location, E object) {
//如果location大于等于0，并且location小于等于size執(zhí)行下面操作
// 否則越界異常
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
//如果location小于總大小的1/2,就從鏈表的尾部找
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
//如果location大于等于總大小的1/2,就從鏈表的頭部找
for (int i = size; i > location; i--) {
link = link.previous;
}
}
//插入到location位置
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
當我們調(diào)用add(E e)方法的同時瓶蚂，方法內(nèi)部又調(diào)用了add(int location, E object)方法糖埋，location是要添加數(shù)據(jù)的位置，下面我們通過一張圖來看一下它的add機制扬跋。
如果location是1阶捆，那么就從0開始循環(huán)找，然后把要添加的數(shù)據(jù)添加到0和1之間钦听；
如果location是3洒试，那么就從voidLinked header開始找，然后把數(shù)據(jù)添加到2和3之間朴上。
再來看看其他add方法
public boolean addAll(Collection<? extends E> collection) {
int adding = collection.size();
if (adding == 0) {
return false;
}
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
Link<E> previous = voidLink.previous;
//下面代碼的邏輯就是：從鏈表的頭開始插入數(shù)據(jù)垒棋，
// 最后一條數(shù)據(jù)是在鏈表頭上面的數(shù)據(jù)
for (E e : elements) {
Link<E> newLink = new Link<E>(e, previous, null);
previous.next = newLink;
previous = newLink;
}
previous.next = voidLink;
voidLink.previous = previous;
size += adding;
modCount++;
return true;
}
addFirst方法
public void addFirst(E object) {
addFirstImpl(object);
}
//把object添加到鏈表的最尾部，因為我們?nèi)?shù)據(jù)的時候是從尾部開始取的
private boolean addFirstImpl(E object) {
Link<E> oldFirst = voidLink.next;
Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
voidLink.next = newLink;
oldFirst.previous = newLink;
size++;
modCount++;
return true;
}
addLast方法
public void addLast(E object) {
addLastImpl(object);
}
//把object添加到鏈表的頭部
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
get方法
@Override
public E get(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
return link.data;
}
throw new IndexOutOfBoundsException();
}
跟添加數(shù)據(jù)獲取location位置數(shù)據(jù)的邏輯是一致的痪宰，這邊就不細說了叼架。
remove刪除方法
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
//把locaiton位置的對象的上面和下面的對象關(guān)聯(lián)起來
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
查找數(shù)據(jù)的邏輯和取值的邏輯是一致的，然后就是把location位置對象的上面和下面對象關(guān)聯(lián)起來衣撬。
@Override
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
}
//最后調(diào)用了此方法
private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
while (iter.hasNext()) {
E element = iter.next();
if (o == null ? element == null : o.equals(element)) {
iter.remove();
return true;
}
}
return false;
}
循環(huán)遍歷乖订，通過equals方法對比找到相同的數(shù)據(jù)，然后刪除具练。
總結(jié)
LinkedList內(nèi)部存儲數(shù)據(jù)是以鏈表的形式存儲的乍构，查詢數(shù)據(jù)需要從鏈表頭或尾循環(huán)取值，所以會比ArrayList查詢慢扛点，添加和刪除數(shù)據(jù)差不多哥遮，在特定的情況下添加數(shù)據(jù)ArrayList會稍慢，其他方法差別不會特別大陵究。
