集合类之LinkedList
特点
- 数据按照插入有序
- 可以存储null值
- 可以重复存储数据
- 底层数据结构为链表
继承关系
从源码上来看:
LinkedList继承了AbstractSequentialList这个类,实现了List、Deque的接口,具有队列的特征
底层数据结构
是一个双向链表
构造函数
有参构造和无参构造
默认值
由于LinkedList是一个双向链表,没有初始化大小,也没有扩容机制,就是一直在前面或者后面新增就行
增长方式
无限后续
CRUD(增删改查)方法研究
添加:
LinkedList提供头插,尾插方式插入节点、默认采用的是尾插
头插法:
尾插法:
删除:
先判断元素是否为null,然后进行不同的判等处理
删除元素从前往后删除,重复性元素直接删除第一个节点
前驱prev分两种情况:一种是first节点,一种非first节点
后驱next也分为两种情况:一种为null,一种为非null
查找:
查找时采用了二分法(效率高),先将链表的长度除二,然后将结果与所要查找的下标进行比较,如果大于,就从后往前找;如果小于,就从前往后找,节约时间,提高了效率