【数据结构】链表(单链表与双链表实现+原理+源码)
博主介绍：✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦！
🍅附上相关C语言版源码讲解🍅
👇🏻 精彩专栏推荐订阅👇🏻 不然下次找不到哟
一、链表定义
链表是一种数据结构，它由一系列节点组成，这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用（指针）。链表的最后一个节点通常指向一个特定的值（如空值或null），表示链表的结束。
链表是一种数据结构，它由一系列节点组成，这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用（指针）。链表的最后一个节点通常指向一个特定的值（如空值或null），表示链表的结束。
链表可以分为单链表和双链表两种主要类型：
1. 单链表（Singly Linked List）：每个节点包含数据和指向下一个节点的指针。链表的最后一个节点指向null。
节点1 节点2 节点3
| 数据1 | -> | 数据2 | -> | 数据3 | -> null
2. 双链表（Doubly Linked List）：每个节点包含数据、指向下一个节点的指针，以及指向前一个节点的指针。这使得在双链表中可以更方便地进行前向和后向遍历。
null <- | 数据1 | <-> | 数据2 | <-> | 数据3 | -> null
链表优点： 链表相对于数组的优势在于插入和删除操作的效率较高，因为不需要移动大量元素，只需调整节点的指针。然而，链表的缺点是访问元素时需要按顺序遍历，而数组可以通过索引直接访问元素。链表在内存中不需要连续的存储空间，因此可以更灵活地分配内存。
二、链表实战
1、单链表（C语言实现版本）
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
struct Node {
int data; // 节点数据
struct Node* next; // 指向下一个节点的指针
};
// 定义链表结构
struct LinkedList {
struct Node* head; // 链表头指针
};
// 初始化链表
void initLinkedList(struct LinkedList* list) {
list->head = NULL; // 将头指针初始化为NULL，表示链表为空
}
// 在链表末尾添加节点
void append(struct LinkedList* list, int data) {
// 创建新节点
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
// 判断链表是否为空
if (list->head == NULL) {
// 如果为空，将新节点设为头节点
list->head = new_node;
} else {
// 如果不为空，找到链表末尾，将新节点链接到末尾
struct Node* current = list->head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
}
}
// 在链表开头添加节点
void prepend(struct LinkedList* list, int data) {
// 创建新节点
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = list->head;
// 将新节点设为头节点
list->head = new_node;
}
// 删除节点
void deleteNode(struct LinkedList* list, int data) {
struct Node* current = list->head;
struct Node* prev = NULL;
// 遍历链表，找到待删除节点及其前一个节点
while (current != NULL && current->data != data) {
prev = current;
current = current->next;
}
// 如果找到待删除节点
if (current != NULL) {
// 如果待删除节点不是头节点
if (prev != NULL) {
prev->next = current->next;
} else {
// 如果待删除节点是头节点
list->head = current->next;
}
free(current); // 释放内存
}
}
// 更新节点
void updateNode(struct LinkedList* list, int oldData, int newData) {
struct Node* current = list->head;
// 遍历链表，找到待更新节点
while (current != NULL && current->data != oldData) {
current = current->next;
}
// 如果找到待更新节点
if (current != NULL) {
current->data = newData; // 更新节点数据
}
}
// 搜索节点
struct Node* searchNode(struct LinkedList* list, int data) {
struct Node* current = list->head;
// 遍历链表，找到包含指定数据的节点
while (current != NULL && current->data != data) {
current = current->next;
}
return current; // 返回节点指针
}
// 显示链表内容
void display(struct LinkedList* list) {
struct Node* current = list->head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULLn");
}
// 释放链表内存
void freeLinkedList(struct LinkedList* list) {
struct Node* current = list->head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
list->head = NULL;
}
int main() {
struct LinkedList myLinkedList;
initLinkedList(&myLinkedList);
// 添加节点
append(&myLinkedList, 1);
append(&myLinkedList, 2);
append(&myLinkedList, 3);
// 显示链表内容
printf("链表内容：");
display(&myLinkedList);
// 在开头添加节点
prepend(&myLinkedList, 0);
// 显示链表内容
printf("在开头添加节点后的链表：");
display(&myLinkedList);
// 删除节点
deleteNode(&myLinkedList, 2);
// 显示链表内容
printf("删除节点后的链表：");
display(&myLinkedList);
// 更新节点
updateNode(&myLinkedList, 1, 10);
// 显示链表内容
printf("更新节点后的链表：");
display(&myLinkedList);
// 搜索节点
int searchData = 10;
struct Node* searchResult = searchNode(&myLinkedList, searchData);
if (searchResult != NULL) {
printf("找到数据为 %d 的节点。n", searchData);
} else {
printf("未找到数据为 %d 的节点。n", searchData);
}
// 释放链表内存
freeLinkedList(&myLinkedList);
return 0;
}
执行结果详细：
2、双链表（C++）
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef struct Node
{
int data;
struct Node *prior;
struct Node *next;
} LinkList;
LinkList *Create()
{
LinkList *head;
head=(LinkList*)malloc(sizeof(LinkList));
if(head!=NULL)
{
head->prior=NULL;
head->next=NULL;
return head;
}
else return NULL;
}
int Insert(LinkList *head,int e) //尾插法
{
LinkList *p;
LinkList *q=head;
p=(LinkList*)malloc(sizeof(LinkList));
if(p!=NULL)
{
p->data=e;
p->prior=NULL;
p->next=NULL;
while(q->next!=NULL)
{
q=q->next;
}
q->next=p;
return 1;
}
return 0;
}
LinkList* Change(LinkList *head) //变成双向链表后返回一个尾指针
{
LinkList *p,*q;
p=head;
q=p->next;
while(q!=NULL)
{
q->prior=p;
p=p->next;
q=q->next;
}
return p;
}
void Output1(LinkList *head) //从头到尾遍历输出
{
LinkList *p;
p=head->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("n");
}
void Output2(LinkList *tail) //从尾到头遍历输出
{
LinkList *p;
p=tail;
while(p->prior!=NULL)
{
printf("%d ",p->data);
p=p->prior;
}
printf("n");
}
void FreeLink(LinkList *head) //释放
{
LinkList *p,*q;
p=head;
q=NULL;
while(p!=NULL)
{
q=p;
p=p->next;
free(q);
}
}
int main()
{
LinkList *phead,*tail;
int n,e,flag;
phead=Create();
if(phead!=NULL)
{
cout<<"请输入长度:";
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&e);
flag=Insert(phead,e);
}
cout<<"从头到尾输出为: ";
Output1(phead);
tail=Change(phead);
cout<<"从尾到头输出为: ";
Output2(tail);
FreeLink(phead);
}
return 0;
}
代码执行结果：
三、分析总结
链表是一种常见的数据结构，具有一些优点和应用：
优点：
1. 动态内存分配：链表允许在运行时动态分配内存，这使得它更加灵活，不需要预先指定存储空间大小，通过动态分配内存可以实现降低时间运行成本。
2. 插入和删除效率高：在链表中插入和删除节点相对容易且效率较高。相比之下，数组在中间或开头插入/删除元素可能需要移动大量元素。
3. 大小可变：*链表可以根据需要动态增长或缩小，而不浪费内存。
应用：
1. 实现动态数据结构：链表常用于实现其他动态数据结构，如栈、队列、图等。
2. 内存分配：动态链表的能力使其在动态内存分配的场景中非常有用，例如，动态分配内存的链表可用于管理操作系统的进程列表。
3. 实现算法：链表常用于算法实现，例如，链表在排序算法、图算法等方面有广泛的应用。
4. 嵌入式系统： 在资源受限的嵌入式系统中，链表可以更好地处理动态数据。
5. LRU缓存淘汰算法：链表可以用于实现LRU（Least Recently Used）缓存淘汰算法，用于管理缓存中的数据。
6. 数据库：数据库中的索引通常使用链表实现，以支持高效的插入和删除操作。
总的来说，链表在许多场景中都是一种强大且灵活的数据结构，特别适合那些需要频繁插入和删除操作的应用。
小结
大家点赞、收藏、关注、评论啦 ！
谢谢哦！如果不懂，欢迎大家下方讨论学习哦。