1. LinkedList是一种由双向链表实现的List
2. LinkedList是线程不安全的
3. LinkedList允许元素为null,且允许包含重复元素
4. 由于LinkedList是基于链表实现的,因此插入和删除元素的效率很高,但查找元素的效率较低(尽管有一些加速的方法)
5. 由于LinkedList是基于链表实现的,所以不会存在容量不足的问题,因此没有扩容的方法
6. LinkedList还实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用
2.1 LinkedList的存储结构
LinkedList是由双链表的数据结构组成的
public class LinkedList{// 元素个数transient int size = 0;/指向第一个节点的指针不变性:1. 如果first = null,则last=null2. 如果first.prev == null,则first.item != null/
2.2 添加元素
2.2.1 从头部添加
2.2.2 从尾部添加
2.3 删除节点
2.3.1 从头部删除
2.3.2 从尾部移除
2.3.3 根据索引移除
2.4.1 获取头部数据
2.4.2 获取尾部数据
2.4.3 根据索引获取节点数据
三、总结:LinkedList和ArrayList的比较
1. 顺序插入速度ArrayList会比较快,因为ArrayList是基于数组实现的,数组是事先new好的,只要往指定位置 塞一个数据就好了
2. LinkedList则不同,每次顺序插入的时候LinkedList将new一个对象出来,如果对象比较大,那么new的时间 势必会长一点,再加上一些引用赋值的操作,所以顺序插入LinkedList必然慢于ArrayList
3. ArrayList的遍历效率会比LinkedList的遍历效率高一些
4. LinkedList做插入、删除的时候,慢在寻址,快在只需要改变前后Node的引用地址
5. ArrayList做插入、删除的时候,慢在数组元素的批量copy,快在寻址