1.2.1-2部分数据结构的阐明02_链表

（1）链表数据结构：

概念：

将列表中相互毗连的节点不连续的存储在内存中。与数据不同，我们无法再恒定时间内访问任何元组，如果遍历所有则泯灭时间与元素总数n成正比。插入和删除1个元素的时间复杂度都是O(n)。链表中每个块成为一个节点，每个节点有两个字段，一个存储数据，另一个存储下一个节点的地点(链接字段)。

特点：

(1) 每个节点由2个字段构成，1个存储数据，另1个存储下一个节点的地点。
(2) 下一个节点的名称与上一个节点的link同等。
(3)存整数型的数组(array)占4字节，而链表因存储地点故所需8字节。对于大量数据，链表比数组所需的内存要小，缘故原由是数组要预留很多空的内存空间。

C语言中表述

（1）逻辑代码——插入第1个节点

1. typedef struct Node {
2.     int data;        // 用于存储数据
3.     struct Node* link;   // 指向下一个节点的指针
4. } Node;
7. //(1) 创建指针
8. Node* A;  //声明指向节点的指针 A
9. A = NULL; //最初列表为空，指针 A 不指向任何位置
12. //(2) 插入节点。用malloc函数创建内存块，参数是内存块所需字节数
13. Node* temp = (Node*)malloc(sizeof(Node));
14. //说明：malloc返回void指针，该指针为我们提供分配的内存块地址
15. //说明：我们把它保存在名为temp的变量里，最后需要类型转换(由于返回void指针)
18. //(4) 把数据写入该节点，并调整链接。
20. #if 0
21. (*temp).data = 2;
22. //说明：向 A 写入地址，以及调整新创建节点的链接字段。为此必须解引用指针(也就是刚创建的变量temp)。
23. //说明：变量前加"*"可解引用并可以修改地址的值(也就是内容)。
24. (*temp).link = NULL;
25. //说明：我们这个临时变量temp指向这个节点，此时这个节点是第一个也是最后一个节点，所以链接不是是NULL
27. #else
28. temp->data = 2;
29. temp->link = NULL;
30. #endif
32. A = temp;
33. //说明：把新创建节点的地址写入 A
34. //说明：temp事实用来暂时存储节点地址，一旦链接调整完成，temp就可用于其他目的
35.    

复制代码

（2）逻辑代码——遍历后再链表最后插入第1个节点

1. typedef struct Node {
2.     int data;      
3.     struct Node* link;  
4. } Node;
6. //(1) 创建指针
7. Node* A;  
8. A = NULL;
10. //(2) 构建第1个节点，并写入数据和地址
11. Node* temp = (Node*)malloc(sizeof(Node));
12. temp->data = 2;
13. temp->link = NULL;
15. //(3)把新节点的地址写入原本为NULL的此前尾节点的link
16. A = temp;
18. //(4)遍历节点地址后，插入新节点
19. Node* temp1 = A;
20. while(temp1->link != NULL){ //用最后一个节点地址为空，作为判断
21.      temp1 = temp1->link;
22. }
24. //(5)创建新节点，并在新节点内写入数据
25. Node* newtemp = (Node*)malloc(sizeof(Node));
26. newtemp->link = NULL;
27. newtemp->data = 3;
29. //(6)把新节点的地址写入原本为NULL的此前尾节点的link
30. temp1->link = newtemp;

复制代码

截图参考来自，很好的视频

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。