ToB企服应用市场:ToB评测及商务社交产业平台

标题: 一起探秘，不可不知双向链表底层原理 [打印本页]

---

作者: 写过一篇    时间: 2022-9-16 17:12
标题: 一起探秘，不可不知双向链表底层原理
双向链表与数据结构

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

复制代码

什么是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

1. package com.llist;
3. import java.util.ArrayList;
4. import java.util.Collection;
5. import java.util.LinkedList;
7. public class LList {
9.     public static void main(String[] args) {
10.         LinkedList<String> linkedList = new LinkedList<String>();
11.         linkedList.add("100");//尾插,等价于 linkedList.addLast()
12.         linkedList.add("200");
13.         linkedList.add("300");
14.        //*******中间插入linkedList..add(3,"700")*************
15.         linkedList.add("400");
16.         linkedList.add("500");
17.         linkedList.add("600");
18.         System.out.println(linkedList);
19.         linkedList.add(3,"700");//中间插入
20.         System.out.println(linkedList);
21.         //*******修改***************************************
22.         linkedList.set(3,"700000000");
23.         System.out.println(linkedList);
24.         //*******查询***************************************
25.         System.out.println(linkedList.getFirst());//头查
26.         System.out.println(linkedList.getLast());//尾查
27. //        for(int s=0;s<linkedList.size();s++){
28. //            System.out.println(linkedList.get(s));//随机插
29. //        }
31.         //*******移除***************************************
32.         LinkedList<String> linkedListRemove = new LinkedList<String>();
33.         linkedListRemove.add("100");
34.         linkedListRemove.add("200");
35.         linkedListRemove.add("300");
36.         linkedListRemove.remove(1);//指定移除
37.         linkedListRemove.removeAll(linkedList);//也调用上面的unlink方法；LinkedList.ListItr.remove
38.     }
40. }

复制代码

1.     transient int size = 0;//元素个数
2.     transient Node<E> first;//头结点引用（查询时获取）
3.     transient Node<E> last;//尾节点引用（查询时获取）
7.     private static class Node<E> { //链表节点元素，封装了真实数据，同时加入了前后指针
8.         E item;//元素，这是放入的真实数据
9.         Node<E> next;//下一个节点，指针也是Node类型
10.         Node<E> prev;//上一个节点
11.       
12.                                 //构造器，前、值、后，很清晰
13.         Node(Node<E> prev, E element, Node<E> next) {
14.             this.item = element;//新元素
15.             this.next = next;//下个节点
16.             this.prev = prev;//上个节点
17.         }
18.     }

复制代码

本文由传智教育博学谷 - 狂野架构师教研团队发布
如果本文对您有帮助，欢迎关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力
转载请注明出处！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4