一起探秘，不可不知双向链表底层原理_linklist是单向链表还是双向

作者：小舞很执着 | 2024-07-18 05:24:52

踩

linklist是单向链表还是双向

双向链表与数据结构

	`引言`
	`在上小节中`
	`我们分析了ArrayList的底层实现，`
	`知道了ArrayList底层是基于数组实现的，因此具有查找修改快而插入、删除慢的特点`
	`本章我们介绍的LinkedList是List接口的另一种实现`
	`它的底层是基于双向链表实现的`
	`因此它具有插入、删除快而查找修改慢的特点`

什么是LinkedList

LinkList是一个双向链表（双链表）；它是链表的一种，也是最常见的数据结构，其内部数据呈线性排列，属于线性表结构.

它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，所以是双向链表.

LinkList特点：

链表: 优势：不是连续的内存，随便插入（前、中间、尾部）插入O(1) 劣势：查询慢O(N)

线程不安全的，允许为null，允许重复元素

蓝色表示；可随意插入、删除

查询循环循环链表

总结

双链表的节点既有指向下一个节节点的指针，也有指向上一个结点的指针（双向读）

所谓指针，就是指向其他节点的一个对象的引用（说白了就是定义了两个成员变量）

双向链表线程不安全的，允许为null，允许重复元素

查询O(n)

插入删除O(1)

1.2 双向链表继承关系

LinkedList 是一个继承于AbstractSequentialList的双向链表。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，能将LinkedList当作双端队列（double ended queue）使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。

1.3 双向链表源码深度剖析

案例代码

com.llist.LList

	`package com.llist;`

	`import java.util.ArrayList;`
	`import java.util.Collection;`
	`import java.util.LinkedList;`

	`public class LList {`

	`public static void main(String[] args) {`
	`LinkedList<String> linkedList = new LinkedList<String>();`
	`linkedList.add("100");//尾插,等价于 linkedList.addLast()`
	`linkedList.add("200");`
	`linkedList.add("300");`
	`//*****中间插入linkedList..add(3,"700")***********`
	`linkedList.add("400");`
	`linkedList.add("500");`
	`linkedList.add("600");`
	`System.out.println(linkedList);`
	`linkedList.add(3,"700");//中间插入`
	`System.out.println(linkedList);`
	`//*****修改*************************************`
	`linkedList.set(3,"700000000");`
	`System.out.println(linkedList);`
	`//*****查询*************************************`
	`System.out.println(linkedList.getFirst());//头查`
	`System.out.println(linkedList.getLast());//尾查`

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/843762