第 74 期(数据结构-链表)：什么是链表 #77

链表定义

链表是一种物理存储单元上非连续、非顺序的存储结构，由指针链接 n 个结点组成，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

结点： 数据元素的存储映像、映射。每个节点由数据域和指针域两部分组成

数据域： 存储元素数据，即当前节点的存储数据

指针域： 存储下一个节点的存储位置，即指向下一个节点的指针

可以把链表想象成自行车链条：结构为一节节相连，每个链节都有自己的零件（数据）并且链接下一个链节（指针）

链表的优点

数据元素可自由扩充；插入、删除动作高效，不需要像数组那样移动过多的元素。

链表种类

• 单向链表：或称线性链表，指每个结点只有一个指针域的链表，单向链表只有一个方向；
• 双向链表：指每个节点有两个指针域的链表，双向链表有两个方向，可以从头节点依次指向尾节点，又可反向从尾节点指向头节点；
• 循环链表：指首尾相接的链表，即链表的尾节点指向头结点。