当前位置: 首页 > news >正文

【数据结构】链表(单链表与双链表实现+原理+源码)

博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦!

🍅附上相关C语言版源码讲解🍅

👇🏻 精彩专栏推荐订阅👇🏻 不然下次找不到哟

文章目录

    • 一、链表定义

      二、链表实战

      1、单链表(C语言实现版本)

      2、双链表(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("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. 数据库:数据库中的索引通常使用链表实现,以支持高效的插入和删除操作。

总的来说,链表在许多场景中都是一种强大且灵活的数据结构,特别适合那些需要频繁插入和删除操作的应用。

小结

大家点赞、收藏、关注、评论啦 !

谢谢哦!如果不懂,欢迎大家下方讨论学习哦。

http://www.lryc.cn/news/287098.html

相关文章:

  • 14027.ptp 控制流
  • 【昕宝爸爸小模块】深入浅出之为什么POI的SXSSFWorkbook占用内存更小
  • CentOS安装Flume
  • Qt 多次绘图
  • 设计模式介绍
  • linux 之 ln 命令
  • 【设计模式】张一鸣笔记:责任链接模式怎么用?
  • Vulnhub-dc4
  • MySQL45道练习题
  • HTML5和CSS3的新特性
  • 【MySQL】表列数和行大小限制详解
  • 算法基础学习|双指针算法
  • 4.远程登录服务
  • 代码随想录算法训练营第二十九天| 491.递增子序列、46.全排列、47.全排列 II
  • 基于若依的ruoyi-nbcio流程管理系统一种简单的动态表单模拟测试实现(五)
  • 多场景建模:阿里多场景多任务元学习方法M2M
  • 仿真机器人-深度学习CV和激光雷达感知(项目2)day03【机器人简介与ROS基础】
  • 【多商户开源-BSD- Fecmall 电商平台】
  • 2023春秋杯冬季赛 --- Crypto wp
  • ImageMagick使用手册
  • 嵌入式培训机构四个月实训课程笔记(完整版)-C++和QT编程第五天-Qt编程技巧若干解答(物联技术666)
  • 【蓝桥杯选拔赛真题59】python小写字母 第十五届青少年组蓝桥杯python 选拔赛比赛真题解析
  • 代码随想录算法训练营Day37|738.单调递增的数字、贪心算法总结
  • 笔记-影响力-对比,互惠,赌徒原理
  • PIL、cv2、numpy,和pytorch(torch)之间的转换
  • Java面试题50道
  • 电脑怎么剪辑视频?这些软件不可错过
  • HBase学习七:Compaction
  • MySQL定期整理磁盘碎片
  • 【centos7安装docker】