一、链表定义
链表是一种数据结构，它由一系列节点组成，这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用（指针）。链表的最后一个节点通常指向一个特定的值（如空值或null），表示链表的结束。
链表是一种数据结构，它由一系列节点组成，这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用（指针）。链表的最后一个节点通常指向一个特定的值（如空值或null），表示链表的结束。
链表可以分为单链表和双链表两种主要类型：
1. 单链表（Singly Linked List）：每个节点包含数据和指向下一个节点的指针。链表的最后一个节点指向null。
1. 节点1 节点2 节点3 2. | 数据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("NULL\n"); } // 释放链表内存 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. 数据库：数据库中的索引通常使用链表实现，以支持高效的插入和删除操作。
总的来说，链表在许多场景中都是一种强大且灵活的数据结构，特别适合那些需要频繁插入和删除操作的应用。
小结
大家点赞、收藏、关注、评论啦 ！
谢谢哦！如果不懂，欢迎大家下方讨论学习哦。
