C语言数据结构一一如何理解链表与数组呢？

正点原子运营

以下文章摘自微信公众号——开源电子网《如何理解链表与数组呢？ 》
更多技术文章，请扫下方二维码关注





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

一.数组

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




数组优点?

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

数组缺点?

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

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

二.链表

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

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

1. struct os_node
   
2. 
   
3. {
   
4. 
   
5.      /* 下一个节点的指针 */
   
6. 
   
7.      struct os_node *next;
   
8. 
   
9. uint8_t data
   
10. 
    
11. };

复制代码

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

1. #include<stdio.h>
   
2. 
   
3. int main()
   
4. 
   
5. {
   
6. 
   
7.   /*int类型的变量*/
   
8. 
   
9.   int lv_variate=10;
   
10. 
    
11.   /*指针变量*/
    
12. 
    
13.   int*ip_variate;
    
14. 
    
15.   /*在指针变量存储lv_variate地址*/
    
16. 
    
17.   ip_variate=&lv_variate;
    
18. 
    
19.   printf("ip_variate指针变量存储的地址:%p\n",ip_variate);
    
20. 
    
21.   return 0;
    
22. 
    
23. }

复制代码

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



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

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



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



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



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




链表的优点

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

链表的缺点

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

返璞归真

学习了