203707一、链表理论基础1.什么是链表链表是线性 表的链式存储结构。它与数组最大的不同在于链表使用任意的存储单元存放数据元素这些单元可以是连续的也可以是不连续的。因此为了找到每个元素的下一个元素每个数据元素除了存储自身信息外还必须存储一个指向其直接后继位置的指针。2.结点Node这两部分信息合在一起称为一个结点数据域存储数据元素本身的信息。指针域存储直接后继结点的存放位置即指针。3.单链表与双链表单链表每个结点只设置一个指向后继结点的指针。整个链表通过头指针head开始尾结点的指针指向空∧ 或 None。双链表每个结点设置两个指针分别指向前驱结点和后继结点方便双向遍历。4.结点引用方式在链表中我们不能像数组那样通过下标直接访问某个元素而是必须从表头开始沿着 next 指针逐个结点遍历。例如通过 L.head 得到第一个结点再通过 L.head.next 得到第二个结点依此类 推。