数据结构-链表

在数据结构中，链表是一种常见的线性数据结构，它通过节点之间的指针（或引用）来连接数据元素，形成一个链式结构。与数组不同，链表中的元素在内存中不必连续存储，这使得它在插入、删除操作上具有独特的优势。

一、链表的基本组成

链表的核心组成单元是节点（Node），每个节点通常包含两部分：

• 数据域（Data）：存储具体的数据信息（如整数、字符串、对象等）。

• 指针域（Pointer/Reference）：存储下一个节点的地址（或引用），用于连接各个节点。

整个链表由头节点（Head） 开始，头节点是链表的第一个节点（有时会设置 “哑节点” 作为头节点，简化边界处理），最后一个节点的指针域为null（表示链表结束）。

二、链表的常见类型

根据节点指针域的数量和连接方式，链表可分为以下几种常见类型：

1. 单链表（Singly Linked List）

• 每个节点只有一个指针域，指向下一个节点。

• 特点：只能从前往后遍历，无法反向访问。

• 示意图：
  Head -> 节点1 -> 节点2 -> ... -> 尾节点 -> null

2. 双向链表（Doubly Linked List）

• 每个节点有两个指针域：一个指向下一个节点，另一个指向上一个节点。

• 特点：可以双向遍历，支持从任意节点向前或向后访问，但节点结构更复杂（占用更多内存）。

• 示意图：
  Head <-> 节点1 <-> 节点2 <-> ... <-> 尾节点 <-> null

3. 循环链表（Circular Linked List）

• 尾节点的指针域不指向null，而是指向头节点（或某个特定节点），形成一个闭环。

• 特点：可以循环遍历，适合需要反复处理数据的场景（如约瑟夫问题）。

• 分类：单循环链表（基于单链表）、双向循环链表（基于双向链表）。

三、链表的基本操作

以单链表为例，常见操作包括：

1. 初始化

创建一个空链表，通常将头节点设为null。

2. 插入

• 头部插入：新节点的指针指向原头节点，再将头节点更新为新节点（时间复杂度O(1)）。

• 中间 / 尾部插入：先遍历找到插入位置的前一个节点，再修改指针连接新节点（时间复杂度O(n)，n为链表长度）。

3. 删除

• 头部删除：直接将头节点更新为头节点的下一个节点（O(1)）。

• 中间 / 尾部删除：遍历找到待删除节点的前一个节点，修改指针跳过待删除节点（O(n)）。

4. 遍历

从头部开始，依次访问每个节点的数据，直到指针为null（O(n)）。

5. 查找

遍历链表，对比节点数据与目标值，返回找到的节点（O(n)）。

四、链表与数组的对比

 链表初始化流程（LinkList list = new LinkList()）

1. 在堆内存中创建LinkList对象，head成员变量初始化为null（无任何节点）

2. 在栈内存中创建list引用，指向堆中的LinkList对象

3. 此时内存状态：只有一个空链表对象，head = null

 尾插法插入流程（以list.insert(5)为例）

                                LinkList list=new LinkList();
                                        list.insert(5);
                                        list.insert(2);
                                        list.insert(9);
                                        list.insert(1);
                                        list.insert(4);

1. 调用insert(5)方法，在堆中创建Node对象（value=5，next=null）

2. 判断head是否为null（此时为空），执行head = node

3. 内存变化：head引用指向新创建的节点，链表长度变为 1

4. 后续插入（如insert(2)）：

   • 创建新节点（value=2）

   • 从head开始遍历，找到最后一个节点（值为 5 的节点）

   • 将最后一个节点的next指向新节点

   • 内存中形成链式结构：5 -> 2

toString () 方法执行流程

1. 初始化字符串res = "["，创建index引用指向head

2. 遍历过程：

   • 第一次循环：index指向 5，res变为"[5,"，index移动到 2

   • 第二次循环：res变为"[5,2,"，index移动到 9

   • 直到最后一个节点（4），拼接为"[5,2,9,1,4]"

3. 返回拼接后的字符串并打印

指定位置插入流程（list.insertAtPostoin(16, 3)）

1. 检查位置合法性：3 在 0~5 范围内（合法）

2. 创建新节点（value=16）

3. 初始化index=head，pre=null，count=0

4. 遍历寻找插入位置：

   • count=0：pre指向 5，index指向 2

   • count=1：pre指向 2，index指向 9

   • count=2：pre指向 9，index指向 1

   • count=3：找到目标位置

 length () 方法执行流程

1. 初始化计数器count=0，index指向head

2. 遍历链表：

   • 第一次循环：index指向 5，count=1，index移动到 2

   • 第二次循环：count=2，index移动到 9

   • 直到index为null，循环结束

3. 返回count=5（初始 5 个元素）

调用 list.search(9) 时：

1. 初始化索引：创建 index 引用，指向链表的头节点（此时头节点的值为 5）。

2. 遍历链表：

   • 第一次循环：index 指向值为 5 的节点，5 != 9，index 移动到下一个节点（值为 2 的节点）。

   • 第二次循环：index 指向值为 2 的节点，2 != 9，index 移动到下一个节点（值为 9 的节点）。

3. 找到目标节点：

   • 此时 index.value == 9，满足条件，返回当前 index 所指向的节点（值为 9 的节点）。

4. 内存状态：整个过程中链表的节点引用关系未发生变化，仅通过 index 引用在内存中遍历节点，最终返回指向值为 9 的节点的引用。