如何理解链表与数组呢？ (amobbs.com 阿莫电子技术论坛) -

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

如何理解链表与数组呢？

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

以下文章来源于：公众号：开源电子网，读取更多技术文章，请扫码关注

如何理解链表与数组呢？

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

一.数组

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



 数组优点?

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

 数组缺点?

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

 ②如果我们删除一个元素a，那么后面的元素进行逐一的移位，如果我们数组的长度设置为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;

}

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



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

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



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



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



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



 链表的优点

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

 链表的缺点

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

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

{:victory:}哦，原来是这样的啊。
继续。。。

页: [1]

amobbs.com 阿莫电子技术论坛's Archiver

如何理解链表与数组呢？