从LinkedList的常用方法来解析它的内部实现

LinkedList作为一个常用的集合在我们项目开发当中经常会用到，它经常会拿来和ArrayList做比较，那我们今天就通过源码来解析下它内部的实现原理

构造方法

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

new了一个Link类，这个Link类包括：添加的数据data，链表上个对象和下个对象的引用；因为是初始化所以它的数据是null，对上一个和下一个的引用也是自己本身。

添加方法

    @Override
    public void add(int location, E object) {
         //如果location大于等于0，并且location小于等于size执行下面操作
         // 否则越界异常
        if (location >= 0 && location <= size) {
            Link<E> link = voidLink;
            //如果location小于总大小的1/2,就从链表的尾部找
            if (location < (size / 2)) {
                for (int i = 0; i <= location; i++) {
                    link = link.next;
                }
            } else {
                //如果location大于等于总大小的1/2,就从链表的头部找
                for (int i = size; i > location; i--) {
                    link = link.previous;
                }
            }
             
            //插入到location位置
            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();
        }
    }

当我们调用add(E e)方法的同时，方法内部又调用了add(int location, E object)方法，location是要添加数据的位置，下面我们通过一张图来看一下它的add机制。

QQ图片20170123105921.jpg

如果location是1，那么就从0开始循环找，然后把要添加的数据添加到0和1之间；
如果location是3，那么就从voidLinked header开始找，然后把数据添加到2和3之间。

再来看看其他add方法

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

addFirst方法

    public void addFirst(E object) {
        addFirstImpl(object);
    }
    
    //把object添加到链表的最尾部，因为我们取数据的时候是从尾部开始取的
    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;
    }

addLast方法

   public void addLast(E object) {
        addLastImpl(object);
    }
   //把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;
    }

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

跟添加数据获取location位置数据的逻辑是一致的，这边就不细说了。

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;
                }
            }
            //把locaiton位置的对象的上面和下面的对象关联起来
            Link<E> previous = link.previous;
            Link<E> next = link.next;
            previous.next = next;
            next.previous = previous;
            size--;
            modCount++;
            return link.data;
        }
        throw new IndexOutOfBoundsException();
    }

查找数据的逻辑和取值的逻辑是一致的，然后就是把location位置对象的上面和下面对象关联起来。

 @Override
    public boolean remove(Object object) {
        return removeFirstOccurrenceImpl(object);
    }
  //最后调用了此方法
    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;
    }

循环遍历，通过equals方法对比找到相同的数据，然后删除。

总结

LinkedList内部存储数据是以链表的形式存储的，查询数据需要从链表头或尾循环取值，所以会比ArrayList查询慢，添加和删除数据差不多，在特定的情况下添加数据ArrayList会稍慢，其他方法差别不会特别大。