LinkedList与链表(有源码剖析)（一）

 💕"你笑的次数越多越好，因为你只有用笑才能不怀恶意地消灭罪恶。"💕

作者：Mylvzi

文章主要内容：数据结构之单链表的模拟实现

一.前言:

在上个顺序表的博客结尾针对ArrayList的缺陷留了一个思考题

大家可以去再看一下顺序表这篇博客https://blog.csdn.net/Mylvzi/article/details/133896470?spm=1001.2014.3001.5501

 因为ArrayList的底层是一段连续内存的空间，进行插入/删除操作的开销很大，因此ArrayList不适合用于"需要大量添加/删除数据的场景"，因此Java中又引入了LinkedList，即链表结构

二.链表

1.链表的概念及结构

 链表是物理地址不连续的线性表，逻辑顺序是通过"链条"连接起来的

可以将链表想象成拉着很多节车厢的火车

注意:

1.链表是由一个个结点(Node)组成的，每个结点都是从堆上申请的

2.堆为每个结点分配内存地址，分配时是随机的，所以链表的物理结构是不连续的

链表的分类:

按照不同的性质可以有多种分类方法:

• 按照是否有"头节点":带头和不带头
• 按照是否循环：循环和不循环
• 按照链表逻辑的方向：单向和双向

综上，链表可分为2 * 2 * 2 = 8种，在这里我们只需重点掌握两种链表即可

• 无头单项非循环链表  面试常考
• 无头双向非循环链表  Java中LinkedList的底层就是一个无头双向非循环链表

注意：这里说的"有无头节点"中的头节点不属于链表中的有效数据，他更像是一个“傀儡节点”，仅仅作为前驱使用

三.无头单向非循环链表的实现

1.链表的结构

 // 定义结点
 static class ListNode {
int val;// 结点存储的数据
        ListNode next;// 保存下一个结点的地址
 public ListNode(int val) {
 this.val = val;
         }
     }
 // 定义头节点
 public ListNode head = null;

2.链表的插入

因为链表的物理地址并不是连续的，所以我们插入数据的位置是多样性的，总的来说可以分为三种

• 头插法：addFirst
• 尾插法：addLast
• 任意位置插入：addIndex

1.头插法

 头插法及创建一个新的结点，将此结点插入到第一个结点之前

 public void addFirst(int data) {
 ListNode newNode = new ListNode(data);
 // 头插法不需要考虑链表是否为空
         newNode.next = head;
         head = newNode;
     }

注意：

在链表中插入/删除数据时，最重要的一点是记得保存"下一节点"，往往是先连接后面的结点，在进行其他的操作(如果不先连接后面的结点就会损失后面的所有节点火车一节车厢断开，则后面的车厢都断开了)

2.尾插法

尾插法即在链表的末尾添加一个新的结点

 public void addLast(int data) {
 ListNode newNode = new ListNode(data);
 // 如果为空  链表中没有一个节点 直接插入
 if(head == null) {
             head = newNode;
 return;
         }
 ListNode cur = head;
 // 让cur走到链表的最后一个节点
 while (cur.next != null) {
            cur = cur.next;
        }
         cur.next = newNode;
     }

LinkedList与链表(有源码剖析)（二）+https://developer.aliyun.com/article/1413522