/**
* List接口的實現(xiàn)類LinkedList ?linked list鏈表
* ArrayList和Vector都是使用數(shù)組來存儲數(shù)據(jù) 數(shù)組是空間連續(xù)的 在內(nèi)存中指定長度創(chuàng)建連續(xù)的空間 數(shù)組的元素與元素之間在空間上是相鄰的
* 數(shù)組使用index索引所以查詢效率高O(1) 但每次增刪都涉及到index后面元素的位移 增刪效率低
* LinkedList使用雙向鏈表存儲數(shù)據(jù) 每個結(jié)點/元素包含數(shù)據(jù)域(即元素本身的數(shù)據(jù))和指針域(指向直接前驅(qū)結(jié)點和指向直接后繼結(jié)點的兩個指針)
* 鏈表不記錄index 每次查詢需要從表頭結(jié)點或表尾結(jié)點沿指針域逐個結(jié)點查找 查詢效率低 但每次增刪只需要更改目標位置前后結(jié)點的指針域 不需要對元素進行移位 增刪效率高
* LinkedList線程不安全
*/
public class TestLinkedList {
? ?public static void main(String[] args) {
? ? ? ?List<String> linked = new LinkedList<>();
? ? ? ?//LinkedList實現(xiàn)了List的抽象方法 對于List的方法的調(diào)用通過List引用變量來使用? ? ? ? //linked.add();linked.remove();linked.clear();linked.size();linked.toArray();linked.indexOf();linked.set();linked.get();linked.contains();linked.isEmpty();????LinkedList實現(xiàn)的這些基本方法的用法同ArrayList和Vector
? ? ? ?LinkedList<String> ll1 = new LinkedList<>();
? ? ? ?//測試LinkedList類內(nèi)定義的用于鏈表操作的方法 這些方法不是實現(xiàn)自List 不能用List引用變量調(diào)用
? ? ? ?ll1.addFirst("a");
? ? ? ?//.addFirst()向鏈表的表頭添加結(jié)點 每次添加的結(jié)點都變更為表頭結(jié)點
? ? ? ?ll1.addFirst("b");
? ? ? ?ll1.addFirst("c");
? ? ? ?System.out.println(ll1);
? ? ? ?//結(jié)果為[c, b, a] 每次addFirst的結(jié)點都變更為表頭
? ? ? ?ll1.addLast("d");
? ? ? ?//.addLast()向表尾添加結(jié)點 每次添加都變更為新的表尾
? ? ? ?ll1.addLast("f");
? ? ? ?for (String e:ll1){
? ? ? ? ? ?System.out.print(e+",");
? ? ? ? ? ?//結(jié)果c,b,a,d,f,
? ? ? ?}
? ? ? ?System.out.println();
? ? ? ?System.out.println(ll1.getFirst());
? ? ? ?//.getFirst()返回表頭結(jié)點 結(jié)果為c
? ? ? ?System.out.println(ll1.getLast());
? ? ? ?//.getLast()返回表尾結(jié)點 結(jié)果為f
? ? ? ?System.out.println(ll1.removeFirst());
? ? ? ?System.out.println(ll1);
? ? ? ?//.removeFirst()刪除表頭并返回 刪除了c并返回 鏈表的結(jié)果[b, a, d, f]
? ? ? ?System.out.println(ll1.removeLast());
? ? ? ?for (int i = 0 ;i<ll1.size();i++){
? ? ? ? ? ?System.out.print(ll1.get(i)+",");
? ? ? ?}
? ? ? ?//.removeLast()刪除表尾并返回 刪除了f并返回 鏈表的結(jié)果[b, a, d]
? ? ? ?System.out.println();
? ? ? ?System.out.println(ll1.pop());
? ? ? ?//作用同Stack棧容器的pop() 彈出棧頂/表頭結(jié)點 并返回 相當于removeFirst
? ? ? ?System.out.println(ll1);
? ? ? ?//結(jié)果[a, d]
? ? ? ?ll1.push("g");
? ? ? ?//作用同Stack棧容器的push() 壓棧 將結(jié)點推入棧頂/表頭 相當于addFirst
? ? ? ?System.out.println(ll1);
? ? ? ?//結(jié)果[g, a, d]

? ? ? ?/* LinkedList通過雙向鏈表存儲數(shù)據(jù) 源碼
? ? ? ?public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
? ? ? ?//泛型類
? ? ? ? ? ?private static class Node<E> {
? ? ? ? ? ?//node結(jié)點 static class 靜態(tài)內(nèi)部類 在LinkedList類內(nèi)部定義
? ? ? ? ? ? ? ?E item;
? ? ? ? ? ? ? ?Node<E> next;
? ? ? ? ? ? ? ?Node<E> prev;
? ? ? ? ? ? ? ?//item用來保存元素 即數(shù)據(jù)域 ?next/previous指針域指向直接后繼結(jié)點和直接前驅(qū)結(jié)點
? ? ? ? ? ? ? ?Node(Node<E> prev, E element, Node<E> next) {
? ? ? ? ? ? ? ? ? ?this.item = element;
? ? ? ? ? ? ? ? ? ?this.next = next;
? ? ? ? ? ? ? ? ? ?this.prev = prev;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?//沒有無參構(gòu)造器 每個結(jié)點在實例時必須定義唯三的屬性 表頭結(jié)點的prev=null 表尾結(jié)點的next=null
? ? ? ? ? ?}
? ? ? ? ? ?//回到LinkedList類內(nèi)
? ? ? ? ? ?transient int size = 0;
? ? ? ? ? ?//size即結(jié)點的總數(shù) 作用同ArrayList/Vector.size
? ? ? ? ? ?transient Node<E> first;
? ? ? ? ? ?transient Node<E> last;
? ? ? ? ? ?//LinkedList對象中只保存表頭結(jié)點first和表尾結(jié)點last

? ? ? ? ? ?public boolean add(E e) {
? ? ? ? ? ? ? ?linkLast(e);
? ? ? ? ? ? ? ?return true;
? ? ? ? ? ?}
? ? ? ? ? ?//實現(xiàn)List的add()方法 通過向表尾添加結(jié)點的方式
? ? ? ? ? ?void linkLast(E e) {
? ? ? ? ? ? ? ?final Node<E> l = last;
? ? ? ? ? ? ? ?//先將當前表尾緩存 如果鏈表為空則last=null
? ? ? ? ? ? ? ?final Node<E> newNode = new Node<>(l, e, null);
? ? ? ? ? ? ? ?//l賦值給prev e賦值給item next設為null
? ? ? ? ? ? ? ?last = newNode;
? ? ? ? ? ? ? ?if (l == null)
? ? ? ? ? ? ? ? ? ?first = newNode;
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ?l.next = newNode;
? ? ? ? ? ? ? ? ? ?//新結(jié)點變?yōu)楸砦步Y(jié)點，如果鏈表為空則將first和last都設為新結(jié)點 否則將緩存的原表尾結(jié)點.next鏈到新結(jié)點
? ? ? ? ? ? ? ?size++;
? ? ? ? ? ? ? ?modCount++;
? ? ? ? ? ?}
? ? ? ? ? ?//每個結(jié)點保存前后的指針 LinkedList容器保存頭尾的指針 這樣做不會在鏈表容器內(nèi)保存每一個結(jié)點的指針

? ? ? ? ? ?public void addFirst(E e) {linkFirst(e);}
? ? ? ? ? ?//linkFirst和linkLast原理相同 一個在表頭做調(diào)整 一個在表尾做調(diào)整 操作基本是鏡像的 這里addFirst沒有返回值 普通add會返回boolean

? ? ? ? ? ?public void add(int index, E element) {
? ? ? ? ? ? ? ?checkPositionIndex(index);
? ? ? ? ? ? ? ?//判定索引越界
? ? ? ? ? ? ? ?if (index == size)
? ? ? ? ? ? ? ? ? ?linkLast(element);
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ?linkBefore(element, node(index));
? ? ? ? ? ?}
? ? ? ? ? ?//判斷index==size即向表尾添加結(jié)點所以直接調(diào)用linkLast() 也同時解決了index=size=0空鏈表的情況 所以else為鏈表中至少有一個結(jié)點的情況 ?node(index)方法如下
? ? ? ? ? ?Node<E> node(int index) {
? ? ? ? ? ? ? ?if (index < (size >> 1)) {
? ? ? ? ? ? ? ?//二分 size即length /2為中位 size為偶數(shù)時/2是右半邊的首位 小于中位則從頭查找更快 大于則從尾查找
? ? ? ? ? ? ? ? ? ?Node<E> x = first;
? ? ? ? ? ? ? ? ? ?for (int i = 0; i < index; i++)
? ? ? ? ? ? ? ? ? ? ? ?x = x.next;
? ? ? ? ? ? ? ? ? ?return x;
? ? ? ? ? ? ? ? ? ?//將表頭賦值給x 每次.next都會返回直接后繼結(jié)點 從first一直.next.next.next可以通到last 當i=index-1時x.next即為index位結(jié)點
? ? ? ? ? ? ? ?} else {
? ? ? ? ? ? ? ? ? ?Node<E> x = last;
? ? ? ? ? ? ? ? ? ?for (int i = size - 1; i > index; i--)
? ? ? ? ? ? ? ? ? ? ? ?x = x.prev;
? ? ? ? ? ? ? ? ? ?return x;
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ? ? ?//node(index)是查找索引位結(jié)點的方法 ?linkBefore(element, node(index))方法如下
? ? ? ? ? ?void linkBefore(E e, Node<E> succ) {
? ? ? ? ? ?//傳入的succ即為index位結(jié)點
? ? ? ? ? ? ? ?final Node<E> pred = succ.prev;
? ? ? ? ? ? ? ?final Node<E> newNode = new Node<>(pred, e, succ);
? ? ? ? ? ? ? ?succ.prev = newNode;
? ? ? ? ? ? ? ?if (pred == null)
? ? ? ? ? ? ? ? ? ?first = newNode;
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ?pred.next = newNode;
? ? ? ? ? ? ? ?size++;
? ? ? ? ? ? ? ?modCount++;
? ? ? ? ? ?}
? ? ? ? ? ?//通過index位結(jié)點succ找到直接前驅(qū)結(jié)點pred ?new新結(jié)點.prev設為前驅(qū)結(jié)點 .next設為succ 將succ的prev和前驅(qū)結(jié)點的next改為新結(jié)點
? ? ? ? ? ?//pred==null即add(0,element)的情況

? ? ? ? ? ?public E get(int index) {
? ? ? ? ? ? ? ?checkElementIndex(index);
? ? ? ? ? ? ? ?return node(index).item;
? ? ? ? ? ?}
? ? ? ? ? ?//node()方法返回Node結(jié)點 .item即數(shù)據(jù)域/存放的元素 ?get()方法返回的是結(jié)點的數(shù)據(jù)，類型<E>，返回的不是結(jié)點Node<E>

? ? ? ? ? ?public E remove(int index) {
? ? ? ? ? ? ? ?checkElementIndex(index);
? ? ? ? ? ? ? ?return unlink(node(index));
? ? ? ? ? ?}
? ? ? ? ? ?//移除index位結(jié)點 先node()返回index位的結(jié)點再解除鏈接unlink()方法如下
? ? ? ? ? ?E unlink(Node<E> x) {
? ? ? ? ? ?//泛型方法 根據(jù)傳入的結(jié)點類型做調(diào)整
? ? ? ? ? ? ? ?final E element = x.item;
? ? ? ? ? ? ? ?//緩存要刪除結(jié)點x的元素作為之后的返回值
? ? ? ? ? ? ? ?final Node<E> next = x.next;
? ? ? ? ? ? ? ?final Node<E> prev = x.prev;
? ? ? ? ? ? ? ?if (prev == null) {
? ? ? ? ? ? ? ?//prev==null即remove(0) 將first=x改為next
? ? ? ? ? ? ? ? ? ?first = next;
? ? ? ? ? ? ? ?} else {
? ? ? ? ? ? ? ? ? ?prev.next = next;
? ? ? ? ? ? ? ? ? ?x.prev = null;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?//將前驅(qū)結(jié)點跳過x鏈到后繼結(jié)點
? ? ? ? ? ? ? ?if (next == null) {
? ? ? ? ? ? ? ? ? ?last = prev;
? ? ? ? ? ? ? ?} else {
? ? ? ? ? ? ? ? ? ?next.prev = prev;
? ? ? ? ? ? ? ? ? ?x.next = null;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?x.item = null;
? ? ? ? ? ? ? ?//將指向x的鏈接全部撤掉 將x的指針全賦null 將x的item賦null x對象和數(shù)據(jù)對象不再被引用 等待垃圾回收
? ? ? ? ? ? ? ?size--;
? ? ? ? ? ? ? ?modCount++;
? ? ? ? ? ? ? ?return element;
? ? ? ? ? ?}

? ? ? ? ? ?public boolean remove(Object o) {
? ? ? ? ? ? ? ?if (o == null) {
? ? ? ? ? ? ? ?//元素/數(shù)據(jù)雖然是空 但.item保存空元素的結(jié)點是存在的 結(jié)點的prev/next可能有值 即空數(shù)據(jù)結(jié)點占了一位
? ? ? ? ? ? ? ? ? ?for (Node<E> x = first; x != null; x = x.next) {
? ? ? ? ? ? ? ? ? ? ? ?if (x.item == null) {
? ? ? ? ? ? ? ? ? ? ? ? ? ?unlink(x);
? ? ? ? ? ? ? ? ? ? ? ? ? ?return true;
? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?} else {
? ? ? ? ? ? ? ? ? ?for (Node<E> x = first; x != null; x = x.next) {
? ? ? ? ? ? ? ? ? ?//將迭代通過.next.next實現(xiàn) 表尾結(jié)點的next為null 所以直到遇到null即遍歷完成 這里x=null是判斷結(jié)點不是上面的x.item=null判斷元素 結(jié)點只有空鏈表或表頭.prev或表尾.next才會為空
? ? ? ? ? ? ? ? ? ? ? ?if (o.equals(x.item)) {
? ? ? ? ? ? ? ? ? ? ? ?//這里調(diào)用了o.equals()方法，如果沒有單獨判斷if(o==null)的話，當o為null時調(diào)用方法會報空指針異常
? ? ? ? ? ? ? ? ? ? ? ? ? ?unlink(x);
? ? ? ? ? ? ? ? ? ? ? ? ? ?return true;
? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?return false;
? ? ? ? ? ? ? ?//不存在o返回false
? ? ? ?}
? ? ? ? */
? ?}
}