链表（1）----概念
定义：链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。
特点： 链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：
一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域
链表由一个个节点构成，每个节点一般采用结构体的形式组织，例如：
typedef struct student｛ int num； char name[20]； struct student *next； }STU;
链表节点分为两个域
数据域：存放各种实际的数据，如：num、score等
指针域：存放下一节点的首地址，如：next等.
链表的操作:
链表最大的作用是通过节点把离散的数据链接在一起，组成一个表，这大概就是链表 的字面解释了吧。 链表常规的操作就是节点的插入和删除，为了顺利的插入，通常一条链 表我们会人为地规定一个根节点，这个根节点称为生产者。通常根节点还会有一个节点计 数器，用于统计整条链表的节点个数，具体见图3中的 root_node。
双向链表
双向链表与单向链表的区别就是节点中有两个节点指针，分别指向前后两个节点，其 它完全一样。有关双向链表的文字描述参考单向链表小节即可，有关双向链表的示意图具体见图4
链表与数组的对比
在很多公司的嵌入式面试中，通常会问到链表和数组的区别。在 C 语言中，链表与数 组确实很像，两者的示意图具体见图5，这里以双向链表为例。
链表是通过节点把离散的数据链接成一个表，通过对节点的插入和删除操作从而实现 对数据的存取。而数组是通过开辟一段连续的内存来存储数据，这是数组和链表最大的区 别。数组的每个成员对应链表的节点，成员和节点的数据类型可以是标准的 C 类型或者是 用户自定义的结构体。数组有起始地址和结束地址，而链表是一个圈，没有头和尾之分， 但是为了方便节点的插入和删除操作会人为的规定一个根节点。
投递小米集团等公司9个岗位 >
查看18道真题和解析