如何理解链表与数组呢?
本帖最后由 正点原子 于 2022-1-7 17:41 编辑以下文章来源于:公众号:开源电子网,读取更多技术文章,请扫码关注
如何理解链表与数组呢?
在学习数据结构的时候,我们接触了数组和链表,那么两者到底有哪些区别呢,首先我们分别讨论。
一.数组
数组是有序的元素序列,用来存储一系列数据,例如我们定义一个数组inta ={0,1,2,3,4};的数组,inta为自定义设置固定长度,里面包含五个元素,a对应数组的第一个元素,而a对应数组的最后一个元素,从内存来看:数组由连续的内存位置组成,如以下图所示:
数组优点?
由于数组是连续的内存位置组成的,所以数组应用需要快速访问数据。
数组缺点?
①如果我们插入一个元素,显然上述的int a数组无法插入的,因为该数组已经越界了,注意:数组不能动态扩展空间的,所以无法插入。
②如果我们删除一个元素a,那么后面的元素进行逐一的移位,如果我们数组的长度设置为1000呢,首位除去,是不是进行大面积的移位,造成时间的复杂度是非常高的。例如排队时候,前面除去一个,后面的人是不是逐一的向前一位。
二.链表
链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起,链表分为两种链表(单向和双向)而单向和双向链表也分为两种,循环还是不循环,接下来我们就以单向链表为例,
在了解单向链表之前,我们必须知道单向链表的结构体怎么定义的,如以下源码所示:
<font size="4">struct os_node</font>
<font size="4">{ </font>
<font size="4"> /* 下一个节点的指针 */ </font>
<font size="4"> struct os_node *next; </font>
<font size="4"> uint8_t data</font>
<font size="4">};</font>
这个结构体主要包含了两个,一个是挂载的数据,另一个是成员变量next,指向下一个节点的指针,在我们学习C语言时候,指针也就是内存地址,那么它指向内存地址的,如以下源码所示:
<font size="4">#include<stdio.h></font>
<font size="4">int main()</font>
<font size="4">{</font>
<font size="4">/*int类型的变量*/</font>
<font size="4">int lv_variate=10;</font>
<font size="4">/*指针变量*/</font>
<font size="4">int*ip_variate;</font>
<font size="4">/*在指针变量存储lv_variate地址*/</font>
<font size="4">ip_variate=&lv_variate;</font>
<font size="4">printf("ip_variate指针变量存储的地址:%p\n",ip_variate);</font>
<font size="4">return 0;</font>
<font size="4">}</font>
执行上述的源码我们就可以得到下面的图:
总结:ip_variate的指针变量存储的是lv_variate变量的地址。
既然我们已经知道指针变量存储的是指向变量的地址,那么我们看下面单向链表的示意图我们就会明白。
从内存来看,单向链表的节点是非连续的内存位置,如以下图所示:
所以我们需要插入一个数据或者删除一个数据,我们只需要修改next的下一个节点指针指向即可,如以下图所示:
我们只要把数据节点1的next指针指向数据节点2的下一个数据节点即可,插入也是一样,如图所示:
链表的优点
应用于插入以及删除数据,因为他们直接插入以及直接删除。
链表的缺点
由于链表是非连续的内存位置组成的,所以链表不适用快速访问数据。
{:victory:}哦,原来是这样的啊。
继续。。。
页:
[1]