前言

LinkedList由于实现了Deque这个接口，所以可以当栈和队列使用。不过一般要用栈或队列的时候推荐使用ArrayDeque,所以这里就不讲LinkedList的栈和队列功能了🌚。本文主要讲些常用的方法。

LinkedList内部是由双链表组成的，里面存放着一个个Node，每个Node又包含三个元素(prev,item,next):

  • prev:指向前一个Node
  • item:存放存入的数据
  • next:指向下一个Node

链表的第一个Node的prev为null，最后个Node的next为null

我简单的画了一张图，可以看下

这个prev和next并不是指向null，因为内存中没有为null分配空间，这边是表示是prev和next为null；

 

本文内容

 

内部变量

相比于Arraylist，LinkedList内部变量就少得多，就只有三个，size存这当前元素的个数，first指向链表的第一个，last指向列表的最后一个

 

构造方法

无参构造方法

代码实现

List<String> list=new LinkedList<>();
复制代码

源码分析

无参构造只是初始化了数据，并未做任何操作(初始化 size=0 first=null last=null)

 

有参构造方法

代码实现

List<String> oldList=new LinkedList<>();
List<String> newList=new LinkedList<>(oldList);
复制代码

源码分析

由于篇幅有限，addAll()方法这边就不讲了，后面另写文章再讲，里面的操作就相当于把集合里的元素复制到新集合里面。

 

get方法

get(int index)

这里先讲get()方法，然后再讲add()方法，原因是插入方法里用到的调用的方法个get()方法里是一样的

代码实现

List<String> list=new LinkedList<>();
list.add("hui");
list.add("灰");
list.add("灰2");
list.add("灰3");
list.get(2);
复制代码

源码分析

 

  • checkElementIndex(int index)检查越界

 

 

  • node(int index)查找Node

 

add方法

add(E e)

代码实现

List<String> list=new LinkedList<>();
list.add("hui");
复制代码

源码分析

 

  • linkLast(E e)连接最后一个元素

 

  • Node<E>内部类

就像开头说的，每个Node里有三个，prev:指向前一个Node，item:存放存入的数据，next:指向下一个Node

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
复制代码

流程图

  • 第一次添加时的流程示意图

第一次添加时的流程示意图

  • 不是第一次添加

不是第一次添加

add(int index, E element)

代码实现

List<String> list=new LinkedList<>();
list.add("hui");
list.add("灰");
list.add(1,"hk");
复制代码

源码分析

这边插入元素时，先判断插入的位置是不是尾部，如果不尾部的话，先调用和get()那个一样的方法，来查找要插入位置的当前元素，然后进行插入操作

 

  • checkPositionIndex(int index)检查是否越界

这个检查越界的方法个get()检查越界的方法有点不同，它是可以等于size的，因为linkedList的索引设计也是从0开始的，所以size永远比索引大1

 

 

  • linkBefore(E e, Node<E> succ)插入元素操作

 

流程图

上面说的可能有点绕，看看流程图就明白了，哈哈

  • 添加的位置为第一个

添加的位置为第一个

  • 添加的位置为中间

添加的位置为中间

set方法

set(int index, E element)

代码实现

List<String> list=new LinkedList<>();
list.add("hui");
list.set(0,"灰");
复制代码

源码解析

这里大多调用的是和get()里一样的方法

 

remove方法

remove(int index)

按索引删除，先找到被删除的Node，然后解除相关链接，设置Node里三大元素为null，删除后返回被删除Node里的item

代码实现

List<String> list=new LinkedList<>();
list.add("hui");
list.add("灰");
list.remove(1);
复制代码

源码解析

 

  • unlink(Node<E> x)解除Node的连接，然后返回被解除链接的item

 

流程图

  • 删除的是链表里的第一个元素

删除的是链表里的第一个元素

  • 删除的是链表里的中间元素

 

  • 删除的是链表里的最后一个元素

 

remove(Object o)

这个删除就比较慢了，它内部没有用二分查找算法，而是从头开始一一对比，时间复杂度为O(n)，这个删除也是只删除最早添加的数据

代码实现

List<String> list=new LinkedList<>();
list.add("hui");
list.remove("hui");
复制代码

源码解析

unlink()方法就是上面讲的那个

 

clear方法

clear()

代码实现

List<String> list=new LinkedList<>();
list.add("hui");
list.clear();
复制代码

源码解析

 

总结

LinkedList里删除，添加操作一般就两个步骤，变换前后Node指向的地址，删除操作把对应Node里的三个变量都设置为null，方便GC回收。

如果要删除元素时，最好选择传入索引删除，他比直接传入要删除的对象的方法要快很多