跳到主要内容

LinkedList

  • LinkedList: 基于链表实现，由双向链表next、prev把数据节点穿插起来，并非所有的插入都是高效的，比如在中间区域插入，需要遍历元素找到插入位置
    Linked + List = 链表 + 列表 = LinkedList = 链表列表
    LinkedList

初始化​

  • LinkedList是链表结构，初始化不需要创建数组，但是构造函数提供了一些跟ArrayList相同的方式来初始化入参 

    // 初始化方式；普通方式
    LinkedList<String> list01 = new LinkedList<String>();
    list01.add("a");
    list01.add("b");
    list01.add("c");

    // 初始化方式；Arrays.asList
    LinkedList<String> list02 = new LinkedList<String>(Arrays.asList("a", "b", "c"));

    // 初始化方式；内部类
    LinkedList<String> list03 = new LinkedList<String>(){
        {add("a");add("b");add("c");}
    };

    // 初始化方式；Collections.nCopies
    LinkedList<Integer> list04 = new LinkedList<Integer>

插入​

  • 默认提供add，也可以指定位置插入，同时提供头插(addFirst)和尾插(addLast)

  1. 头插:
    头插 

    - ArrayList头插时，需要把数组元素通过Arrays.copyOf的方式移位，如果容量不足还需要扩容  
    - LinkedList头插时，则不需要考虑扩容及移位问题，直接把元素定位到首位，接点链条链接上即可  
    - 源码:  

      ```java showLineNumbers
      private void linkFirst(E e) {
          final Node<E> f = first;
          final Node<E> newNode = new Node<>(null, e, f);
          first = newNode;
          if (f == null)
              last = newNode;
          else
              f.prev = newNode;
          size++;
          modCount++;
      }
      ```  
      - first: 首节点，一直会被记录，方便头插  
      - 插入时会创建新的节点元素，`new Node<>(null, e, f)`，然后把新的头元素赋值给first  
      - 之后判断f节点是否存在，不存在则把头插节点作为最后一个节点，存在则用f节点的上一个链条prev链接  
      - 最后记录size大小，和元素数量modCount，modCount用于遍历时做校验，`modCount != expectedModCount`  
    - 头插时ArrayList需要做大量的位移和复制操作，而LinkedList只需要实例化一个对象

  2. 尾插:
    尾插

  • ArrayList尾插时不需要数据位移，比较耗时的是数据的扩容时需要拷贝迁移
  • LinkedList尾插时，与头插相比耗时点会在对象的实例化上
  • 源码: 
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    • 与头插代码基本无区别，first替换成last
    • 耗时点只在创建节点上，Node<E>
  • ArrayList尾插不需扩容时，不需要进行位移和数据拷贝，LinkedList需要创建对象，因此ArrayList不需扩容时性能更高
  1. 中间插:
    中间插
  • ArrayList中间插，定位时间复杂度为O(1)，主要耗时为数据迁移和容量不足时扩容
  • LinkedList中间插，链表的数据在实际插入时耗时较低，但定位元素的时间复杂度是O(n)，因此主要耗时为元素定位和元素实例化
  • 源码:
    使用add(位置、元素)方法插入 
    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    位置定位node(index):
    size >> 1，这部分的代码判断元素位置在左半区间，还是右半区间，在进行循环查找 
      Node<E> node(int index) {
          // assert isElementIndex(index);
          if (index < (size >> 1)) {
              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;
          }
      }
    执行插入: 
    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)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    • 找到指定位置后插入过程与头插、尾插区别不大
    • 插入过程中比较耗时的点在遍历寻找插入位置上
  • Linked在遍历查找位置上非常耗时，因此ArrayList中间插更高效

删除​

删除

  • 找到元素位置，把元素前后链连接上，假如删除首尾元素，操作则更加简单
  • 删除操作方法:
    删除操作方法
  • 源码:
    list.remove("a"); 
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    unlink(x)解链 
    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;
    }
    1. 获取待删除节点的信息: 元素item、元素的下一个节点next、元素的上一个节点prev
    2. 如果上个节点为空则吧待删除元素的下一个节点赋值给首节点，否则吧待删除节点的下一个节点赋值给待删除节点的上一个节点的子节点
    3. 同样待删除节点的下一个节点next,也执行2步骤的同样操作
    4. 把删除节点设置为null,并扣减size和modeCount数量

循环​

略