简说 LinkedList 底层代码实现

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2800+ 小伙伴加入学习 ，欢迎点击围观

如图所示 LinkedList 底层是基于双向链表实现的，也是实现了 List 接口，所以也拥有 List 的一些特点 (JDK1.7/8 之后取消了循环，修改为双向链表)。

新增方法

	public boolean add(E e) {
		linkLast(e);
		return true;
	}
	 /**
	 * Links e as last element.
	 */
	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++;
	}

可见每次插入都是移动指针，对比 ArrayList 的拷贝数组来说效率要高上不少。

查询方法

上述代码，利用了双向链表的特性，如果 index 离链表头比较近，就从节点头部遍历。否则就从节点尾部开始遍历。使用空间（双向链表）来换取时间。

node() 会以 O(n/2) 的性能去获取一个结点, 如果索引值大于链表大小的一半，那么将从尾结点开始遍历.

这样的效率是非常低的，特别是当 index 越接近 size 的中间值时。

总结

• LinkedList 插入，删除都是移动指针效率很高。

• 查找需要进行遍历查询，效率较低。