這次是自己閱讀JDK源碼得到的一些頓悟痊乾，java集合類LinkList是數(shù)據(jù)結(jié)構(gòu)鏈表的實現(xiàn)皮壁。
LinkedList繼承了AbstractSequentiaList,主要實現(xiàn)了接口List里的方法。
public class LinkedListextends AbstractSequentialListimplements List, Deque, Cloneable, java.io.Serializable
鏈表頭節(jié)點：
transient? Node first;
鏈表表尾節(jié)點：
transient? Node last;
1.1添加節(jié)點
使用前插法創(chuàng)建鏈表：每添加一個節(jié)點哪审，都會在當(dāng)前的鏈表頭部添加一個節(jié)點蛾魄，然后添加之后的節(jié)點成為這個鏈表的頭部---（先進(jìn)為尾，后進(jìn)為頭）湿滓。
public void addFirst(E e) {? ??
linkFirst(e);
}
private void linkFirst(E e) {
final Node f = first;? ??
final Node newNode =new Node<>(null, e, f);??
? first = newNode;? ?
?if (f ==null)? ? ??
? ? ? ?last = newNode;? ?
?else? ? ??
? ? ? ? ? ?f.prev = newNode;??
? size++;??
? modCount++;}
使用后插法創(chuàng)建鏈表：當(dāng)有節(jié)點添加進(jìn)鏈表時滴须，都會在當(dāng)前鏈表的尾部添加該節(jié)點，鏈表add（）方法默認(rèn)時鏈表的后插法叽奥。---（先進(jìn)為頭描馅，后進(jìn)為尾）。
public void addLast(E e) {??
? linkLast(e);
}
public boolean add(E e) {? ?
?linkLast(e);? ??
return true;
}
void linkLast(E e) {
final Node l = last;??
? final Node newNode =new Node<>(l, e, null);??
? ? ? ? ? ? ? ? ? ?last = newNode;??
? if (l ==null)? ? ?
? ? ? ? ? ? ? ? ? ? ? first = newNode;? ??
else? ? ? ??
? ? ? ? ? ? ? ? ? ?l.next = newNode;??
? ? ? ? ? ? ? ? ? size++;? ?
? ? ? ? ? ? ? ? ? ? modCount++;
}
1.2刪除節(jié)點---刪節(jié)點動作之前都要做判空處理而线。以免刪空鏈表導(dǎo)致程序報錯
?刪除頭節(jié)點：將當(dāng)前鏈表頭的next所指向的地址铭污，賦予給first節(jié)點。之后再將該節(jié)點的前綴賦予null膀篮。
public E removeFirst() {
final Node f = first;?
?? if (f ==null)throw new NoSuchElementException();
? ? return unlinkFirst(f);
}
private E unlinkFirst(Node f) {
// assert f == first && f != null;? ??
final E element = f.item;? ?
?final Node next = f.next;?
?? f.item =null;??
? f.next =null;?
// help GC??
? first = next;??
? if (next ==null)? ? ? ?
?last =null;??
? else? ??
? ? next.prev =null;? ?
?size--;? ?
?modCount++;? ??
return element;}
刪除鏈表尾節(jié)點：找出鏈表表尾的前綴所指向的地址嘹狞，之后就是將原先未處理的鏈表表尾所指節(jié)點的next指針置為空。達(dá)到刪除表尾元素的效果誓竿。
public E removeLast() {
final Node l = last;?
?? if (l ==null)throw new NoSuchElementException();? ?
?return unlinkLast(l);
}
private E unlinkLast(Node l) {
// assert l == last && l != null;??
? final E element = l.item;
? ? final Node prev = l.prev;??
? l.item =null;?
?? l.prev =null;?
// help GC?
?? last = prev;??
? if (prev ==null)? ?
?? ? first =null;??
? else? ? ??
? prev.next =null;? ??
size--;?
?? modCount++;??
? return element;
}
刪除特定節(jié)點：
public E remove(int index) {??
? checkElementIndex(index);??
? return unlink(node(index));
}
*刪除鏈表中的節(jié)點：包括前兩種處理磅网。是remove()方法的實現(xiàn)。獲取要刪除節(jié)點的prev所指節(jié)點和next做直接點筷屡。如果prev所指的節(jié)點為null,則表示要刪除的節(jié)點是頭結(jié)點涧偷，操作和removeFirst（）相一致，如果是鏈表表尾節(jié)點毙死，操作和removeLast（）相一致燎潮。非上面兩種情況，則會將的prev所指節(jié)點指向next所致的節(jié)點扼倘。
public boolean remove(Object o) {
if (o ==null) {
for (Node x = first; x !=null; x = x.next) {
if (x.item ==null) {? ? ? ? ? ? ?
?? unlink(x);? ? ? ? ? ? ??
? return true;? ? ?
?? ? ? }? ??
? ? }? ?
?}else {
for (Node x = first; x !=null; x = x.next) {
if (o.equals(x.item)) {? ?
?? ? ? ? ? ? unlink(x);? ?
?? ? ? ? ? ? return true;?
?? ? ? ? ? }? ? ? ?
?}? ??
}
return false;}
E unlink(Node x) {
// assert x != null;??
? final E element = x.item;?
?? final Node next = x.next;?
?? final Node prev = x.prev;?
?? if (prev ==null) {? ? ?
?? first = next;? ? }
else {? ?
?? ? prev.next = next;? ?
?? ? x.prev =null;? ??
}if (next ==null) {? ??
? ? last = prev;? ? }
else {??
? ? ? next.prev = prev;
? ? ? ? x.next =null;? ?
?}? ?
?x.item =null;?
?? size--;? ?
?modCount++;? ??
return element;
}
1.3添加所有節(jié)點：使用一個過度節(jié)點newNode來組裝該鏈表确封。
public boolean addAll(Collection c) {return addAll(size, c);}
public boolean addAll(int index, Collection c) {? ??
checkPositionIndex(index);? ?
?Object[] a = c.toArray();? ?
?int numNew = a.length;? ?
?if (numNew ==0)return false;??
? Node pred, succ;??
? if (index == size) {? ?
?? ? succ =null;? ? ?
?? pred = last;
? ? }else {?
?? ? ? succ = node(index);? ??
? ? pred = succ.prev;? ?
?}
for (Object o : a) {? ?
?? ? @SuppressWarnings("unchecked") E e = (E) o;?
?? ? ? Node newNode =new Node<>(pred, e, null);? ?
?? ? if (pred ==null)? ? ??
? ? ? first = newNode;? ? ?
?? else? ? ? ?
?? ? pred.next = newNode;? ??
? ? pred = newNode;?
?? }
if (succ ==null) {? ?
?? ? last = pred;??
? } else {? ? ?
?? pred.next = succ;?
?? ? ? succ.prev = pred;??
? }??
? size += numNew;??
? modCount++;? ?
?return true;
}
1.4修改鏈表中特定的節(jié)點：
public E set(int index, E element) {? ??
checkElementIndex(index);? ?
?Node x = node(index);??
? E oldVal = x.item;? ?
?x.item = element;??
? return oldVal;
}
1.5在特定的位置添加節(jié)點：
public void add(int index, E element) {? ??
checkPositionIndex(index);?
?? if (index == size)? ? ??
? linkLast(element);? ?
?else? ? ??
? linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
// assert succ != null;??
? final Node pred = succ.prev;??
? final Node newNode =new Node<>(pred, e, succ);
? ? succ.prev = newNode;?
?? if (pred ==null)? ? ??
? first = newNode;? ?
?else? ?
?? ? pred.next = newNode;? ??
size++;? ??
modCount++;
}
? ? 定位節(jié)點位置：
Node node(int index) {
// assert isElementIndex(index);? ?
?if (index < (size >>1)) {??
? ? ? Node x = first;? ? ?
?? for (int i =0; i < index; i++)? ? ? ?
?? ? x = x.next;? ??
? ? return x;? ??
}else {? ? ??
? Node x = last;? ?
?? ? for (int i = size -1; i > index; i--)? ?
?? ? ? ? x = x.prev;??
? ? ? return x;? ? }}
1.6獲取特定節(jié)點信息：
public E get(int index) {? ? checkElementIndex(index);? ? return node(index).item;}
1.7清空鏈表信息：
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:??
? // - helps a generational GC if the discarded nodes inhabit? ??
//? more than one generation??
? // - is sure to free memory even if there is a reachable Iterator?
?? for (Node x = first; x !=null; ) {? ? ??
? Node next = x.next;? ? ? ?
?x.item =null;?
?? ? ? x.next =null;??
? ? ? x.prev =null;
? ? ? ? x = next;? ?
?}??
? first = last =null;??
? size =0;? ?
?modCount++;
}
平常在工作使用的比較多的，鏈表中的add()，addAll()爪喘，remove()get()颜曾，clear()方法的具體實現(xiàn)邏輯。筆者第一次寫的博客秉剑，還有很多不足的地方泛豪，希望看過的博主們能提一提您寶貴的建議。
筆者目前是一個java小菜鳥侦鹏，還在努力學(xué)習(xí)和成長中候址。技術(shù)的進(jìn)步貴在交流。
