常见链表的设计

2024-09-06 19:12
文章标签 设计 常见 链表

本文主要是介绍常见链表的设计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表是非常常见的一种数据结构，尤其是在一些操作系统中。
链表常见的操作有插入节点、删除节点、访问节点等。
本文实现了单向链表、双向链表的设计，并提供了可直接运行的C++代码，此外还说明了使用C语言在实现上的差异

本文所使用的图取自代码随想录

链表类型

  • 单链表

    image-20240905164200397

  • 双向链表

    image-20240905164239651

  • 循环链表

    image-20240905164300885

链表的存储方式

各个节点分布在内存的不同地址空间上，通过指针串联在一起

单链表的定义

struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

链表的操作

  • 删除节点

    image-20240905164922557

  • 添加节点

    image-20240905164951835

与数组对比

插入/删除（时间复杂度）查询（时间复杂度）使用场景
数组O(n)O(1)数据量固定，频繁查询，较少增删
链表O(1)O(n)数据量不固定，频繁增删，较少查询

移除链表元素

struct node {int value;node *next;node(int x) : value(x), next(nullptr) {}
};node *removeElement(node *head, int val){node *dummyHead = new node(0);dummyHead->next = head;node *cur = dummyHead;while(cur->next != NULL){if(cur->next->value == val){node *tmp = cur->next;cur->next = cur->next->next;delete tmp;}else{cur = cur->next;}}head = dummyHead->next;delete dummyHead;return head;
}

链表设计

class MyList{    
public:struct node{int value;node *next;node(int initValue):value(initValue), next(nullptr){}};    MyList(){_dummyHead = new node(0);_size = 0;}// 获取第index个结点的数值int get(int index){if(index > (_size-1) || index < 0){// throw out_of_range("index out of range!");cout << "index out of range!————return INT32_MAX = " << INT32_MAX << endl;return INT32_MAX;}node *cur = _dummyHead->next;while(index){cur = cur->next;index--;}return cur->value;}// 在链表最前面插入一个节点void addAtHead(int value){node *newNode = new node(value);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}// 在链表最后面插入一个元素void addAtTail(int value){node *newNode = new node(value);        node *cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}// 在第index个节点之前插入一个节点void addAtIndex(int index, int value){if(index > _size){return;}if(index < 0){index = 0;}node *newNode = new node(value);node *cur = _dummyHead;while(index != 0){cur = cur->next;index--;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点void deleteAtIndex(int index){if(index < 0 || index >= _size){return;}node *cur = _dummyHead;while(index != 0){cur = cur->next;index--;}node *tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = nullptr;_size--;}// 打印链表void printList(){node *cur = _dummyHead;while(cur->next != nullptr){cout << cur->next->value;cur = cur->next;if(cur->next){cout << "->";}}cout << endl;}private:int _size;node *_dummyHead;    
};

单独实现插入节点

struct node{int value;node *next;node(int initValue):value(initValue), next(nullptr){}
};
void addAtIndex(node *&head, int index, int value){node *dummyHead = new node(0);dummyHead->next = head;node *cur = dummyHead;int size = 0;    while(cur->next != nullptr){size++;cur = cur->next;}if(index < 0){index = 0;}if(index > size){delete dummyHead;cout << "index is invalid" << endl;return;}cur = dummyHead;while(index){cur = cur->next;index--;}node *newNode = new node(value);newNode->next = cur->next;cur->next = newNode;size++;head = dummyHead->next;delete dummyHead;
}

使用C语言实现，与C++基本一致，只不过我们要自己定义结点的创建函数，并且new/delete要对应转换为malloc/free

typedef struct node{int value;struct node *next;
}node;node *createNode(int value){node *newNode = (node *)malloc(sizeof(struct node));newNode->value = value;newNode->next = NULL;return newNode;
}void addAtIndex(node **head, int index, int value){node *dummyHead = createNode(0);dummyHead->next = *head;int size = 0;node *cur = dummyHead;while(cur->next != NULL){cur = cur->next;size++;}if(index < 0)index=0;if(index > size){free(dummyHead);    return;}cur = dummyHead;while(index){cur = cur->next;index--;}node *newNode = createNode(value);newNode->next = cur->next;cur->next = newNode;*head = dummyHead->next;free(dummyHead);
}

双向链表设计

class MyDualList{    
public:struct node{int value;node *next;node *prev;node(int initValue):value(initValue), next(nullptr), prev(nullptr){}};MyDualList(){_dummyHead = new node(0);_dummyTail = new node(0);_size = 0;_dummyHead->next = _dummyTail;_dummyTail->prev = _dummyHead;}int get(int index){if(index < 0 || index >= _size){return -1;}node *cur = _dummyHead->next;while(index){cur = cur->next;index--;}return cur->value;}void addAtHead(int value){node *newNode = new node(value);newNode->next = _dummyHead->next;_dummyHead->next->prev = newNode; // 跟单链表一致，只是在指针换向时多考虑一个prev指针_dummyHead->next = newNode;newNode->prev = _dummyHead; //_size++;}void addAtTail(int value){node *newNode = new node(value);// 这里设计的双向链表，与单向链表相比，末尾节点会指向_dummyTail，基于此可以像单向链表一样写// 不过从另一个角度来说，我们的尾插可以看作在_dummyTail之前插入一个节点_dummyTail->prev->next = newNode;newNode->prev = _dummyTail->prev;newNode->next = _dummyTail;_dummyTail->prev = newNode;_size++;}void addAtIndex(int index, int value){if(index < 0)index=0;if(index > _size)return;node *cur = _dummyHead;while(index){cur = cur->next;index--;}node *newNode = new node(value);newNode->next = cur->next;cur->next->prev = newNode;cur->next = newNode;newNode->prev = cur;_size++;}void deleteAtIndex(int index){if(index < 0 || index >= _size)return;node *cur = _dummyHead;while(index){cur = cur->next;index--;}node *tmp = cur->next;cur->next = cur->next->next;cur->next->prev = cur;delete tmp;_size--;}void printListForward(){node *cur = _dummyHead;while(cur->next != _dummyTail){cout << cur->next->value;cur = cur->next;if(cur->next != _dummyTail){cout << "->";}}cout << endl;}void printListReverse(){node *cur = _dummyTail;while(cur->prev != _dummyHead){cout << cur->prev->value;cur = cur->prev;if(cur->prev != _dummyHead){cout << "<-";}}cout << endl;}    
private:int _size = 0;node *_dummyHead, *_dummyTail;    
};

测试部分

  • 函数测试——添加与移除链表元素

    /* C++ */
#include<iostream>
using namespace std;struct node {int value;node *next;node(int x) : value(x), next(NULL) {}
};void printList(node *head){node *dummyHead = new node(0);dummyHead->next = head;node *cur = dummyHead;while(cur->next){cout << cur->next->value;cur = cur->next;if(cur->next){cout << "->";}}cout << endl;
}void removeElement(node *&head, int val){node *dummyHead = new node(0);dummyHead->next = head;node *cur = dummyHead;while(cur->next != NULL){if(cur->next->value == val){node *tmp = cur->next;cur->next = cur->next->next;delete tmp;}else{cur = cur->next;}}head = dummyHead->next;delete dummyHead;
}void addAtIndex(node *&head, int index, int value){node *dummyHead = new node(0);dummyHead->next = head;node *cur = dummyHead;int size = 0;    while(cur->next != nullptr){size++;cur = cur->next;}if(index < 0){index = 0;}if(index > size){delete dummyHead;cout << "index is invalid" << endl;return;}cur = dummyHead;while(index){cur = cur->next;index--;}node *newNode = new node(value);newNode->next = cur->next;cur->next = newNode;size++;head = dummyHead->next;delete dummyHead;dummyHead = nullptr;
}int main(void){node *head = new node(0);addAtIndex(head, 1, 1);addAtIndex(head, 2, 2);addAtIndex(head, 3, 3);addAtIndex(head, 4, 4);addAtIndex(head, 5, 5);cout << "the LinkedList is:" << endl;printList(head);removeElement(head, 2);printList(head);return 0;
}

image-20240906163301527

/* C */
#include<stdio.h>
#include<stdlib.h>typedef struct node{int value;struct node *next;
}node;node *createNode(int value){node *newNode = (node *)malloc(sizeof(struct node));newNode->value = value;newNode->next = NULL;return newNode;
}void printList(node *head){node *dummyHead = createNode(0);dummyHead->next = head;node *cur = dummyHead;while(cur->next){printf("%d", cur->next->value);cur = cur->next;if(cur->next){printf("->");}}printf("\n");
}void addAtIndex(node **head, int index, int value){node *dummyHead = createNode(0);dummyHead->next = *head;int size = 0;node *cur = dummyHead;while(cur->next != NULL){cur = cur->next;size++;}if(index < 0)index=0;if(index > size){free(dummyHead);    return;}cur = dummyHead;while(index){cur = cur->next;index--;}node *newNode = createNode(value);newNode->next = cur->next;cur->next = newNode;*head = dummyHead->next;free(dummyHead);
}void removeElement(node **head, int val){node *dummyHead = createNode(0);dummyHead->next = *head;node *cur = dummyHead;while(cur->next != NULL){if(cur->next->value == val){node *tmp = cur->next;cur->next = cur->next->next;free(tmp);}else{cur = cur->next;}}*head = dummyHead->next;free(dummyHead);
}int main(void){node *head = createNode(0);addAtIndex(&head, 1, 1);addAtIndex(&head, 2, 2);addAtIndex(&head, 3, 3);addAtIndex(&head, 4, 4);addAtIndex(&head, 5, 5);printf("the LinkedList is:\n");printList(head);removeElement(&head, 0);printList(head);return 0;
}

image-20240906163424875

  • 链表设计测试

    #include<iostream>
using namespace std;class MyList{    
public:struct node{int value;node *next;node(int initValue):value(initValue), next(nullptr){}};    MyList(){_dummyHead = new node(0);_size = 0;}// 获取第index个结点的数值int get(int index){if(index > (_size-1) || index < 0){// throw out_of_range("index out of range!");cout << "index out of range!————return INT32_MAX = " << INT32_MAX << endl;return INT32_MAX;}node *cur = _dummyHead->next;while(index){cur = cur->next;index--;}return cur->value;}// 在链表最前面插入一个节点void addAtHead(int value){node *newNode = new node(value);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}// 在链表最后面插入一个元素void addAtTail(int value){node *newNode = new node(value);        node *cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}// 在第index个节点之前插入一个节点void addAtIndex(int index, int value){if(index > _size){return;}if(index < 0){index = 0;}node *newNode = new node(value);node *cur = _dummyHead;while(index != 0){cur = cur->next;index--;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点void deleteAtIndex(int index){if(index < 0 || index >= _size){return;}node *cur = _dummyHead;while(index != 0){cur = cur->next;index--;}node *tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp = nullptr;_size--;}// 打印链表void printList(){node *cur = _dummyHead;while(cur->next != nullptr){cout << cur->next->value;cur = cur->next;if(cur->next){cout << "->";}}cout << endl;}private:int _size;node *_dummyHead;    
};int main(){MyList list;list.addAtIndex(0,0);list.addAtIndex(1,1);list.addAtIndex(2,2);list.addAtIndex(3,3);list.addAtIndex(4,3);list.addAtIndex(5,4);list.printList();list.deleteAtIndex(3);list.printList();cout << list.get(1) << endl;return 0;
}

image-20240906163634682

  • 双向链表设计测试

    #include<iostream>
using namespace std;class MyDualList{    
public:struct node{int value;node *next;node *prev;node(int initValue):value(initValue), next(nullptr), prev(nullptr){}};MyDualList(){_dummyHead = new node(0);_dummyTail = new node(0);_size = 0;_dummyHead->next = _dummyTail;_dummyTail->prev = _dummyHead;}int get(int index){if(index < 0 || index >= _size){return -1;}node *cur = _dummyHead->next;while(index){cur = cur->next;index--;}return cur->value;}void addAtHead(int value){node *newNode = new node(value);newNode->next = _dummyHead->next;_dummyHead->next->prev = newNode; // 跟单链表一致，只是在指针换向时多考虑一个prev指针_dummyHead->next = newNode;newNode->prev = _dummyHead; //_size++;}void addAtTail(int value){node *newNode = new node(value);// 这里设计的双向链表，与单向链表相比，末尾节点会指向_dummyTail，基于此可以像单向链表一样写// 不过从另一个角度来说，我们的尾插可以看作在_dummyTail之前插入一个节点_dummyTail->prev->next = newNode;newNode->prev = _dummyTail->prev;newNode->next = _dummyTail;_dummyTail->prev = newNode;_size++;}void addAtIndex(int index, int value){if(index < 0)index=0;if(index > _size)return;node *cur = _dummyHead;while(index){cur = cur->next;index--;}node *newNode = new node(value);newNode->next = cur->next;cur->next->prev = newNode;cur->next = newNode;newNode->prev = cur;_size++;}void deleteAtIndex(int index){if(index < 0 || index >= _size)return;node *cur = _dummyHead;while(index){cur = cur->next;index--;}node *tmp = cur->next;cur->next = cur->next->next;cur->next->prev = cur;delete tmp;_size--;}void printListForward(){node *cur = _dummyHead;while(cur->next != _dummyTail){cout << cur->next->value;cur = cur->next;if(cur->next != _dummyTail){cout << "->";}}cout << endl;}void printListReverse(){node *cur = _dummyTail;while(cur->prev != _dummyHead){cout << cur->prev->value;cur = cur->prev;if(cur->prev != _dummyHead){cout << "<-";}}cout << endl;}    
private:int _size = 0;node *_dummyHead, *_dummyTail;    
};int main(){MyDualList list;list.addAtIndex(0,0);list.addAtIndex(1,1);list.addAtIndex(2,2);list.addAtIndex(3,3);list.addAtIndex(4,3);list.addAtIndex(5,4);list.addAtTail(60);list.printListForward();list.printListReverse();list.deleteAtIndex(3);list.printListForward();list.printListReverse();cout << list.get(1) << endl;return 0;
}

image-20240906163742188

这篇关于常见链表的设计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1142876。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
怎么让1台电脑共享给7人同时流畅设计

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域，图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能，成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限，比如只有一台高性能电脑时，如何高效地让七人同时流畅地进行设计工作，便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器（CPU）：选择多核、高线程的处理器，例如Intel的至强系列或AMD的Ry
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
基于51单片机的自动转向修复系统的设计与实现

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍：✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师，一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生，希望您们都共创辉煌！✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
SprinBoot+Vue网络商城海鲜市场的设计与实现

SprinBoot+Vue网络商城海鲜市场的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍：CSDN认证博客专家，CSDN平台Java领域优质创作者，全网30w+
阅读更多...
JVM 常见异常及内存诊断

JVM 常见异常及内存诊断

栈内存溢出 栈内存大小设置：-Xss size 默认除了window以外的所有操作系统默认情况大小为 1MB，window 的默认大小依赖于虚拟机内存。 栈帧过多导致栈内存溢出 下述示例代码，由于递归深度没有限制且没有设置出口，每次方法的调用都会产生一个栈帧导致了创建的栈帧过多，而导致内存溢出(StackOverflowError)。 示例代码： 运行结果： 栈帧过大导致栈内存
阅读更多...
单片机毕业设计基于单片机的智能门禁系统的设计与实现

单片机毕业设计基于单片机的智能门禁系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍程序代码部分参考 设计清单具体实现截图参考文献设计获取 前言 💗博主介绍：✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师，一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生，希望您们都共创辉煌！✌💗 👇🏻 精彩专栏 推荐订
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2