Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说java集合框架List子接口之LinkedList源码剖析「终于解决」,希望能够帮助你!!!。

感兴趣的话大家可以关注一下公众号 : 猿人刘先生 , 欢迎大家一起学习 , 一起进步 , 一起来交流吧!

LinkedList

LinkendList是一个双向链表 , 并且实现了Deque接口 , 可以作为一个队列来使用 , 虽然LinkendList是线性结构 , 但是数据的存储并不是按照线性的接口来存储的 , 而是在每一个节点里存数据及下一个节点的地址, 同时实现了Cloneable接口 , 支持拷贝 , 并且实现了java.io.Serializable支持序列化和反序列化

• Cloneable , Serializable接口直通车 : java框架集合List子接口之ArrayList源码剖析

• 数据结构直通车 : 数据结构之顺序存储结构和链式存储结构分析 , 图文并茂 , 又涨姿势了

• 队列直通车 : 线性数据结构之队列(Queue)

Deque

Deque是double ended queue的简称，支持两端的元素插入和移除 ,习惯上称之为双端队列。大多数Deque 实现对它们可能包含的元素的数量没有固定的限制，但是该接口支持容量限制的deques以及没有固定大小限制的deque

Deque同时扩展了Queue接口，当Deque作为队列的时候，会产生FIFO(先进先出)行为。元素添加在双端队列的末尾并从头开始删除。

双端队列的功能就是既可以从队首添加 , 也可以从队尾添加 , 既可以从队尾获取 , 也可以从队首获取

Deque和Queue方法对比

可以看出LinkendList又是一个集合 , 又是一个队列 , 又是一个栈 , 功能还是比较强大的 , 但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。

// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// 推荐的写法：
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");

可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类。

LinkendList构造方法

  // 当前列表的节点个数
  transient int size = 0;
  // 第一个节点
  transient Node<E> first;
  // 最后一个节点 
  transient Node<E> last;
    /** * Constructs an empty list. */
    public LinkedList() { 
   
    }

    /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */
    public LinkedList(Collection<? extends E> c) { 
   
        this();
        addAll(c);
    }

LinkendList常用方法

addAll()

    public boolean addAll(int index, Collection<? extends E> c) { 
   
        // 检查下标是否越界
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        // 需要添加的集合为空，直接返回
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        // 插入位置与当前列表数量相同，表示为尾部插入 
        if (index == size) { 
   
            succ = null;
            pred = last;
        } else { 
   
            // 找到index所在的节点 
            succ = node(index);
            // index所在位置的前一个节点
            pred = succ.prev;
        }
        
        // 遍历需要添加的集合，逐个插入
        for (Object o : a) { 
   
            // 创建一个新的节点，以 pred 为前一个节点，值为 e，null 为后一个节点
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            // 如果 pred 为空，说明是在头部插入
            if (pred == null) 
                // 也就是说新建的节点是第一个节点
                first = newNode; 
            else // pred 不为空，说明是在中间或者尾部插入
                // pred 的下一个节点连接上新创建的节点
                pred.next = newNode; 
            // 依次插入
            pred = newNode; 
        }
        // 如果 succ 为空，说明是在尾部插入
        if (succ == null) { 
    
            // 所以最后插入的元素就是最后一个元素
            last = pred;
        } else { 
    // succ 不为空，说明是在中间插入
            // 最后插入的元素连接上后面的一段
            pred.next = succ;
            // 后面的一段第一个元素连接上前面的一段
            succ.prev = pred;
        }
        // 数量合并
        size += numNew;
        // 修改次数+1
        modCount++;
        return true;
    }

检查数组下标越界方法

private void checkPositionIndex(int index) { 
   
  if (!isPositionIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) { 
   
  return index >= 0 && index <= size;
}

看到了很熟悉的异常 IndexOutOfBoundsException，就是根据链表大小检查一下

时间复杂度

addAll()属于一种浅拷贝的方式 , 通过for循环来把一个集合的元素遍历添加到另一个几集合 , 所以时间复杂度是O(N)

add()

public boolean add(E e) { 
   
  linkLast(e);
  return true;
}

public void add(int index, E element) { 
   
  // 检查 index 是否越界，上面分析过了
  checkPositionIndex(index);

  // 插入位置与当前数量相同，说明是尾部插入
  if (index == size) 
    linkLast(element);
  else
    linkBefore(element, node(index));
}

public void addFirst(E e) { 
   
  linkFirst(e);
}

public void addLast(E e) { 
   
  linkLast(e);
}

可以看到 , 主要调用了linkBefore() linkFirst() linkLast() 这几个方法 , 所以我们接下来分析这几个方法

// 在某个节点前插入一个元素
void linkBefore(E e, Node<E> succ) { 
   
  // assert succ != null;
  // 获取到 succ 的上一个节点
  final Node<E> pred = succ.prev; 
  // 创建一个新的节点，连接到 succ 上一个节点后面
  final Node<E> newNode = new Node<>(pred, e, succ);
  // 将 succ 连接到 newNode 后面
  succ.prev = newNode; 
  // 如果 succ 的上一个节点为空，说明 succ 为头部节点
  if (pred == null) 
    // 直接将 newNode 设为头部节点
    first = newNode; 
  else // 如果 succ 的上一个节点不为空，说明 succ 为中间或者尾部节点
    // 将 succ 的上一个节点关联到 newNode 上
    pred.next = newNode; 
  size++;
  modCount++;
}

linkFirst()和linkLast()逻辑相似 , 所以就分析linkFirst

// 插入一个元素到头节点
private void linkFirst(E e) { 
   
  final Node<E> f = first; // 当前第一个节点
  // 创建了一个新节点，以 null 为前一个节点、e 为值、当前第一个节点为下一个节点
  final Node<E> newNode = new Node<>(null, e, f);
  first = newNode; // 设置新建的节点为第一个节点
  if (f == null) // 当前第一个节点为空，说明列表为空
    last = newNode; // 所以最后一个节点为当前插入的节点
  else // 当前第一个节点不为空，说明列表不为空
    f.prev = newNode; // 当前列表头部连接上插入的节点
  size++;
  modCount++;
}

时间复杂度

add()方法有三种增加方式 , 头插 , 尾插 , 中间插入 , 头插和尾插时间复杂度为O(1) , 因为不需要通过遍历找到上一个节点 , 但是中间插入时间复杂度为O(N) , 因为需要调用node(int index)找到下标对应的元素 , 然后在这个元素后面插入

get()

public E get(int index) { 
   
  // 检查 index 是否越界，上面分析过了
  checkElementIndex(index);
  return node(index).item;
}

Node<E> node(int index) { 
   
  // 如果 index 小于 size 的一半，从开头开始查找 
  if (index < (size >> 1)) { 
   
    Node<E> x = first;
    // 从头开始查找,直到 i == index
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else { 
    // 如果 index 大于 size 的一半，从尾部开始查找
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

getFirst()和getLast()

public E getFirst() { 
   
  final Node<E> f = first;
  if (f == null)
    throw new NoSuchElementException();
  return f.item;
}

public E getLast() { 
   
  final Node<E> l = last;
  if (l == null)
    throw new NoSuchElementException();
  return l.item;
}

时间复杂度

get()方法的时间复杂度也要分开说明 , 因为LinkendList的实现中保存了头尾元素 , 所以可以直接获取 , 时间复杂度为O(1) , 但是如果是根据下标获取 , 那么就要通过遍历来获取下标对应的元素 , 时间复杂度为O(N)

remove()

public E remove(int index) { 
   
  // 检查 index 是否越界
  checkElementIndex(index);
  return unlink(node(index));
}

public E removeFirst() { 
   
  final Node<E> f = first;
  if (f == null)
    throw new NoSuchElementException();
  return unlinkFirst(f);
}

public E removeLast() { 
   
  final Node<E> l = last;
  if (l == null)
    throw new NoSuchElementException();
  return unlinkLast(l);
}

可以看到 , remove()方法和add()方法类似 , 也是分别调用了unlink() unlinkFirst() unlinkLast() , 分别表示删除某个节点 , 删除头节点 , 删除尾结点

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;
  }
  // 当前节点元素设置为空，方便 GC
  x.item = null; 
  size--;
  // 修改次数+1
  modCount++;
  return element;
}

private E unlinkFirst(Node<E> f) { 
   
  // assert f == first && f != null;
  // 获取到当前节点的元素
  final E element = f.item;
  // 获取到当前节点的下一个元素
  final Node<E> next = f.next; 
  f.item = null;
  f.next = null; // help GC
  // 将当前节点的下一个节点设置为头部节点
  first = next;
  // 如果下一个节点为空，说明链表只有一个节点
  if (next == null)
    // 清空尾部节点
    last = null; 
  else // 否则，说明还有其他节点
    // 下一个节点已经设置为头部节点了
    // 所以清空一下与前一个节点的 关联
    next.prev = null; 
  size--; // 数量 -1
  modCount++;
  return element;
}

private E unlinkLast(Node<E> l) { 
   
  // assert l == last && l != null;
  final E element = l.item;
  final Node<E> prev = l.prev;
  l.item = null;
  l.prev = null; // help GC
  last = prev;
  if (prev == null)
    first = null;
  else
    prev.next = null;
  size--;
  modCount++;
  return element;
}

时间复杂度

删除的时间复杂度为O(1) , 直接找到需要删除的前驱节点及后继节点 , 然后将被删除元素的前驱节点指针指向后继节点即可 , 因为是双向链表 , 所以可以直接操作前驱节点 , 如果是单向链表的话就不行

clear()

public void clear() { 
   
  // 遍历一遍全部设置为空
  for (Node<E> x = first; x != null; ) { 
   
    Node<E> next = x.next;
    x.item = null;
    x.next = null;
    x.prev = null;
    x = next;
  }
  first = last = null;
  size = 0;
  modCount++;
}

时间复杂度

从代码的实现不难看出 , clear()方法的时间复杂度为O(N) , 因为是通过遍历然后将元素依次置空 , 所以时间复杂度为O(N)

更多方法可以查看 https://www.runoob.com/manual/jdk11api/java.base/java/util/LinkedList.html

小结

LinkendList从物理结构来说是一种线性结构 , 而从逻辑结构来说是一种链式存储结构 , 虽然是线性结构 , 但是并不会按照线性的顺序存储 , 而是分散存储在内存中 , 通过指针来建立节点与节点之间的联系, 同时实现了Deque这也说明它是一个双向链表 , 在源码中 , 没有看到它对线程安全问题的处理 , 所以它同时还是一个线程不安全的链表 , 也没有看到不允许插入null元素 , 重复元素的处理 , 所以它又是一个允许重复元素以及null元素的链表