前言
单向链表示最基础的数据结构之一，它也是我们学习开始学习数据结构的第一个必须要掌握的数据结构，学习数据结构一定是由浅到深，所以我们最好是先学习简单的在学习有难度的，因为直接学习难的数据结构很容易劝退，让我们来深入了解单向链表。
目录
- 前言
- 一、什么是单向链表
- 二、链表结构
- 三、基本操作
- 四、性能分析
- 五、优点和缺点
- 六、删除、插入元素动态图解
- 七、代码模版
- 八、经典例题
- 1.数列有序!
- 2.二进制链表转整数
- [3.面试题 02.02. 返回倒数第 k 个节点](https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/)
- [4.LCR 140. 训练计划 II](https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/)
- 九、总结
- 十、结语
一、什么是单向链表
单向链表（Singly Linked List）是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。
二、链表结构
1. 节点结构
每个节点通常包含两个部分：
数据域：存储节点的值或数据。
指针域（或称为链接域）：存储指向下一个节点的指针。如果节点是链表的最后一个节点，则指针通常为空（NULL 或 nullptr）。
2. 链表结构
头节点：链表的第一个节点，通常用于方便地访问链表。有时也使用“哑节点”（dummy node）或“哨兵节点”（sentinel node）作为头节点，以简化边界情况的处理。
尾节点：链表的最后一个节点，其指针域为空
三、基本操作
1.插入操作
头插法：在链表头部插入新节点。新节点的指针指向当前头节点，然后更新头指针指向新节点。
尾插法：在链表尾部插入新节点。需要遍历链表找到尾节点，然后将尾节点的指针指向新节点，并更新尾指针（如果链表有尾指针引用的话）。
中间插入：在链表的中间位置插入新节点。需要找到插入位置的前一个节点，然后调整指针。
2.删除操作
删除头节点：更新头指针指向第二个节点（如果存在），并释放头节点的内存。
删除尾节点：需要遍历链表找到倒数第二个节点，然后将其指针设为空，并释放尾节点的内存。
删除中间节点：找到要删除的节点的前一个节点，然后调整其指针指向要删除节点的下一个节点，并释放要删除节点的内存。
3.查找操作
按值查找：从头节点开始遍历链表，比较每个节点的值，直到找到匹配的节点或遍历到链表末尾。
按位置查找：从头节点开始遍历链表，直到达到指定位置或遍历到链表末尾。
遍历操作
从头节点开始，依次访问每个节点，直到遍历到链表末尾（即遇到空指针）。
四、性能分析
时间复杂度：
插入、删除和查找操作在最坏情况下的时间复杂度为 O(n)，其中 n 是链表的长度。因为可能需要遍历整个链表才能找到插入、删除或查找的位置。
空间复杂度：
链表的空间复杂度取决于节点数量和每个节点所需的空间。除了存储数据的空间外，还需要额外的空间来存储指针。
五、优点和缺点
优点
插入和删除操作不需要移动大量数据，只需要调整指针。
不需要预先知道数据的大小。
链表在内存中的分配是动态的，可以灵活地调整大小。
缺点
访问某个节点需要从头节点开始遍历，时间复杂度较高。
需要额外的空间来存储指针。
链表节点的内存分配和释放相对复杂，可能导致内存碎片问题。
六、删除、插入元素动态图解
插入元素
删除元素
七、代码模版
#include<iostream>
#include<stdexcept>
using namespace std;#define eType intstruct ListNode {eType data;//数据域ListNode* next;//指针域，指向下一个节点ListNode(eType x):data(x),next(NULL){}
};class LinkedList {
private:ListNode* head;int size;
public:LinkedList() :size(0), head(NULL) {}//构造函数~LinkedList();//析构函数void inser(int i, eType x);//元素插入void remove(int i);//删除元素void update(int i, eType x);//更新元素ListNode* find(eType x);//按值查找元素ListNode* get(int i);//按序号查找bool isempty();//判空void print();//打印链表元素void append(eType x);//在链表尾部插入元素void ascInsert(eType x);//顺序插入元素
};LinkedList::~LinkedList() {ListNode* curr = head;//游标节点，表示表里链表到当前节点while (curr) {ListNode* t = curr;curr = curr->next;delete t;}
}void LinkedList::inser(int i, eType x) {if (i<0 || i>size) {throw std::out_of_range("Invalid position");}ListNode* newNode = new ListNode(x);if (!i) {newNode->next = head;head = newNode;}else {ListNode* curr = head;for (int j = 0; j < i - 1; j++) {curr = curr->next;}newNode->next = curr->next;curr->next = newNode;}size++;
}void LinkedList::remove(int i) {if (i<0 || i>=size) {throw std::out_of_range("Invalid position");}if (!i) {ListNode* t = head;head = head->next;delete t;}else {ListNode* curr = head;for (int j = 0; j < i - 1; j++) {curr = curr->next;}ListNode* t = curr->next;curr->next = curr->next->next;delete t;}size--;
}void LinkedList::update(int i, eType x) {get(i)->data = x;
}ListNode* LinkedList::find(eType x) {ListNode* curr = head;while (curr && curr->data != x) {curr = curr->next;}return curr;
}ListNode* LinkedList::get(int i) {if (i < 0 || i >= size) {throw std::out_of_range("Invalid position");}ListNode* curr = head;for (int j = 0; j < i; j++) {curr = curr->next;}return curr;
}void LinkedList::print() {ListNode* curr = head;while (curr) {cout << curr->data << " ";curr = curr->next;}cout << endl;
}void LinkedList::append(eType x) {inser(size, x);
}void LinkedList::ascInsert(eType x) {ListNode* curr = head;if (!size) {//如果链表为空inser(0,x);return;}for (int i = 0; i < size; i++) {if (x <= curr->data) {inser(i, x);return;}curr = curr->next;}inser(size, x);//在链表中找不到比插入的值大
}bool LinkedList::isempty() {return size == 0;
}int main() {return 0;
}
八、经典例题
1.数列有序!
(帅哥们这个蓝色字体可以点进去看原题)
#include<iostream>
#include<stdexcept>
using namespace std;#define eType intstruct ListNode {eType data;//数据域ListNode* next;//指针域，指向下一个节点ListNode(eType x):data(x),next(NULL){}
};class LinkedList {
private:ListNode* head;int size;
public:LinkedList() :size(0), head(NULL) {}//构造函数~LinkedList();//析构函数void inser(int i, eType x);//元素插入void remove(int i);//删除元素void update(int i, eType x);//更新元素ListNode* find(eType x);//按值查找元素ListNode* get(int i);//按序号查找bool isempty();//判空void print();//打印链表元素void append(eType x);//在链表尾部插入元素void ascInsert(eType x);//顺序插入元素
};LinkedList::~LinkedList() {ListNode* curr = head;//游标节点，表示表里链表到当前节点while (curr) {ListNode* t = curr;curr = curr->next;delete t;}
}void LinkedList::inser(int i, eType x) {if (i<0 || i>size) {throw std::out_of_range("Invalid position");}ListNode* newNode = new ListNode(x);if (!i) {newNode->next = head;head = newNode;}else {ListNode* curr = head;for (int j = 0; j < i - 1; j++) {curr = curr->next;}newNode->next = curr->next;curr->next = newNode;}size++;
}void LinkedList::remove(int i) {if (i<0 || i>=size) {throw std::out_of_range("Invalid position");}if (!i) {ListNode* t = head;head = head->next;delete t;}else {ListNode* curr = head;for (int j = 0; j < i - 1; j++) {curr = curr->next;}ListNode* t = curr->next;curr->next = curr->next->next;delete t;}size--;
}void LinkedList::update(int i, eType x) {get(i)->data = x;
}ListNode* LinkedList::find(eType x) {ListNode* curr = head;while (curr && curr->data != x) {curr = curr->next;}return curr;
}ListNode* LinkedList::get(int i) {if (i < 0 || i >= size) {throw std::out_of_range("Invalid position");}ListNode* curr = head;for (int j = 0; j < i; j++) {curr = curr->next;}return curr;
}void LinkedList::print() {ListNode* curr = head;while (curr) {cout << curr->data << " ";curr = curr->next;}cout << endl;
}void LinkedList::append(eType x) {inser(size, x);
}void LinkedList::ascInsert(eType x) {ListNode* curr = head;if (!size) {//如果链表为空inser(0,x);return;}for (int i = 0; i < size; i++) {if (x <= curr->data) {inser(i, x);return;}curr = curr->next;}inser(size, x);//在链表中找不到比插入的值大
}bool LinkedList::isempty() {return size == 0;
}int main() {int n, m;while (cin >> n >> m) {LinkedList l;if (!n && !m) break;for (int i = 0; i < n; i++) {int x;cin >> x;l.inser(i, x);}l.ascInsert(m);l.print();}return 0;
}
2.二进制链表转整数
(帅哥们这个蓝色字体可以点进去看原题)
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:int getDecimalValue(ListNode* head) {int sum=0;ListNode*curr=head;while(curr){sum=sum*2+curr->val;curr=curr->next;}return sum;}
};
3.面试题 02.02. 返回倒数第 k 个节点
(帅哥们这个蓝色字体可以点进去看原题)
这个就是经典双指针快慢指针的链表题
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode*fast=head;while(k--){fast=fast->next;}ListNode*slow=head;while(fast){slow=slow->next;fast=fast->next;}return slow->val;}
};
4.LCR 140. 训练计划 II
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* trainingPlan(ListNode* head, int cnt) {ListNode*fast=head;while(cnt--){fast=fast->next;}ListNode*slow=head;while(fast){slow=slow->next;fast=fast->next;}return slow;}
};
九、总结
单向链表是数据结构中的基础内容，理解其工作原理和基本操作对于进一步学习更高级的数据结构（如双向链表、循环链表、栈、队列等）非常重要
十、结语
我发的这些题目都是很简单很基础的题目，我不想一上来就发难题，先做简单题，后续我会整理题库，每个板块都会发有难度的题。学习编程是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，不会的地方就问，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油，我相信你一定能行。
想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家。
