Java:LinkedList源码分析

引言

LinkedList是Java集合中重要的一个实现,其底层才用双向链表结构。和ArrayList一样,LinkedList也支持空值和重复值。由于LinkedList底层基于链表实现,存储过程中,无需像ArrayList那样进行扩容.但有得必有失，LinkedList存储元素的节点需要额外的空间前驱和后继的引用.另外,LinkedList在头部和尾部插入效率比较高,但是在制定位置进行插入时,效率一般.原因是,在指定位置插入需要定位到该位置处的节点,此操作的时间复杂度为O(N)。最后,LinkedList是非线程安全的集合类,并发环境下,多个线程同时操作LinkeList,会引发不可预知的错误.

结构体系

从结构体系我们可以大致其总结特性：

• 实现了List接口，提供了对数据的增删查该功能
• 实现了Deque接口,可用于双端队列
• 实现了Cloneable接口,可被浅拷贝
• 实现了Serializable接口,可被序列化

属性

 transient int size = 0; //表示元素的个数
 transient Node<E> first;//1.8中 结构是双向链表,所以这是头结点
 transient Node<E> last; //尾节点
复制代码

构造函数

• 无参构造函数

   public LinkedList() {
      }
  复制代码

  啥也不干。
• 带集合参数的构造函数

    public LinkedList(Collection<? extends E> c) {
          this();
          addAll(c);
      }
      
      public boolean addAll(Collection<? extends E> c) {
      return addAll(size, c);
  }
  //可以将addAll方法理解成一个插入方法 index即为准备插入节点下标
  public boolean addAll(int index, Collection<? extends E> c) {
      checkPositionIndex(index); //检查下标 区间为 0到size
  
      Object[] a = c.toArray();  //调用集合的toArray()方法将其转化为数组
      int numNew = a.length; //获取数组的长度
      if (numNew == 0) //长度为0 直接返回 表示addAll失败
          return false;
  
      Node<E> pred, succ; //prev表示前置节点 succ表示后置节点
      if (index == size) { //如果是在尾部插入
          succ = null; 后置节点为null
          pred = last; 前置节点为最后一个
      } else {
          succ = node(index); //后置节点为index对应的节点 
          pred = succ.prev; //前置节点为 index对应节点的前一个
      }
  
      for (Object o : a) { //增强for循环 代码更加简介
          @SuppressWarnings("unchecked") E e = (E) o;
          Node<E> newNode = new Node<>(pred, e, null); //实例节点的时候赋值前置节点以及元素
          if (pred == null) //如果前置节点为空，则该节点为头结点
              first = newNode; 
          else
              pred.next = newNode; //否则的话设置新节点为前置节点的下一个节点
          pred = newNode; //将当前的节点作为新的前置节点
      }
      //遍历完成后 需要将最后一个节点与后置节点连接
      if (succ == null) { //如果后置节点为null 则表示最后一个节点即为尾部节点
          last = pred;
      } else { //否则,将最后一个节点与尾部连接
          pred.next = succ;
          succ.prev = pred;
      }
  
      size += numNew; //更新元素的大小
      modCount++; //修改更改的次数
      return true; //返回true表示更新成功
  }
  private void checkPositionIndex(int index) {
      if (!isPositionIndex(index))
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }
  private boolean isPositionIndex(int index) {
      return index >= 0 && index <= size;
  }
  复制代码

增加元素

• add(E e)

  public boolean add(E e) {
          linkLast(e);
          return true;
      }
      
      void linkLast(E e) {
      final Node<E> l = last; //得到last节点
      final Node<E> newNode = new Node<>(l, e, null); //新建连接左边连接last节点
      last = newNode; //将新的节点赋值给last
      if (l == null) //如果 最初的last节点为空 则 当前节点为头结点
          first = newNode;
      else
          l.next = newNode; //否则 将新节点与最初的last节点相连
      size++; //增加元素个数
      modCount++; //增加修改次数
  }
  复制代码

  该方法比较比较简单,只是创建了一个新节点插入在了链表的尾部而已.
• add(int index, E element),可以把该方法当做单个插入的方法

  public void add(int index, E element) {
          checkPositionIndex(index); //检查下标是否合法
  
          if (index == size) //如果是在尾部,插入在尾部即可
              linkLast(element);
          else //否则,插在node(index)节点之前
              linkBefore(element, node(index));
      }
      
      void linkBefore(E e, Node<E> succ) {
      // assert succ != null;
      final Node<E> pred = succ.prev; //取得前置节点引用
      final Node<E> newNode = new Node<>(pred, e, succ); //建立节点以及关联左右节点
      succ.prev = newNode; //连接后面
      if (pred == null) //连接前面 如果前置节点为null 则将当前节点设置为头节点
          first = newNode;
      else //否则与前置节点相连接
          pred.next = newNode;
      size++;
      modCount++;
  }
  复制代码

获取元素

• get(int index)

  public E get(int index) {
          checkElementIndex(index); //检查下标是否合法
          return node(index).item; //只杰根据node方法查找到节点并返回其元素即可
      }
       Node<E> node(int index) {
          // assert isElementIndex(index);
  
          if (index < (size >> 1)) { //位运算 表示 index<size/2 即偏向头结点
              Node<E> x = first;
              for (int i = 0; i < index; i++)
                  x = x.next;
              return x;
          } else { //偏向尾部节点
              Node<E> x = last;
              for (int i = size - 1; i > index; i--)
                  x = x.prev;
              return x;
          }
      }
  复制代码

  可以看到，双向链表在这里起到的作用,在查找的时候,先根据index判断节点更靠近头部还是尾部,提升查找的效率。

删除元素

• remove(int index)

  public E remove(int index) {
          checkElementIndex(index);
          return unlink(node(index));
      }
      
      E unlink(Node<E> x) {
          // assert x != null;
          final E element = x.item;
          final Node<E> next = x.next;
          final Node<E> prev = x.prev;
  
          if (prev == null) {/表示移除的为头结点
              first = next; 
          } else { 
              prev.next = next;
              x.prev = null; 
          }
  
          if (next == null) { 
              last = prev;
          } else {
              next.prev = prev;
              x.next = null;
          }
  
          x.item = null;
          size--;
          modCount++;
          return element;
      }
  复制代码

  检查下标合法后,直接调用unlink方法将该节点移除.在unlink方法中可以看到,将被移除的节点的前后节点以及元素都赋值为null，方便GC回收.

修改元素

• set(int index, E element)

  public E set(int index, E element) {
          checkElementIndex(index);
          Node<E> x = node(index);
          E oldVal = x.item;
          x.item = element;
          return oldVal;
      }
  复制代码

也很简单,不再赘述,现实用node(int index)方法定位到对应节点,然后修改其值即可。

LinkedList总结

• 底层使用链表进行数据存储,不需要扩容
• 增加和删除元素效率比较高,执行相应的链表操作即可
• 查找和修改的效率比较低,虽然遍历之前根据下标判断了遍历起点,但是节点比较多的时候,效率会大幅缩减