1.链表基础概念本质物理上不连续但是逻辑上连续的线性数据结构1.如何让两个不连续的内存空间存在逻辑上的联系让每个空间分成两个存储空间数据域指针域区域一存放数据区域二存放下一块内存地址空间的地址链表的重要特性1.链表的最后一个节点中的指针域总是存放NULL2.分类2.1单向链表和双向链表单向链表节点只有一个指针域指向下一个节点优点简单易理解缺点只能从前往后查找数据双向链表节点中有一个数据域但是有两个指针域一个指针域指向下一个节点另一个指针域指向上一个节点优点节点的查找与增删非常灵活缺点实现起来稍微复杂增加存储负担多了一个指针域2.2循环链表和非循环链表非循环链表单向指针域总是指向下一个节点最后一个节点总是指向空表示结束单向非循环链表双向头节点的prev指向空最后一个节点的next指向空双向非循环链表循环链表单向末尾节点的next总是指向头节点单向循环链表双向末尾节点的next总是指向头节点头节点的prev总是指向末尾节点双向循环链表2.3带头链表和不带头链表带头链表头节点中不存放数据单纯当作链表起始点存在不带头链表头节点中也存放数据并没有固定的节点