Java常用集合LinkedList分析

LinkedList底层数据结构是一个具有头尾节点的双向链表。双向链表的优点就是通过某个节点访问其前驱和后驱表较方便。缺点是需要额外存储其前驱和后驱的空间。LinkeList链表允许null元素；
问题一：LinkedList如何初始化

LinkedList构造函数有两种，无参构造和带集合的构造函数
1.无参构造，初始化集合大小size=0，初始不用存储任何数据，内存占用低；
 public LinkedList() {
        this.size = 0;
 }

2.带集合的构造函数，创建一个大小和传入集合大小一致的链表，记录头尾节点
 public LinkedList(Collection<? extends E> c) {
        this();
        this.addAll(c);
 }
3.接着2我们来看下addAll方法，他的参数有index和传入的集合，猜想index应该是传入集合存储开始的地方。
 public boolean addAll(int index, Collection<? extends E> c) {
        //判断这个index是否超过链表有效位置的范围，超出的话会报IndexOutOfBoundsException.
        this.checkPositionIndex(index);
       //返回包含这个集合中所有数据的数组，感觉是个耗时操作
        Object[] a = c.toArray();
      //获取参数集合的长度，是构造之后链表的长度
        int numNew = a.length;
     //参数集合长度为0，说明不需要存储任何数据，就不用做任何事了直接返回。
        if (numNew == 0) {
            return false;
        } else {
      //辅助构造链表
            LinkedList.Node pred;
            LinkedList.Node succ;
        //index = this.size从链表尾部插入
            if (index == this.size) {
                succ = null;
                pred = this.last;
            } else {
       //index != this.size从链表中间插入
                succ = this.node(index);
                pred = succ.prev;
            }

            Object[] var7 = a;
            int var8 = a.length;
        //遍历参数集合的数组，从插入的位置index开始插入
            for(int var9 = 0; var9 < var8; ++var9) {
                Object o = var7[var9];
                LinkedList.Node<E> newNode = new LinkedList.Node(pred, o, (LinkedList.Node)null);
              //插入集合的第一个节点
                if (pred == null) {
                    this.first = newNode;
                } else {
               //上一个节点记录一下当前节点，形成链表
                    pred.next = newNode;
                }
                //pred记录当前节点，开始下一个节点的插入
                pred = newNode;
            }
           //succ =null说明是从链表尾部开始插入的，所以记录一下链表头部，就行了。
            if (succ == null) {
                this.last = pred;
            } else {
           //相反的不是从链表尾部插入，从第index个插入，index元素排在插入的数据后面，形成新链表。
                pred.next = succ;
                succ.prev = pred;
            }
         //记录新的链表长度
            this.size += numNew;
            ++this.modCount;
            return true;
        }
    }

问题二：LinkedList怎么插入数据？
LinkedList堆插入操作做了相关优化。由于其基于双端链表实现，所以其在头尾插入速度较快，在链表中部插入相对较慢。

    1.头部插入元素，直接通过头节点first插入，头节点变成第二个元素，更新头节点，非常简单。
    private void linkFirst(E e) {
        LinkedList.Node<E> f = this.first;
        LinkedList.Node<E> newNode = new LinkedList.Node((LinkedList.Node)null, e, f);
        this.first = newNode;
        if (f == null) {
            this.last = newNode;
        } else {
            f.prev = newNode;
        }

        ++this.size;
        ++this.modCount;
    }
 2.尾部插入元素，直接通过尾节点插入新元素 ，待插入节点变成新的尾节点。
    void linkLast(E e) {
        LinkedList.Node<E> l = this.last;
        LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);
        this.last = newNode;
        if (l == null) {
            this.first = newNode;
        } else {
            l.next = newNode;
        }

        ++this.size;
        ++this.modCount;
    }
 3.中间插入元素，如果index=链表长度则表示在链表尾部插入数据，否则实在指定元素之前插入元素。
    public void add(int index, E element) {
        this.checkPositionIndex(index);
        if (index == this.size) {
            this.linkLast(element);
        } else {
            this.linkBefore(element, this.node(index));
        }
    }
 4.在看linkBefore之前我看下node方法，这个方法是通过index找到链表中的某个数据。通过以下代码我们可以看到它使用了一次二分查找，提高了一次查找效率，但是随着数据增多这个函数的效率会变得越来越低。
   LinkedList.Node<E> node(int index) {
        LinkedList.Node x;
        int i;
        if (index < this.size >> 1) {
            x = this.first;
            for(i = 0; i < index; ++i) {
                x = x.next;
            }
            return x;
        } else {
            x = this.last;
            for(i = this.size - 1; i > index; --i) {
                x = x.prev;
            }
            return x;
        }
    }
 5.接着看下linkBefore方法。找到指定元素就非常好办了，生成新节点，把新节点放在指定元素的前面就可以了。
    void linkBefore(E e, LinkedList.Node<E> succ) {
        LinkedList.Node<E> pred = succ.prev;
        LinkedList.Node<E> newNode = new LinkedList.Node(pred, e, succ);
        succ.prev = newNode;
     //如果succ是头节点，还需要更新头节点指针。
        if (pred == null) {
            this.first = newNode;
        } else {
            pred.next = newNode;
        }
        ++this.size;
        ++this.modCount;
    }

问题三：LinkedList怎么删除元素
删除节点和增加节点都是通过node方法找到指定元素，然后删除指定节点，链表的基本操作，这里不再赘叙。