链表
- 前言
- 一、链表的概念及结构
- 二、链表的分类
- 三、链表的实现
- 无头单向非循环链表实现
- 无头双向链表实现
- 具体代码
- 四、链表习题
- 五、顺序表和链表的区别
前言
推荐一个网站给想要了解或者学习人工智能知识的读者，这个网站里内容讲解通俗易懂且风趣幽默，对我帮助很大。我想与大家分享这个宝藏网站，请点击下方链接查看。
https://www.captainbed.cn/f1
链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是，它不需要在内存中连续存储，因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择，尤其是在需要动态调整数据结构大小的场景中。
在链表的实现中，通常会有头节点和尾节点之分。头节点是链表的第一个节点，而尾节点是链表的最后一个节点。通过遍历链表，我们可以访问链表中存储的所有数据。链表还支持在链表头部或尾部快速添加新节点，这些操作的时间复杂度通常为O(1)。
然而，链表也有一些缺点。比如，访问链表中的某个特定节点需要从头节点开始遍历，这导致访问链表中间节点的平均时间复杂度为O(n)。此外，链表需要额外的空间来存储指针，这增加了内存的使用。
链表有多种类型，如单向链表、双向链表和循环链表等。单向链表是最简单的链表类型，每个节点只有一个指向下一个节点的指针。双向链表则允许节点同时指向前一个和下一个节点，这使得双向链表在某些操作上比单向链表更高效。循环链表则是将尾节点的指针指向头节点，形成一个闭环。
在实际应用中，链表常用于实现栈、队列和哈希表等数据结构。例如，链表可以作为栈的底层数据结构，实现元素的先进后出。此外，链表还可以用于实现动态数组，支持元素的动态插入和删除。
总之，链表作为一种重要的数据结构，在编程和数据处理中发挥着重要作用。尽管链表在某些方面存在不足，但其灵活性和高效性使得它在许多场景中仍然是理想的选择。通过深入了解链表的特性和应用，我们可以更好地利用这种数据结构来解决实际问题。
一、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
现实中 数据结构中
二、链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
三、链表的实现
无头单向非循环链表实现
// 1、无头单向非循环链表实现
public class SingleLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void display();
public void clear();
}
无头双向链表实现
// 2、无头双向链表实现
public class DoubleLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void display();
public void clear();
}
具体代码
// 2、使用无头单向非循环链表实现
public class SingleLinkedList {
private Node head; // 头节点
// 节点类
private class Node {
private int data; // 数据
private Node next; // 下一个节点
public Node(int data) {
this.data = data;
}
}
// 头插法
public void addFirst(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
newNode.next = head;
head = newNode;
}
}
// 尾插法
public void addLast(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
}
// 任意位置插入
public boolean addIndex(int index, int data) {
if (index < 0 || index > size()) {
return false;
}
if (index == 0) {
addFirst(data);
return true;
}
if (index == size()) {
addLast(data);
return true;
}
Node newNode = new Node(data);
Node cur = findNode(index - 1);
newNode.next = cur.next;
cur.next = newNode;
return true;
}
// 查找是否包含关键字
public boolean contains(int key) {
Node cur = head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
// 删除第一个出现的关键字节点
public void remove(int key) {
if (head == null) {
return;
}
if (head.data == key) {
head = head.next;
return;
}
Node cur = head;
while (cur.next != null && cur.next.data != key) {
cur = cur.next;
}
if (cur.next != null) {
cur.next = cur.next.next;
}
}
// 删除所有值为关键字的节点
public void removeAllKey(int key) {
if (head == null) {
return;
}
// 处理头节点的情况
while (head != null && head.data == key) {
head = head.next;
}
// 处理其他节点的情况
Node cur = head;
while (cur != null && cur.next != null) {
if (cur.next.data == key) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
}
// 获取链表长度
public int size() {
int count = 0;
Node cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
// 查找指定位置的节点
private Node findNode(int index) {
Node cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
}
// 打印链表
public void display() {
Node cur = head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
// 清空链表
public void clear() {
head = null;
}
}
四、链表习题
- 删除链表中等于给定值 val 的所有结点
- 反转一个单链表
- 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
- 输入一个链表，输出该链表中倒数第k个结点
- 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的
- 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
- 链表的回文结构
- 输入两个链表，找出它们的第一个公共结点
- 给定一个链表，判断链表中是否有环
【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
【扩展问题】
-
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。 -
快指针一次走3步，走4步，…n步行吗？
- 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL
解决像这样的题目，我们可以找等式，通过等式来找出相应的关系
- 结论
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。 - 证明
- 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。
要求返回这个链表的深度拷贝 - 其他 。ps：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，大家可以先把
c++学一下，在逐步开始刷题 Leetcode + 牛客
五、顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
备注：缓存利用率参考存储体系结构 以及 局部原理性。
与程序员相关的CPU缓存知识
