Android版数据结构与算法(三):基于链表的实现LinkedList源码彻底分析

版权声明：本文出自汪磊的博客，未经作者允许禁止转载。

LinkedList 是一个双向链表。它可以被当作堆栈、队列或双端队列进行操作。LinkedList相对于ArrayList来说，添加，删除元素效率更高，ArrayList添加删除元素的话需移动数组元素，甚至还需要考虑到扩容数组长度。

一、LinkedList中成员变量及每个节点信息

源码如下：

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

1行，size代表当前链表中有多少个节点。

3行，voidLink指向链表的头部，稍后具体分析会有更近了解。

5-14行则定义了每个节点所包含的信息。

6行，data存储每个节点中的数据。

8行，存储每个节点指向的前一个与后一个节点信息。

10-14行则是节点的构造函数，在初始化的时候需要指定节点的数据，以及当前节点的前一个节点和后一个节点。

数组的每一项只包含数据信息，而在链表中每一项不仅包含数据还包含前一项，后一项的信息，在C语言中是通过指针来链接起来的，而在java中我们只需要定义一个实体类就可以了，每个节点类似如下结构：

二、LinkedList中初始化方式

LinkedList初始化有如下两种方式：

public LinkedList()

public LinkedList(Collection<? extends E> collection)

接下来，挨个分析。

LinkedList()源码如下：

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

2行，构造一个空节点voidLink，数据，前向指针，后向指针都为null。（java中没有指针这一概念，为了方便讲解，这里就叫做指针了）

3，4行，voidLink前向指针与后向指针都指向自身。

以上方式初始化一个LinkedList后链表样式如下：

接下来看下LinkedList(Collection<? extends E> collection)方式如何创建的，源码如下：

    public LinkedList(Collection<? extends E> collection) {
        this();
        addAll(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;
    }

2行，调用空参数的构造方法，逻辑上面已经讲了。this()方法调用完构造了一个空节点如下(上面已经说过)：

3行，调用addAll(collection)方法，主要逻辑在此方法中。

15行代码，创建一个新节点previous指向voidLink的前向指针，而此时前向指针指向自身，图示如下：

16-20行，遍历集合中每个元素加入链表中，接下来看看每个元素是怎么加入链表中的。

17行，创建一个新节点，新节点的值就是遍历出的元素e，前向指针指向previous所指向的节点，后向指针指向null，此时图示如下:

18行，previous的后向指针指向新节点。

19行，previous指向新节点。

18，19行完成后，图示如下：

好了，到此集合中一个元素就加入链表中了，不断遍历照此逻辑不断加入链表中。

voidLink指向链表的头结点，而previous则指向链表的尾节点。

假设集合中只有一个元素那么经过上述遍历后链表样式也就如上图所示了。

接下来看看21，22行逻辑。

21行，将previous的后向指针指向voidLink。

22行，voidLink的前向指针指向previous。

这样链表的首尾也就连接起来了，图示如下：

这样整个链表的初始化完成了，这样的首尾链接的链表叫做：双向循环链表。

好了，链表的初始化基本就这些玩意，接下来看看其余一些操作。

三、LinkedList中添加数据方式

假设添加之前LinkedList如图所示：

首先我们分析boolean add(E object)添加方法，源码如下：

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

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

其本质调用了addLastImpl(E object)方法。顾名思义，调用这个方法就是将元素放入链表的尾部。

7行，将头部节点voidLink的前向指针指向的节点赋值给oldLast，很简单，这里就不画出图示了。

8行，创建新节点newLink，值为放入的值object，前向指针指向oldLast,后向指针指向头指针voidLink，此时图示如下：

咦？怎么还有两条线指向voidLink呢？别急啊，还有逻辑没分析呢。

9行，头节点voidLink的前向指针指向新节点newLink。

10行，oldLast指向的节点的后向指针指向新节点。

经过9，10行逻辑后，链表变为图示：

到此，一个新数据就插入到链表尾部了，是不是也没那么复杂，整个过程就是对指针的操作。

接下来我们分析add(int location, E object) 可以向指定位置插入元素，源码如下：

    @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<E> previous = link.previous;
            Link<E> newLink = new Link<E>(object, previous, link);
            previous.next = newLink;
            link.previous = newLink;
            size++;
            modCount++;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

我们假设插入之前链表如下：

 

 并且我们要向位置3放入一个数据。

4行，link指向voidLink也就是指向头部节点。

5-13行，就是查找我们要插入的位置，这里有个优化，如果我们插入的位置靠前则从头部向后查找，如果插入的位置靠后，则从后向前查找。

5行，插入的位置location与整个链表长度的一半比较，如果小于链表长度一半则表明插入位置靠前，否则也就靠后了。

这里我们向位置3插入数据，明显位置靠后，所以执行的是9-13行逻辑。

10-12行逻辑执行完link定位到位置3，如图：

****link一开始指向的是头节点，也就是位置0的节点，这里经过两次循环最终定位到位置3处的节点。

接下来就是数据的插入逻辑，还是对各个节点指针的操作，这里再说一下，后续分析其他方法就不细说了。

14行，定义previous指向link指向节点的前一个节点，如图：

15行，新建一个节点，数据就是我们要放入的数据信息，前向指针指向previous指向的节点，后向指针指向link所指向的节点，如图：

16行，previous指向节点的后向指针指向newLink。

17行，link指向节点的前向指针指向newLink。

16，17行执行完链表变为如图：

到此，我们就将一个数据插入到链表中指定位置了。

链表的插入数据与数组相比不用考虑空间的扩容，以及后面的元素不用移动位置，而只需操作对应位置指针就可以了，可以说性能上提升很多。

四、LinkedList中删除数据方式

其实上面添加数据逻辑如果你真的理解了，删除数据的方式也就是大概看一下源码就明白了，同样操作相邻指针就可以了，这里简单说一下吧。

删除数据的方法主要有如下方式：

public boolean remove(Object object)//删除指定数据

public E remove(int location)//删除指定位置数据

public E removeFirst()//删除链表第一个数据

public E removeLast()//删除链表最后一个数据

首先我们看下删除指定位置数据方法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();
    }

是不是有种似曾相识的感觉，没错大体逻辑和向指定位置添加数据一样一样的。

4-13行，找出待删除位置的节点，优化的地方是判断一下删除的位置靠链表前半部分还是后半部分。

14-17行，就是操作指针删除对应位置节点，这里就不细说了，讲述添加方法逻辑的时候如果你真的理解了那么这里很easy。

至于其余删除方法也很简单，真的没什么特意要说的，就是对指针的操作。

链表的删除数据与数组相比没有后续数据的前移操作，同样只是对指定数据所在节点的指针进行操作就可以了，性能上也有所提升。

 五、LinkedList中更改数据方式

LinkedList中更改数据方法为：public E 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();
    }

大体逻辑也很简单了，4-13行同样查找指定位置元素，然后15行，就是将指定位置节点中的数据设置为我们设定的数据object就可以了，整个过程没有指针的操作，不看源码是不是还以为又是新建一个节点然后操作指针替换呢？其实不必那么麻烦，找到指定节点替换数据就可以了。

看完set源码，想必获取指定位置上数据也不难理解了，找到指定位置节点，然后返回节点数据就可以了，源码都不用看了。

六、LinkedList中查找是否包含某一数据

判断是否包含某一数据方法为public boolean 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;
    }

3行，link指向voidLink.next，这里需要注意一下：如果是空链表，也就是只有voidLink自己一个节点，那么voidLink.next指向的依然是voidLink节点，这里不明白看一下上面讲的初始化逻辑。如果链表中有其余数据，那么next指向的就是链表出去头结点的第一个节点了。

object不为null则执行4-10行逻辑，为null则执行11-18行逻辑。

5行，这里为什么判断link不等于voidLink呢才继续执行查找逻辑呢？两种情况，1：空链表，也就是只有voidLink自己，那么就没必要查找了。2：不是空链表，看下9行每次循环后link都会指向下一个节点，也就是挨个遍历链表的每一个节点，但是链表是循环链表，当遍历到link等于voidLink也就是已经把链表遍历一整遍了。

6-8行也就是挨个比较了，相等则找到了，说明链表中存在我们要查找的数据，直接返回true。

至于11-18行逻辑，就不用我多少了吧。

可以看到链表的查找与数组一样，需要挨个遍历链表中的每个数据项，如果数据量很大，那么效率是很低下的，怎么优化呢？答案是哈希表思想，这里不细说，下一篇分析hashmap的时候会体现这种思想。

七、LinkedList的队列与栈性质

这里简单提一下。

队列：一种数据结构，最明显的特性是只允许队头删除，队尾插入。

栈：同样是一种数据结构，特性是插入删除都在栈的顶部。

LinkedList提供了pop()与push(E e)方法使其有栈的特性。

LinkedList提供了addLast(E object)与E removeFirst()方法使其有队列的特性。

所以，我们要向实现栈与队列只需要新建一个类封装LinkedList就可以了。

八、总结

好了，到此LinkedList我想说的就基本就讲完了，只要理解了指针的操作，基本没什么难度，还有，不要单独看LinkedList，要与ArrayList比较来看，本质就是链表与数组的比较，下一篇讲到hashmap，更要将三者联系起来比较，提取出核心思想。

本片到此结束，希望对你有用。

青山不改，绿水长流，咱们下篇见！