一.LinkedList数据结构
1.1 数据结构
LinkedList 底层数据结构是一个双向链表,整体构造如下图所示:
注意事项:
- 链表每个节点叫做 Node,Node 有 prev 属性,代表前一个节点的地位,next 属性,代表后一个节点的位 置
- first 是双向链表的头节点,它的前一个节点是 null。
- last 是双向链表的尾节点,它的后一个节点是 null;
- 当链表中没有数据时,first 和 last 是同一个节点,前后指向都是 null;
- 因为是个双向链表,是没有大小限度的。
1.2 Node
private static class Node<E> {
E item; // 节点值
Node<E> next; // 指向的下一个节点
Node<E> prev; // 指向的前一个节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
二.源码剖析
2.1 LinkedList类正文解析
- 应用“双向链表”来实现List与Deque接口。 实现了所有List接口中的办法,并且容许寄存所有元素,包含Null。
- 所有的操作都可通过双向链表实现。通过从结尾或者结尾遍历汇合,去靠近要操作的那个元素。
- 是非线程平安的,多线程状况下,举荐应用线程安全类:Collections#synchronizedList
- 加强 for 循环,或者应用迭代器迭代过程中,如果数组大小被扭转,会疾速失败,抛出异样。
2.2 新增
源码解析:
新增节点时,咱们能够抉择追加到链表头部,还是追加到链表尾部,add 办法默认是从尾部开始追加,addFirst 方
法是从头部开始追加:
增加:
/**
* 将元素增加到链表尾部,等于addFirst
*/
public boolean add(E e) {
linkLast(e);
return true;
}
从尾部减少:
/**
* 从尾部开始追加节点
*/
void linkLast(E e) {
// 把尾节点数据暂存
final Node<E> l = last;
// 新建新的节点,初始化入参含意:
// l 是新节点的前一个节点,以后值是尾节点值
// e 示意以后新增节点,以后新增节点后一个节点是 null
final Node<E> newNode = new Node<>(l, e, null);
// 将新建节点追加到尾部
last = newNode;
//如果链表为空 l 是尾节点,尾节点为空,链表即空,头部和尾部是同一个节点,都是新建的节点
if (l == null)
first = newNode;
else
//否则把前尾节点的下一个节点,指向以后尾节点。
l.next = newNode;
//大小和版本更改
size++;
modCount++;
}
从头部减少:
/**
*从头部开始追加节点
*/
private void linkFirst(E e) {
// 把头节点数据暂存
final Node<E> f = first;
// 新建新的节点,初始化入参含意:
// l 是新节点的前一个节点,以后值是尾节点值
// f 示意以后新增节点,以后新增节点后一个节点是 null
final Node<E> newNode = new Node<>(null, e, f);
// 将新建节点追加到头部
first = newNode;
//如果链表为空 f 是头节点,头节点为空,链表即空,头部和尾部是同一个节点,都是新建的节点
if (f == null)
last = newNode;
else
//上一个头节点的前一个节点指向以后节点
f.prev = newNode;
size++;
modCount++;
}
注意事项:
- 头部追加节点和尾部追加节点,只是前者是挪动头节点的 prev 指向,后者是挪动尾节点的 next 指向,两者区别不大。
2.3 删除实现
源码解析:
LinkedList节点删除的形式和追加相似,咱们能够抉择从头部删除,也能够抉择从尾部删除,删除操作会把节点的值,前后指
向节点都置为 null。
从头部删除:
/**
* 从头部开始删除节点
*/
private E unlinkFirst(Node<E> f) {
//拿出头节点的值,作为办法的返回值
final E element = f.item;
// 拿出头节点的下一个节点
final Node<E> next = f.next;
//帮忙 GC 回收头节点
f.item = null;
f.next = null;
//头节点的下一个节点成为头节点
first = next;
//如果 next 为空,表明链表为空
if (next == null)
last = null;
else
//链表不为空,头节点的前一个节点指向 null
next.prev = null;
//批改链表大小和版本
size--;
modCount++;
return element;
}
从尾部删除:
/**
* 和从头部删除基本一致
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
注意事项:
- 前后指向节点都置为 null,是为了帮忙 GC 进行回收;
- 从源码中咱们能够理解到,链表构造的节点新增、删除仅仅把前后节点的指向批改了, 所以LinkedList新增和删除度很快。
2.4 实现查问
查问:
/**
* 依据链表索引地位查问节点
*/
Node<E> node(int index) {
// 如果 index 处于队列的前半部分,从头开始找,size >> 1 是 size 除以 2 的意思。
if (index < (size >> 1)) {
Node<E> x = first;
// 直到 for 循环到 index 的前一个 node 进行
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果 index 处于队列的后半局部,从尾开始找
Node<E> x = last;
// 直到 for 循环到 index 的后一个 node 进行
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
注意事项:
LinkedList 并没有采纳从头循环到尾的做法,而是采取了二分法,首先看 index 是在链表的前半部分,还是后半局部。如果是前半部分,就从头开始寻找,反之亦然。通过这种形式,使循环的次数 至多升高了一半,进步了查找的性能。
三.工夫复杂度
get() 获取第几个元素,顺次遍历,复杂度O(n)
add(E) 增加到开端,复杂度O(1)
add(index, E) 增加第几个元素后,须要先查找到第几个元素,间接指针指向操作,复杂度O(n) (这个比拟容易想错)
remove()删除元素,间接指针指向操作,复杂度O(1)
四.线程平安
4.1 线程平安问题
只有当 LinkedList作为共享变量时,才会有线程平安问题,当 LinkedList是办法内的局部变量时,是没有线程平安的问题的。
LinkedList有线程平安问题的起因,是因为 LinkedList本身的 size、modConut 在进行各种操作时,都没有加锁,而且这些变量的类型并非是可见(volatile)的,所以如果多个线程对这些变量进行操作时,可能会有值被笼罩的状况。
类正文中举荐应用 Collections#synchronizedList 来保障线程平安,SynchronizedList 是通过在每个办法下面加上锁来实现,尽管实现了线程平安,然而性能大大降低,具体实现源码:
public boolean add(E e) {
synchronized (mutex) {return c.add(e);}
}
咱们也能够应用ConcurrentLinkedQueue来保障线程平安,
五.总结
LinkedList的底层是链表构造 ,实用于适宜于常常新增和删除的场景,
欢送关注公众号:前程有光,支付一线大厂Java面试题总结+各知识点学习思维导+一份300页pdf文档的Java外围知识点总结! 这些材料的内容都是面试时面试官必问的知识点,篇章包含了很多知识点,其中包含了有基础知识、Java汇合、JVM、多线程并发、spring原理、微服务、Netty 与RPC 、Kafka、日记、设计模式、Java算法、数据库、Zookeeper、分布式缓存、数据结构等等。
发表回复