寫(xiě)在前面
本文所看的源碼是在idea里面查看的互婿，一些代碼和Java的源碼可能有所不同……但是思想應(yīng)該是一致的鹏控。
上一篇淺析ArrayList簡(jiǎn)要的了解了一下ArrayList是如何實(shí)現(xiàn)的，ArrayList內(nèi)部是用一個(gè)Object數(shù)組對(duì)象來(lái)作為容器盛放各個(gè)對(duì)象的蠕啄。而LinkedList則不然筑悴，其內(nèi)部實(shí)現(xiàn)就類(lèi)似于數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表。只不過(guò)在Java中可能你不能直接使用“指針”沼死，所以得通過(guò)Java的“引用”來(lái)實(shí)現(xiàn)這個(gè)雙向鏈表。那么今天也讓我們通過(guò)幾個(gè)比較經(jīng)典的方法來(lái)看一下其內(nèi)部實(shí)現(xiàn)崔赌。
Node
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
很經(jīng)典的一個(gè)數(shù)據(jù)結(jié)構(gòu)……（笑）
考慮到了代碼的兼容性加入了泛型意蛀，這些都是可以暫時(shí)不看的耸别，對(duì)我們了解其實(shí)現(xiàn)沒(méi)什么大的影響。
這個(gè)類(lèi)內(nèi)部一個(gè)next一個(gè)prev分別代表了當(dāng)前節(jié)點(diǎn)的前驅(qū)和后繼县钥，大白話(huà)就是這節(jié)點(diǎn)的前一個(gè)元素和后一個(gè)元素秀姐，item是保存的值。
add()
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
向鏈表的尾部插入一個(gè)值若贮，那么繼續(xù)看看linkLast(e)是怎么實(shí)現(xiàn)的
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
可以看出這個(gè)方法會(huì)將節(jié)點(diǎn)插入鏈表的尾部省有。在LinkedList內(nèi)部有一個(gè)指向尾部的引用，所以插入尾部實(shí)現(xiàn)起來(lái)十分簡(jiǎn)單谴麦。先將尾節(jié)點(diǎn)引用指向新節(jié)點(diǎn)蠢沿，之后判斷一下頭節(jié)點(diǎn)是否為空，如果是空的話(huà)匾效，那么說(shuō)明這個(gè)鏈表還沒(méi)有節(jié)點(diǎn)舷蟀，那么將第一個(gè)節(jié)點(diǎn)的引用指向這個(gè)節(jié)點(diǎn)，如果非空的話(huà)就將新的節(jié)點(diǎn)插入到最后一個(gè)節(jié)點(diǎn)的后面面哼。
get()
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
這個(gè)方法會(huì)返回一個(gè)特定位置的node所存儲(chǔ)的值野宜。代碼很少一共就兩行，先看第一行的代碼是個(gè)啥：
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Tells if the argument is the index of an existing element.
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
通過(guò)兩個(gè)方法我們可以看出這個(gè)方法會(huì)檢查你所給的index是否在這個(gè)鏈表內(nèi)魔策，如果不是會(huì)拋出索引越界的異常速缨。
接下來(lái)看看第二行代碼是如何實(shí)現(xiàn)的：
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
可以看出這個(gè)方法還是對(duì)這個(gè)索引進(jìn)行了簡(jiǎn)單的計(jì)算，如果這個(gè)索引大于鏈表的尺寸的一半那么他會(huì)從尾部開(kāi)始遍歷直到找到這個(gè)index對(duì)應(yīng)的node代乃。反之他會(huì)從這個(gè)鏈表的頭部開(kāi)始遍歷旬牲。畢竟雙向鏈表，從哪都行~
暫時(shí)只寫(xiě)這么多吧搁吓，準(zhǔn)備周末再去看下集合框架中的那幾個(gè)接口原茅，回頭來(lái)再詳細(xì)的看一些東西。
