集合类之LinkedList

特点

• 数据按照插入有序
• 可以存储null值
• 可以重复存储数据
• 底层数据结构为链表

继承关系

从源码上来看：

LinkedList继承了AbstractSequentialList这个类，实现了List、Deque的接口，具有队列的特征

底层数据结构

是一个双向链表

构造函数

有参构造和无参构造

默认值

由于LinkedList是一个双向链表，没有初始化大小，也没有扩容机制，就是一直在前面或者后面新增就行

增长方式

无限后续

CRUD（增删改查）方法研究

添加：
LinkedList提供头插，尾插方式插入节点、默认采用的是尾插

头插法：

尾插法：

删除：
先判断元素是否为null，然后进行不同的判等处理
删除元素从前往后删除，重复性元素直接删除第一个节点

前驱prev分两种情况：一种是first节点，一种非first节点
后驱next也分为两种情况：一种为null，一种为非null

查找：
查找时采用了二分法（效率高），先将链表的长度除二，然后将结果与所要查找的下标进行比较，如果大于，就从后往前找；如果小于，就从前往后找，节约时间，提高了效率