数据结构-02 LinkedList源码解析

本文根据Android API 21
LinkedList组成的元素是每个Link节点。所以要分析LinkedList首先要看Link。
LinkedList 内部类 Link< ET >

 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;
        }
    }

从这段代码中可以看出，每个link节点包含三个成员变量：

• data:用来存储Link节点的数据
• previous:用来指向前一个节点
• next:用来指向下一个节点

接下来在看LinkedList
LinkedList

首先来看成员变量

size 用来记录节点的个数

transient int size = 0;

默认的头节点

transient Link<E> voidLink;

构造方法 LinkedList()

public LinkedList() {
        voidLink = new Link<E>(null, null, null);
        voidLink.previous = voidLink;
        voidLink.next = voidLink;
    }

用来构造一个空的LinkedList对象

public LinkedList(Collection<? extends E> collection) {
this();
        addAll(collection);
    }

构造方法中调用了addAll方法，下面看addAll()方法。
addAll(Collection< ? extends E> collection) 向LinkedList集合中添加集合

@Override
public boolean addAll(Collection<? extends E> collection) {
//要添加集合的数量
int adding = collection.size();
if (adding == 0) {
return false;
        }
//如果被添加的集合的类型是LinkedList 那么elements = new ArrayList< E >();
        Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
//创建一个节点，并用头结点的previous指针指向这个节点（这里用指针来形容previous我觉得更形象）
        Link<E> previous = voidLink.previous;
//遍历elements
for (E e : elements) {
//每遍历一次，就重新创建一个Link节点
            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;
    }

图形说明一切：

1.由于voidLink的previous指向的是自己。所以previous和voidLink表示的是同一个节点。
2.创建newLink节点，并把newLink节点的previous指针指向previous节点
3.把pevious节点的next指针指向newLink节点

4.把newLink节点重新赋值给previous节点 2,3,4三个操作完成一次循环。

5.经过多次循环后,最终形成了这种双向循环链表

下面这段代码不是很理解，如果要添加的集合和自身相等，
那么 elements=new ArrayList< E >(collection)
否则 elements = collection 这是在搞什么？ 我觉得这样做的目的是转成ArrayList遍历时候更快。

Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;

说到这里，LinkedList的构造方法就一目了然了。LinkedList(Collection< ? extends E> collection)方法会通过addAll()方法，将集合添加到LinkedList中。

下面继承自LinkedList爸爸的方法
继承AbstractSequentialList方法

在指定位置添加元素
1 add(int location, E object)

 @Override
public void add(int location, E object) {
//下标值必须不能为负数，且要小于节点的数量
if (location >= 0 && location <= size) {
//定义节点 并指向头结点
Link<E> link = voidLink;
//如果要插入的位置为LinkedList的前半部分
if (location < (size / 2)) {
//1 一个一个的找 直到找到下标值为location的节点 并把该节点赋给link
                for (int i = 0; i <= location; i++) {
link = link.next;
                }
            } else {//如果要插入的位置为LinkedList的后半部分
//同上 从后往前找
                for (int i = size; i > location; i--) {
link = link.previous;
                }
            }
//2 找到link的前一个节点previous
Link<E> previous = link.previous;
//创建newLink 并把newLink的previous指向previous,next指向link
Link<E> newLink = new Link<E>(object, previous, link);
//5 把prvious的next指向newLink
            previous.next = newLink;
//6 把link的previous指向newLink
link.previous = newLink;
            size++;
            modCount++;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

向LinkedList中添加集合
2 addAll(int location, Collection< ? extends E> collection)

 @Override
public boolean addAll(int location, Collection<? extends E> collection) {
if (location < 0 || location > size) {
throw new IndexOutOfBoundsException();
        }
int adding = collection.size();
if (adding == 0) {
return false;
        }
        Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;

        Link<E> previous = voidLink;
if (location < (size / 2)) {
for (int i = 0; i < location; i++) {
                previous = previous.next;
            }
        } else {
for (int i = size; i >= location; i--) {
                previous = previous.previous;
            }
        }
        Link<E> next = previous.next;
for (E e : elements) {
            Link<E> newLink = new Link<E>(e, previous, null);
            previous.next = newLink;
            previous = newLink;
        }
        previous.next = next;
        next.previous = previous;
        size += adding;
        modCount++;
return true;
    }

这个方法就像是add(Collection< ? extends E> collection)和add(int index,Object object)的结合体。首先找到要插入的位置。再遍历集合的元素，并插入到指定位置。

获取下标值为index的节点的数据
3 get(int location)

@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();
    }

没什么可解释的。和add(int index,E object)差不多。不同的是找到下标值为index的节点后，直接将此节点的data返回。

下个方法是 listIterator(int location) 所以先看下迭代器LinkIterator的实现
LinkIterator
LinkIterator的成员变量
pos表示当前遍历的位置，expectedModCount表示集合被操作的次数

int pos, expectedModCount;

list表示将要遍历的LinkedList

final LinkedList<ET> list;

link表示当前遍历到的节点，lastLink节点也表示当前遍历到的节点。但是必须调用next方法才会有lastLink=link.并且每次remove后，lastLink=null;

Link<ET> link, lastLink;

LinkIterator的构造方法

LinkIterator(LinkedList<ET> object, int location) {
//把需要遍历的LinkedList赋给成员变量list
list = object;
//被操作的次数
            expectedModCount = list.modCount;
//判断开始遍历的位置是否是非负数，并在集合长度的范围内
if (location >= 0 && location <= list.size) {
// pos ends up as -1 if list is empty, it ranges from -1 to
// list.size - 1
// if link == voidLink then pos must == -1
link = list.voidLink;
//如果开始遍历的位置在集合前半部分
if (location < list.size / 2) {
//从头结点开始遍历 遍历找到下标为location的节点
                    for (pos = -1; pos + 1 < location; pos++) {
link = link.next;
                    }
                } else {//从头结点向后遍历，找到下标为location的节点
                    for (pos = list.size; pos >= location; pos--) {
link = link.previous;
                    }
                }
            } else {
                throw new IndexOutOfBoundsException();
            }
        }

添加一个元素
1 add(ET object)
此方法和LinkedList的方法基本一样，插入的位置是下表为location的下一个节点。首先找到将要被插入位置的及诶单

public void add(ET object) {
if (expectedModCount == list.modCount) {
//被添加节点下一个节点
Link<ET> next = link.next;
//被插入的新节点位于link的下个节点，next的前一个节点。
Link<ET> newLink = new Link<ET>(object, link, next);
//给
link.next = newLink;
                next.previous = newLink;
//给插入节点的位置重新赋值
link = newLink;
                lastLink = null;
                pos++;
                expectedModCount++;
//结合节点数加1
list.size++;
list.modCount++;
            } else {
                throw new ConcurrentModificationException();
            }
        }

不明白这段的含义
if (expectedModCount == list.modCount)

从前往后遍历时，判断是否还有下一个节点
2 hasNext()

public boolean hasNext() {
return link.next != list.voidLink;
        }

从后往前遍历时，判断是否还有前一个节点
3 hasPrevious()

public boolean hasPrevious() {
return link != list.voidLink;
        }

返回遍历到的当前节点的下一个节点的data属性。即返回节点的数据。
4 next()

public ET next() {
if (expectedModCount == list.modCount) {
                LinkedList.Link<ET> next = link.next;
if (next != list.voidLink) {
                    lastLink = link = next;
                    pos++;
return link.data;
                }
                throw new NoSuchElementException();
            }
            throw new ConcurrentModificationException();
        }

返回遍历到的当前节点的下一个节点的下标值。
5 nextIndex()

public int nextIndex() {
return pos + 1;
        }

返回当前节点的前一个节点的data属性。和next（）方法基本一样，只是遍历的方向相反。
6 previous()

 public ET previous() {
if (expectedModCount == list.modCount) {
if (link != list.voidLink) {
                    lastLink = link;
link = link.previous;
                    pos--;
return lastLink.data;
                }
                throw new NoSuchElementException();
            }
            throw new ConcurrentModificationException();
        }

返回当前遍历节点的前一个节点的下标值。
7 previousIndex()

public int previousIndex() {
return pos;
        }

移除当前遍历的节点
8 remove()

 public void remove() {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
Link<ET> next = lastLink.next;
Link<ET> previous = lastLink.previous;
                    next.previous = previous;
                    previous.next = next;
if (lastLink == link) {
                        pos--;
                    }
link = previous;
                    lastLink = null;
                    expectedModCount++;
list.size--;
list.modCount++;
                } else {
                    throw new IllegalStateException();
                }
            } else {
                throw new ConcurrentModificationException();
            }
        }

重新给当前节点的数据赋值
9 set(ET object)

public void set(ET object) {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
                    lastLink.data = object;
                } else {
throw new IllegalStateException();
                }
            } else {
throw new ConcurrentModificationException();
            }
        }

接着继承自AbstractSequentialList的方法。

返回当前集合的迭代器。并且迭代器从location开始遍历
4 listIterator(int location)

@Override
public ListIterator<E> listIterator(int location) {
return new LinkIterator<E>(this, location);
    }

移除下标为location的节点。
5 remove(int location)

 @Override
    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;
                }
            }
            Link<E> previous = link.previous;
            Link<E> next = link.next;
            previous.next = next;
next.previous = previous;
            size--;
            modCount++;
return link.data;
        }
        throw new IndexOutOfBoundsException();
    }

执行过程为:

• 先找到需要移除的节点link
• 再分别找到将被移除的节点link的前一个节点和后一个节点

• 在把link的前一个节点的next指针指向link的后一个节点。把link的后一个节点的previous指针指向link的前一个节点

  将下标值为location的节点的data属性替换成object
  6 set(int location, E object)

@Override
    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();
    }

下面继承自LinkedList爷爷的方法
继承自AbstractList的方法

把新节点添加到末尾
1 add(E object)

@Override
public boolean add(E object) {
return addLastImpl(object);
    }

清空所有节点
2 clear()

@Override
public void clear() {
if (size > 0) {
            size = 0;
            voidLink.next = voidLink;
            voidLink.previous = voidLink;
            modCount++;
        }
    }

找到节点的data和object相等的节点的下标值
3 indexOf(Object object)

  @Overrid
    public int indexOf(Object object) {
int pos = 0;
        Link<E> link = voidLink.next;
if (object != null) {
while (link != voidLink) {
if (object.equals(link.data)) {
return pos;
                }
link = link.next;
pos++;
            }
        } else {
while (link != voidLink) {
if (link.data == null) {
return pos;
                }
link = link.next;
pos++;
            }
        }
return -1;
    }

从上述代码可以看出，如果要找的data不是空，那么就从前往后找到第一个data符合的下标值.如果是空，也是从前往后，找到第一个data为空的节点的下标值。

从后往前找到LinkedList中第一个节点中的data和object相等的节点下标值。和前一个indexOf()方法找的方向正相反。
4 lastIndexOf(Object object)

 @Override
    public int lastIndexOf(Object object) {
int pos = size;
        Link<E> link = voidLink.previous;
if (object != null) {
while (link != voidLink) {
pos--;
if (object.equals(link.data)) {
return pos;
                }
link = link.previous;
            }
        } else {
while (link != voidLink) {
pos--;
if (link.data == null) {
return pos;
                }
link = link.previous;
            }
        }
return -1;
    }

下面继承自LinkedList祖爷爷的方法
继承自AbstractCollection< E>的方法

在LinkedList的构造方法中曾经调用过这个方法。不再解释。
1 addAll(Collection< ? extends E> collection)

@Override
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;
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;
    }

判断集合的节点中是否有包含object的节点
2 contains(Object object)

@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;
    }

从前往后找到节点的data和object相等的节点

移除集合中节点的数据和object相等的节点
3 remove(Object object)

@Override
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
    }

返回LinkedList集合的长度
4 size()

@Override
public int size() {
return size;
    }

把集合转成数组
5 toArray()

@Override
    public Object[] toArray() {
int index = 0;
        Object[] contents = new Object[size];
        Link<E> link = voidLink.next;
while (link != voidLink) {
            contents[index++] = link.data;
link = link.next;
        }
return contents;
    }

遍历Linked集合，并把集合的每个数据添加到一个数组中。

把集合转成指定的数组
6 toArray(T[] contents)

 @Override
@SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] contents) {
int index = 0;
//如果指定的数组比集合的长度小
if (size > contents.length) {
//获取创建数组的类型
            Class<?> ct = contents.getClass().getComponentType();
//重新创建一个和集合的长度同样大数组
            contents = (T[]) Array.newInstance(ct, size);
        }
        Link<E> link = voidLink.next;
//遍历集合的元素，并添加到数组中
while (link != voidLink) {
            contents[index++] = (T) link.data;
link = link.next;
        }
        //（应该有index==contents.length） 这里表示指定的数组比集合长度大  把数组被遍历赋值的最后的一个元素后的第一个元素置为空。
if (index < contents.length) {
            contents[index] = null;
        }
return contents;
    }

不明白这里为啥要置空
contents[index] = null;
/**
* Returns an array containing all elements contained in this
* {@code LinkedList}. If the specified array is large enough to hold the
* elements, the specified array is used, otherwise an array of the same
* type is created. If the specified array is used and is larger than this
* {@code LinkedList}, the array element following the collection elements
* is set to null.
*
* @param contents
* the array.
* @return an array of the elements from this {@code LinkedList}.
* @throws ArrayStoreException
* if the type of an element in this {@code LinkedList} cannot
* be stored in the type of the specified array.
*/
这是官方的注释，我自己翻译后的意思是：
返回一个数组，这个数组包含LinkedList的所有元素。如果传入的指定数组比集合的数组大。那么这个指定的数组将被使用，否则的话，将会创建一个和指定数组类型一样的数组。如果指定的数组被使用，并且比LinkedList的长度大，那么这个数组被添加的集合元素后的元素将被置空。

下面实现Deque接口的方法
实现 Deque 的方法

把新节点插入到集合的头部，其data为object.
1 addFirst(E object)

public void addFirst(E object) {
        addFirstImpl(object);
    }

把新节点插入到集合的头部，其data为object.
2 addLast(E object)

public void addLast(E object) {
        addLastImpl(object);
    }

返回集合的第一个节点的data
3 getFirstImpl()

private E getFirstImpl() {
        Link<E> first = voidLink.next;
if (first != voidLink) {
return first.data;
        }
throw new NoSuchElementException();
    }

返回集合的最后一个节点的data
4 getLast()

public E getLast() {
        Link<E> last = voidLink.previous;
if (last != voidLink) {
return last.data;
        }
throw new NoSuchElementException();
    }

移除集合的第一个节点，并返回该节点的data
5 removeFirst()

public E removeFirst() {
return removeFirstImpl();
    }

private E removeFirstImpl() {
        Link<E> first = voidLink.next;
if (first != voidLink) {
            Link<E> next = first.next;
            voidLink.next = next;
next.previous = voidLink;
            size--;
            modCount++;
return first.data;
        }
        throw new NoSuchElementException();
    }

移除头节点的前一个节点，并返回该节点的data
6 removeLast()

public E removeLast() {
return removeLastImpl();
    }

private E removeLastImpl() {
        Link<E> last = voidLink.previous;
if (last != voidLink) {
            Link<E> previous = last.previous;
            voidLink.previous = previous;
            previous.next = voidLink;
            size--;
            modCount++;
return last.data;
        }
throw new NoSuchElementException();
    }

这里的ReverseLinkIterator和之前的LinkIterator一样，只是迭代的方向是相反的。
获得一个反向迭代器的实例
7 descendingIterator()

public Iterator<E> descendingIterator() {
return new ReverseLinkIterator<E>(this);
    }

8 offerFirst(E e)

public boolean offerFirst(E e) {
return addFirstImpl(e);
    }

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;
    }

8 offerLast(E e)

 public boolean offerLast(E e) {
return addLastImpl(e);
    }

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;
    }

返回第一个节点的数据，如果是空集合，返回null
9 peekFirst(E e)

public E peekFirst() {
return peekFirstImpl();
    }

private E peekFirstImpl() {
        Link<E> first = voidLink.next;
return first == voidLink ? null : first.data;
    }

返回集合的最后一个节点的数据，如果是空集合，返回null
9 peekLast

public E peekLast() {
        Link<E> last = voidLink.previous;
return (last == voidLink) ? null : last.data;
    }

返回第一个节点的数据，如果是空集合，返回null.并把第一个节点移出集合
10 pollFirst()

 public E pollFirst() {
return (size == 0) ? null : removeFirstImpl();
    }

返回最后一个节点的数据，如果是空集合，返回null.并把最后一个节点移出集合
11 pollFirst()

public E pollLast() {
return (size == 0) ? null : removeLastImpl();
    }

和pollFirst()一样，不同的是如果集合为空，这里会抛异常，而不是返回一个null
12 pop()

public E pop() {
return removeFirstImpl();
    }

添加一个节点到集合的头部
12 push()

public void push(E e) {
        addFirstImpl(e);
    }

移除第一个不为null的节点
13 removeFirstOccurrence(Object o)

public boolean removeFirstOccurrence(Object o) {
return removeFirstOccurrenceImpl(o);
    }

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();
if (o == null ? element == null : o.equals(element)) {
                iter.remove();
return true;
            }
        }
return false;
    }

移除最后一个不为null的节点
14 removeLastOccurrence(Object o)

public boolean removeLastOccurrence(Object o) {
        Iterator<E> iter = new ReverseLinkIterator<E>(this);
return removeOneOccurrence(o, iter);
    }

在集合的尾部增加一个节点
15 offer(E o)

public boolean offer(E o) {
return addLastImpl(o);
    }

移除第一个元素并返回 如果集合元素为空，返回null
16 poll()

public E poll() {
return size == 0 ? null : removeFirst();
    }

移除第一个节点
17 remove()

public E remove() {
return removeFirstImpl();
    }

返回第一个节点的data，如果集合为空，返回null
18 peek()

public E peek() {
return peekFirstImpl();
    }

返回第一个节点 要讲求集合不能为空，否则会报异常
19 element()

public E element() {
return getFirstImpl();
    }

总结：

• LinkedList是一种线性的双向回环的链表结构。
• 相对于ArrayList,LinkedList的删除效率较高，因为通过指针的改变来实现。查找效率较慢。因为LinkedList的存储位置不是连续的。