LinkedList(List接口的实现类)

发表于 更新于 分类于 ， 阅读次数： Valine：

LinkedList说明

LinkedList底层实现了一个双向链表，下面图中由first与last元素，分别标识双向链表的头和尾。而他们维护的双向链表中节点又拥有prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点，最终实现双向链表。

所以LinkedLIst的元素的添加和删除不是通过数组，相对效率比较高，添加删除元素只需要控制节点的指向就ok。但是LInkedList是线程不安全的。

LinkedList的底层结构

1
2
3
4
5
6
7
8
9
10
import java.util.*;

public class Test {
    public static void main(String [] args){
        LinkedList linkedList=new LinkedList();
        linkedList.add(1);

    }
}

我们在debug情况下执行上述代码，发现进行add的时候，第一步，对传入的1进行装箱

紧接着进入到一个boolean的add方法，执行linklast方法，将这个数加入到这个双向链表的最后

image-20220308145644770

在linkLast方法中，在双向链表中加new一个新的节点，如果这个为null则把数存放在这里，就使next指向下一个节点中。由于此时链表中一个数也没有存放，所以first与last都指向节点1

image-20220308145900611

可以发现，first与next的指向的地址都相同

image-20220308150942411

此时如果我们再一次add一个数，并且用debug运行，再一次运行到linkLast时，新建立一个节点，last指向新节点，而此时l不为空，则l的next指向newNode

image-20220308151137821

练习

前面的操作与添加操作，而删除操作的流程

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;

public class Test {
    public static void main(String [] args){
        LinkedList linkedList=new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.remove(1);


    }
}

我们在debug条件下运行删除操作，第一步进入到remove的源码

image-20220308152529515

而第一行的函数作用时判断想要删除的元素是否超过了范围，超出范围就抛出异常image-20220308152624085

而第二行的unlink函数则是真正进行双向链表操作的函数，简单一点说就是判断删除的位置在哪里，判断前面和后面是否还有节点，last，next，prev指向哪里？？？当然remove还有其他多种的删除方式，每一种方式不同

image-20220308152807338

image-20220308152905813

ArrayList与LinkList的比较

底层结构 增删的效率 改查的效率
ArrayList 可变的数组 较低，通过数组进行扩容 较高
LinkedList 双向的链表 较高，通过链表进行追加 较低，因为更改需要改变前后的节点的指向

在一个项目中，大部分都是查询，因此大部分会选择ArrayList。同时两个类都是线程不安全的