文章目录
- 前言
- 一、LinkedList
- 二、ArrayList与LinkedList异同
-
- 2.1 数据结构
- 2.2 增删改查
- 2.3 使用场景
- 总结
前言
LinkedList(Queue与List的实现类)底层数据结构是Node节点(data数据+next下一个节点的引用)本质是双向链表。
一、LinkedList
双向链表构成的集合，可用迭代器遍历
a.底层数据结构:
链式结构
b.底层实现:
Node节点(data[数据] + next[下一个节点的引用])
c.特点:
LinkedList是双向链表
①.链表是内存中固定顺序,但是他的物理空间不连续（随机存放）
②.没有下标
③.所有节点的访问,都必须通过头节点(next)/尾节点(pre)
④.head(头节点): 只存next,不存data
last(尾节点): 只存pre,不存data
⑤.head.next = null -> 空链表
last.pre = null -> 空链表
d.优缺点:
优点:
a.插入/删除效率高
b.不需要连续的内存物理空间,所以空间利用率高
缺点:
查询效率低,只能从头节点出发开始查询
e.LinkedList独有的API:
(只要带有First/last的方法)
void addFirst(E e)
void addLast(E e)
E getFirst()
E getLast()
E remove(int index)
E removeFirst()
E removeLast()
构造方法：
常用方法:
二、ArrayList与LinkedList异同
2.1 数据结构
ArrayList是基于数组实现的，LinkedList是基于双链表实现的。另外LinkedList类不仅是List接口的实现类，可以根据索引来随机访问集合中的元素，除此之外，LinkedList还实现Deque 接口，Deque接口是Queue接口的子接口，它代表一个双向队列，因此LinkedList可以作为双向队列 ，栈（可以参见Deque提供的接口方法）和List集合使用，功能强大。ArrayList长度固定，每次以1.5倍进行扩容（然后Arrays.copyOf()去浅克隆），LinkedList链表长度可变。
2.2 增删改查
ArrayList -> 增删慢,查询快
LinkedList -> 增删快,查询慢
2.3 使用场景
使用场景：
(1）如果应用程序对数据有较多的随机访问，ArrayList对象要优于LinkedList对象；
(2) 如果应用程序有更多的插入或者删除操作，较少的随机访问，LinkedList对象要优于ArrayList对象；
(3）不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。
总结：在使用List集合时,会选择ArrayList,在综所有条件之后,ArrayList插入和查询的效率高于LinkedList.
总结
提示：LinkedList与ArrayList相同部分也就继承Collection拥有Collection的特点。