如何理解链表与数组呢？

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

如何理解链表与数组呢？

在学习数据结构的时候，我们接触了数组和链表，那么两者到底有哪些区别呢，首先我们分别讨论。 数组： 数组是有序的元素序列，用来存储一系列数据，例如我们定义一个数组int a[5] ={0,1,2,3,4};的数组， int a[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

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的下一个数据节点即可，插入也是一样，如图所示：

链表的优点：

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

链表的缺点：

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