LinkedList
是一个双向链表实现的list,允许null值 线程非安全 还可以作为队列或栈来使用
其继承关系如下:
可看出LinkedList
不仅实现了list接口 还是先了Queue或Deque接口
主要属性
1 | public class LinkedList<E> |
构造器
1 | public LinkedList() { |
添加元素
作为队列
1 | public void addFirst(E e) { |
作为list
1 | public void add(int index, E element) { |
删除元素
1 | public E remove() { |
栈
1 | public void push(E e) { |
总结
- 双向链表实现的list
- 实现了Queue、Deque接口 具有队列和双端队列、栈的特性
- 队列首尾添加、删除元素非常高效 时间复杂度为O(1)
- 在中间添加、删除元素 需要遍历list 比较低效 时间复杂度为O(n)
- 不支持随机访问 故访问非首尾节点比较低效
- 功能上等于ArrayList+ArrayDeque