LinkedList的基本存儲結(jié)構(gòu)是鏈表
LinkedList的節(jié)點(diǎn)元素的存儲結(jié)構(gòu)為：
? ? ?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;
? ? ? ? ? }
? ? ?}
LinkedList的add源碼為：
public boolean add(E e){
? ? ?linkLast(e);
? ? ?return true;
}
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++;
}
因?yàn)長inkedList的基本結(jié)構(gòu)是鏈表祈远，所以add就是在鏈表的末尾添加一個(gè)節(jié)點(diǎn)氢橙，然后size++，當(dāng)last==null代表改list為空的碧囊，所以頭結(jié)點(diǎn)置為newNode
linkedList的remove源碼為：
public boolean remove(Object o){
? ? ?if(o==null){
? ? ? ? ? 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){
? ? ? ? ? ? ? ?if(o.equals(x.item)){
? ? ? ? ? ? ? ? ? ? unlink(x);
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ? ?}
? ? ? ? ? }
? ? ?}
? ? ?return false;
}
linkedList的remove就是從頭遍歷節(jié)點(diǎn)责语，然后調(diào)用unlink來remove節(jié)點(diǎn)鸟辅，unlink的源碼如下：
? ?E unlink(Node<E> x){
? ? ? ? ? final E element = x.item;
? ? ? ? ? final Node<E> next = x.next;
? ? ? ? ? final Node<E> 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;
? ? ?}
``unlink就是把元素的前節(jié)點(diǎn)的next指向該元素的next,把元素的后節(jié)點(diǎn)的prev指向該元素的prev,然后把該元素的prev和next和item置為null,方便GC回收庶溶。
linkedList的get的源碼為：
public E get(int index){
? ? ?checkElementIndex(index);
? ? ?return node(index).item;
}
get的時(shí)候先檢測了index是否<0或者大于size,若是則拋出異常宅此。node()的源碼為：
Node<E> node(int 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;
? ? ?}
}
node方法就是先判斷一下index接近first還是last秦踪，然后決定從哪個(gè)方向開始查找褐捻。
linkedList的contains的源碼為：
public boolean contains(Object o){
? ? ?return indexOf(o)!=-1;
}
public int indexOf(Object o){
? ? ?int index = 0;
?????if(o==null){
? ? ? ? ? for(Node<E> x=first;x!=null;x=x.next){
? ? ? ? ? ? ? ?if(x.item == null)
? ? ? ? ? ? ? ? ? ? return index;
? ? ? ? ? ? ? ?index++;
? ? ? ? ? }
? ? ?}else{
? ? ? ? ? for(Node<E> x = first;x!=null;x=x.next){
? ? ? ? ? ? ? ? ? if(o.equals(x.item))
? ? ? ? ? ? ? ? ? ? ? ? ?return index;
? ? ? ? ? ? ? ? ? ? index++;
? ? ? ? ? }
? ? ?}
? ? ?return -1;
}
contains就是從first開始遍歷掸茅，查到就返回index
linkedList的clone的源碼為：
public Object clone(){
? ? ?LinkedList<E> clone = superClone();
? ? ?clone.first = clone.last=null;
? ? ?clone.size=0;
? ? ?clone.modCount = 0;
? ? ?for(Node<E> x=first;x!=null;x=x.next)
? ? ? ? ? clone.add(x.item);
? ? ?return clone;
}
``LinkedList的clone是淺克隆，只是克隆了引用柠逞。
