LinkedList作為一個(gè)常用的集合在我們項(xiàng)目開發(fā)當(dāng)中經(jīng)常會(huì)用到，它經(jīng)常會(huì)拿來(lái)和ArrayList做比較，那我們今天就通過(guò)源碼來(lái)解析下它內(nèi)部的實(shí)現(xiàn)原理
構(gòu)造方法
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
new了一個(gè)Link類，這個(gè)Link類包括：添加的數(shù)據(jù)data，鏈表上個(gè)對(duì)象和下個(gè)對(duì)象的引用；因?yàn)槭浅跏蓟运臄?shù)據(jù)是null，對(duì)上一個(gè)和下一個(gè)的引用也是自己本身。
添加方法
@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();
}
}
當(dāng)我們調(diào)用add(E e)方法的同時(shí)，方法內(nèi)部又調(diào)用了add(int location, E object)方法，location是要添加數(shù)據(jù)的位置，下面我們通過(guò)一張圖來(lái)看一下它的add機(jī)制。
如果location是1，那么就從0開始循環(huán)找，然后把要添加的數(shù)據(jù)添加到0和1之間；
如果location是3，那么就從voidLinked header開始找，然后把數(shù)據(jù)添加到2和3之間。
再來(lái)看看其他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添加到鏈表的最尾部，因?yàn)槲覀內(nèi)?shù)據(jù)的時(shí)候是從尾部開始取的
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ù)的邏輯是一致的，這邊就不細(xì)說(shuō)了。
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位置的對(duì)象的上面和下面的對(duì)象關(guān)聯(lián)起來(lái)
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位置對(duì)象的上面和下面對(duì)象關(guān)聯(lián)起來(lái)。
@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)遍歷，通過(guò)equals方法對(duì)比找到相同的數(shù)據(jù)，然后刪除。
總結(jié)
LinkedList內(nèi)部存儲(chǔ)數(shù)據(jù)是以鏈表的形式存儲(chǔ)的，查詢數(shù)據(jù)需要從鏈表頭或尾循環(huán)取值，所以會(huì)比ArrayList查詢慢，添加和刪除數(shù)據(jù)差不多，在特定的情況下添加數(shù)據(jù)ArrayList會(huì)稍慢，其他方法差別不會(huì)特別大。
