1.簡(jiǎn)介

源碼基于android 23.

• 繼承于AbstractSequentialList<E>，實(shí)現(xiàn)了List<E>, Deque<E>, Queue<E>, Cloneable, Serializable接口
• 基于雙向循環(huán)鏈表
• 支持null
• 在有類(lèi)似隊(duì)列操作時(shí)很有用處，也可使用在你的list中有一個(gè)或者0個(gè)元素時(shí)但是你還想list擁有擴(kuò)展更多元素的能力。
• 在沒(méi)有隊(duì)列操作時(shí)使用ArrayList是比較好的選擇

/**
 * LinkedList is an implementation of {@link List}, backed by a doubly-linked list.
 * All optional operations including adding, removing, and replacing elements are supported.
 *
 * <p>All elements are permitted, including null.
 *
 * <p>This class is primarily useful if you need queue-like behavior. It may also be useful
 * as a list if you expect your lists to contain zero or one element, but still require the
 * ability to scale to slightly larger numbers of elements. In general, though, you should
 * probably use {@link ArrayList} if you don't need the queue-like behavior.
 *
 * @since 1.2
 */

2.成員變量

    transient int size = 0;

    transient Link<E> voidLink;

    private static final class Link<ET> {
        ET data;

        Link<ET> previous, next;

        Link(ET o, Link<ET> p, Link<ET> n) {
            data = o;
            previous = p;
            next = n;
        }
    }

3.構(gòu)造方法

voidLink作為鏈接指針，最后元素的next指向voidLink的previous，
voidLink的next指向第一個(gè)元素的previous
 public LinkedList() {
        voidLink = new Link<E>(null, null, null);
        voidLink.previous = voidLink;
        voidLink.next = voidLink;
    }
 public LinkedList(Collection<? extends E> collection) {
        this();
        addAll(collection);
    }

4.方法

1.add

   public void addFirst(E object) {
        addFirstImpl(object);
    } 
    private boolean addFirstImpl(E object) {
        Link<E> oldFirst = voidLink.next;  
        Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
        voidLink.next = newLink; //voidLink的next指向新添加元素
        oldFirst.previous = newLink;//以前的第一個(gè)元素的previous指向新添加元素
        size++;
        modCount++;
        return true;
    }
//addLast同理
private boolean addLastImpl(E object) {
        Link<E> oldLast = voidLink.previous;
        Link<E> newLink = new Link<E>(object, oldLast, voidLink);
        voidLink.previous = newLink;//voidLink的previous指向新添加元素
        oldLast.next = newLink;//以前最后元素的next指向新添加元素
        size++;
        modCount++;
        return true;
    }
//指定位置添加元素，采用簡(jiǎn)單的二分法則。找到需要插入位置的元素link
 @Override
    public void add(int location, E object) {
        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;
                }
            }
            //找到link的前一個(gè)元素
            Link<E> previous = link.previous;
            //生成新元素
            Link<E> newLink = new Link<E>(object, previous, link);
            //link的前一個(gè)元素的next指向新添加元素
            previous.next = newLink;
            //link的previous的指向新添加元素
            link.previous = newLink;
            size++;
            modCount++;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

2.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;
                }
            }
    //二分找出需要?jiǎng)h除的元素link。找到link的前一個(gè)元素和后一個(gè)元素
            Link<E> previous = link.previous;
            Link<E> next = link.next;
//將link的前元素的next指向link的后一個(gè)元素
            previous.next = next;
//將link的后一個(gè)元素的previous指向link的前一個(gè)元素
            next.previous = previous;
            size--;
            modCount++;
            return link.data;
        }
        throw new IndexOutOfBoundsException();
    }
//刪除指定元素
  @Override
    public boolean remove(Object object) {
        return removeFirstOccurrenceImpl(object);
    }
    private boolean removeFirstOccurrenceImpl(Object o) {
        Iterator<E> iter = new LinkIterator<E>(this, 0);
        return removeOneOccurrence(o, iter);
    }

    private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
        while (iter.hasNext()) {
            E element = iter.next();
            //可以操作null。
            if (o == null ? element == null : o.equals(element)) {
                iter.remove();
                return true;
            }
        }
        return false;
    }
//刪除所有元素，將voidLink的指針指向自己。
  @Override
    public void clear() {
        if (size > 0) {
            size = 0;
            voidLink.next = voidLink;
            voidLink.previous = voidLink;
            modCount++;
        }
    }

3.set

 public E set(int location, E object) {
        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;
                }
            }
            E result = link.data;
            link.data = object;
            return result;
        }
        throw new IndexOutOfBoundsException();
    }

4.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();
    }
  @Override
    public boolean contains(Object object) {
        Link<E> link = voidLink.next;
        if (object != null) {
            while (link != voidLink) {
                if (object.equals(link.data)) {
                    return true;
                }
                link = link.next;
            }
        } else {
            while (link != voidLink) {
                if (link.data == null) {
                    return true;
                }
                link = link.next;
            }
        }
        return false;
    }

5.實(shí)現(xiàn)Deque接口方法

Deque接口.png

//返回第一個(gè)元素
   public E peek() {
        return peekFirstImpl();
    }

    private E peekFirstImpl() {
        Link<E> first = voidLink.next;
        return first == voidLink ? null : first.data;
    }
   //添加一個(gè)元素到最后
    public boolean offer(E o) {
        return addLastImpl(o);
    }
   //移除第一個(gè)元素。
    public E poll() {
        return size == 0 ? null : removeFirst();
    }
    public E pop() {
        return removeFirstImpl();
    }
    public void push(E e) {
        addFirstImpl(e);
    }
   //正向iterator
   @Override
    public ListIterator<E> listIterator(int location) {
        return new LinkIterator<E>(this, location);
    }
  //逆向iterator
  public Iterator<E> descendingIterator() {
        return new ReverseLinkIterator<E>(this);
    }

6.序列化,transient的作用還是在于自己手動(dòng)序列化，不去保存指針，只保存數(shù)據(jù)，節(jié)約空間。在恢復(fù)數(shù)據(jù)時(shí)在將鏈表結(jié)構(gòu)恢復(fù)。

private void writeObject(ObjectOutputStream stream) throws IOException {
        stream.defaultWriteObject();
        stream.writeInt(size);
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            stream.writeObject(it.next());
        }
    }
  @SuppressWarnings("unchecked")
    private void readObject(ObjectInputStream stream) throws IOException,
            ClassNotFoundException {
        stream.defaultReadObject();
        size = stream.readInt();
        voidLink = new Link<E>(null, null, null);
        Link<E> link = voidLink;
        for (int i = size; --i >= 0;) {
            Link<E> nextLink = new Link<E>((E) stream.readObject(), link, null);
            link.next = nextLink;
            link = nextLink;
        }
        link.next = voidLink;
        voidLink.previous = link;
    }

5.ArrayList和LinkedList的比較

• 普通結(jié)論：ArrayList基于數(shù)組，查詢快，增刪慢。LinkedList基于鏈表，查詢慢，增刪快。
• get和set，ArrayList較快，LinkedList要二分然后for循環(huán)查找到指定元素。
• 在remove和add上。LinkedList如果不是在首位位置操作，也需要先查詢到指定的元素才能操作（快操作，慢尋址）。ArrayList在這兩個(gè)操作上時(shí)間主要浪費(fèi)在copy數(shù)組上（慢操作，快尋址）。但是ArrayList中remove（index）中
  System.arraycopy(a, index + 1, a, index, --s - index);如果刪除最后一個(gè)元素copy數(shù)組不浪費(fèi)時(shí)間，這個(gè)時(shí)候性能超過(guò)LinkedList。add（index）類(lèi)似。
• index，contains效率差不多
• 迭代效率,建議使用foreach
  Trinea分析ArrayList和LinkedList的幾種循環(huán)遍歷方式及性能對(duì)比分析