【最完整系列】JAVA-容器篇-LinkedList源码解析
2020/2/23 17:02:51
本文主要是介绍【最完整系列】JAVA-容器篇-LinkedList源码解析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
简介
LinkedList 顾名思义其本质是一个链表,具体来说是一个双向链表,同时还有2个指针分别对应链表的头和尾。
![](/upload/202002/23/202002231702519160.png)
源码
源码还是跟 ArrayList 一样,从我们常用的代码出发:
List<String> a = new LinkedList<>(); a.add("sidfate"); 复制代码
进入初始化源码:
// LinkedList 长度 transient int size = 0; // 指向头结点 transient Node<E> first; // 指向尾节点 transient Node<E> last; public LinkedList() { } 复制代码
可以看到默认的构造函数空空如也,需要注意的是链表是以 Node 为基础连接起来的,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; } } 复制代码
Node 结构也很简单,prev 和 next 说明它是一个双向的链表,保存前后 Node 的指针。接下来进入 add 的过程:
public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } 复制代码
简单来说,添加一个元素就是往链表尾插入一个新的 Node。那么如果是往链表中插入一个元素呢:
public void add(int index, E element) { // 检查index合法性 checkPositionIndex(index); if (index == size) // 如果index就是尾部则直接添加 linkLast(element); else // 在 index 所在的 Node 前插入 linkBefore(element, node(index)); } Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 复制代码
node 函数用来查找对应 index 的 Node 节点,比较有意思的是 2 将遍历降低成了链表长度的一半:
- 如果 index 在头和中点之间,那么就从头开始遍历到中点。
- 如果 index 在中点和尾之间,那么就从尾开始遍历到中点。
双向链表的优势就凸显出来的,相对而言插入的效率比 ArrayList 高,毕竟 ArrayList 需要拷贝 index 后的数组。但是查询效率就低了,ArrayList 根据下标能直接取出元素,而且因为是数组所以内存空间上是连续的,不像 LinkedList是根据指针串联,内存地址上可能是不连续的。
LinkedList 的还有个优势时它既能当队列也能当栈来使用。
这篇关于【最完整系列】JAVA-容器篇-LinkedList源码解析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现