如何理解链表与数组呢？

正点原子 · 发表于 2021-11-2 11:50:05

本帖最后由正点原子于 2022-1-7 17:41 编辑

以下文章来源于：公众号：开源电子网，读取更多技术文章，请扫码关注
讨论发帖图.png

如何理解链表与数组呢？

   在学习数据结构的时候，我们接触了数组和链表，那么两者到底有哪些区别呢，首先我们分别讨论。

   一.数组

   数组是有序的元素序列，用来存储一系列数据，例如我们定义一个数组inta[5] ={0,1,2,3,4};的数组，inta[5]为自定义设置固定长度，里面包含五个元素，a[0]对应数组的第一个元素，而a[n-1]对应数组的最后一个元素，从内存来看：数组由连续的内存位置组成，如以下图所示：

   数组优点?

   由于数组是连续的内存位置组成的，所以数组应用需要快速访问数据。

   数组缺点?

   ①如果我们插入一个元素，显然上述的int a[5]数组无法插入的，因为该数组已经越界了，注意：数组不能动态扩展空间的，所以无法插入。

   ②如果我们删除一个元素a[0]，那么后面的元素进行逐一的移位，如果我们数组的长度设置为1000呢，首位除去，是不是进行大面积的移位，造成时间的复杂度是非常高的。例如排队时候，前面除去一个，后面的人是不是逐一的向前一位。

   二.链表

   链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起，链表分为两种链表(单向和双向)而单向和双向链表也分为两种，循环还是不循环，接下来我们就以单向链表为例，

   在了解单向链表之前，我们必须知道单向链表的结构体怎么定义的，如以下源码所示：

struct os_node
{
/* 下一个节点的指针 */
struct os_node *next;
uint8_t data
};

复制代码

这个结构体主要包含了两个，一个是挂载的数据，另一个是成员变量next，指向下一个节点的指针，在我们学习C语言时候，指针也就是内存地址，那么它指向内存地址的，如以下源码所示：

#include<stdio.h>
int main()
{
/*int类型的变量*/
int lv_variate=10;
/*指针变量*/
int*ip_variate;
/*在指针变量存储lv_variate地址*/
ip_variate=&lv_variate;
printf("ip_variate指针变量存储的地址:%p\n",ip_variate);
return 0;
}

复制代码

执行上述的源码我们就可以得到下面的图：

如何理解链表与数组974.png

      总结：ip_variate的指针变量存储的是lv_variate变量的地址。

   既然我们已经知道指针变量存储的是指向变量的地址，那么我们看下面单向链表的示意图我们就会明白。

      如何理解链表与数组1065.png

从内存来看，单向链表的节点是非连续的内存位置，如以下图所示：

如何理解链表与数组1099.png

   所以我们需要插入一个数据或者删除一个数据，我们只需要修改next的下一个节点指针指向即可，如以下图所示：

      如何理解链表与数组1155.png

   我们只要把数据节点1的next指针指向数据节点2的下一个数据节点即可，插入也是一样，如图所示：

      如何理解链表与数组1206.png

   链表的优点

   应用于插入以及删除数据，因为他们直接插入以及直接删除。

   链表的缺点

   由于链表是非连续的内存位置组成的，所以链表不适用快速访问数据。

ordman · 发表于 2021-11-2 12:38:20

哦，原来是这样的啊。
继续。。。

如何理解链表与数组呢？

阿莫论坛20周年了！感谢大家的支持与爱护！！

相关帖子