• 本文主题：通过一道题目，学习链表的基本操作

• 更多算法：动态规划 ✔️ 边界控制

• 我的主页：蓝色学者的主页

文章目录

• 一、前言
• 二、题目信息
• 三、解决方案
• • • • 3.0什么是链表？
      • 3.1节点的概念
      • • 虚拟头节点
      • 3.2链表创建
      • 3.3头插/尾插
      • 3.4在给定位置前插入
      • 3.5删除给定位置节点
      • 3.6删除链表
• 四、完整参考代码
• 五、结语

一、前言

大家好久不见，今天学者想给大家分享一道题目，通过这道题目我们会学习链表的常规操作，只要熟练掌握这道题目，我们就掌握了链表的基本操作，一起来看看吧！

二、题目信息

点我做题：设计链表

本题题目描述复杂，在这里简单描述一下题目要求实现的功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
• ListFree() //C语言和C++需要手动销毁内存

这道题目说白了就是让我们设计一个链表，能够完成链表的基础操作即可！

三、解决方案

3.0什么是链表？

要创建一个链表，我们就要知道什么是链表，链表功能与顺序表（数组）相同，都是用来存储数据的表，与顺序表（数组）不同的是，链表的地址空间并不连续，如图：

我们把这种物理存储单元上非连续、非顺序的存储结构叫做链表

3.1节点的概念

要实现上述功能，我们需要有一个结构体实现，这个结构体有两点要求

1. 数据域
2. 指针域（指向下一个节点）

通过这样的方式，将整个链表串联在一起，以C/C++的结构体为例：

typedef struct mylinkedList{int val;//数据域struct mylinkedList* next;//指针域
} MyLinkedList;

虚拟头节点

在链表增删查改的过程中，常常有一些极端的情况需要单独处理，比如增加一个元素、删除一个元素这种情况，因此我们选择使用虚拟头节点（dummynode）来使操作统一，这样也更加简洁。

3.2链表创建

链表创建就是让我们返回一个节点，这个节点就代表了这个链表，我们顺便实现一个获取节点的函数getNodo() 后续操作都会使用到。

//创建一个节点
MyLinkedList* getNode()
{MyLinkedList* Node = (MyLinkedList*)malloc(sizeof(MyLinkedList));Node->val = 0;Node->next = NULL;return Node;
}//创建头节点并返回
MyLinkedList* myLinkedListCreate() {MyLinkedList* dummyNode = getNode();_size = 0;//可以设置为全局变量，也可以在对象里设置return dummyNode;
}

3.3头插/尾插

• 头插

头插即让此节点（newnode）成为第一个节点，我们只要调整指针指向的对象即可

1. newnode->firstnode（这样firstnode就成为了第二个节点）
2. dummyhead->newnode（这样虚拟头节点找到了新的头节点）

参考代码：

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {MyLinkedList* newnode = getNode();newnode->val = val;newnode->next = obj->next;obj->next = newnode;_size++;
}

• 尾插

尾插即在链表最后追加一个节点，因此我们需要找到最后一个节点，定义一个循环变量cur，只要cur->next是NULL，我们就停止循环，在cur位置重复与头插相同的操作即可。

参考代码：

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {MyLinkedList* cur = obj;while(cur->next != NULL){cur = cur->next;}MyLinkedList* newnode = getNode();newnode->val = val;cur->next = newnode;_size++;
}

3.4在给定位置前插入

与头插尾插相同，大家可以看图理解一下，需要注意的是本题要求在index位置前插入

可以采用数学归纳法来总结：

1. 在1位置前插入，cur需要走1次
2. 在0位置前插入，cur需要走0次

循环里的（index–）恰好就满足我们的需要

参考代码：

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {if(index > _size) return;//大于链表肯定无法插入直接返回if(index < 0) index = 0;//小于0就是按照头插逻辑进行MyLinkedList* cur = obj;MyLinkedList* newnode = getNode();while(index--){cur = cur->next;}newnode->val = val;newnode->next = cur->next;cur->next = newnode;_size++;
}

3.5删除给定位置节点

如图，要删除第0个节点，只需要找到前一个节点，让前一个节点指向要删除的节点的下一个节点即可，大家可以看图理解一下，虚线部分就是我们要删除的元素，至于如何找到前一个元素，我在3.4在给定位置前插入这一小节已经讲过，大家可以回去翻阅~

参考代码：

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {if(index >= _size || index < 0) return;//检查是否符合删除的要求，不符合直接返回即可MyLinkedList* cur = obj;while(index--){cur=cur->next;}cur->next = cur->next->next;_size--;}

3.6删除链表

C/C++等语言需要手动删除链表，逻辑也非常简单，我们只需要一个循环变量，将它赋值为cur，释放掉对应内存再重复此操作即可

参考代码：

void myLinkedListFree(MyLinkedList* obj) {while(obj != NULL){MyLinkedList* tmp = obj;obj = obj->next;free(tmp);}
}

四、完整参考代码

typedef struct mylinkedList{int val;struct mylinkedList* next;
} MyLinkedList;int _size = 0;MyLinkedList* getNode()
{MyLinkedList* Node = (MyLinkedList*)malloc(sizeof(MyLinkedList));Node->val = 0;Node->next = NULL;return Node;
}MyLinkedList* myLinkedListCreate() {MyLinkedList* dummyNode = getNode();_size = 0;return dummyNode;
}int myLinkedListGet(MyLinkedList* obj, int index) {if(index < 0 || index >= _size) return -1;MyLinkedList* cur = obj->next;while(index--){cur = cur->next;}return cur->val;
}void myLinkedListAddAtHead(MyLinkedList* obj, int val) {MyLinkedList* newnode = getNode();newnode->val = val;newnode->next = obj->next;obj->next = newnode;_size++;
}void myLinkedListAddAtTail(MyLinkedList* obj, int val) {MyLinkedList* cur = obj;while(cur->next != NULL){cur = cur->next;}MyLinkedList* newnode = getNode();newnode->val = val;cur->next = newnode;_size++;
}void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {if(index > _size) return;if(index < 0) index = 0;MyLinkedList* cur = obj;MyLinkedList* newnode = getNode();while(index--){cur = cur->next;}newnode->val = val;newnode->next = cur->next;cur->next = newnode;_size++;
}void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {if(index >= _size || index < 0) return;MyLinkedList* cur = obj;while(index--){cur=cur->next;}cur->next = cur->next->next;_size--;}void myLinkedListFree(MyLinkedList* obj) {while(obj != NULL){MyLinkedList* tmp = obj;obj = obj->next;free(tmp);}
}

五、结语

到这里，本篇文章所有的内容就结束了，相信你已经学会了链表的基本操作！

如果你感觉有所收获，可以点赞 + 收藏 +关注 支持一下学者哦~ 我们下次见~