链表是一种线性数据结构其中的每个元素都是一个节点对象各个节点通过“引用”相连接。引用记录了下一个节点的内存地址通过它可以从当前节点访问到下一个节点。链表的设计使得各个节点可以分散存储在内存各处它们的内存地址无须连续。由上图可知链表在逻辑上是相连的但是在物理空间上是分散的常见的链表类型包括三种。单向链表即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点将最后一个节点称为尾节点尾节点指向空None。环形链表如果我们令单向链表的尾节点指向头节点首尾相接则得到一个环形链表。在环形链表中任意节点都可以视作头节点。双向链表与单向链表相比双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点下一个节点和前驱节点上一个节点的引用指针。相较于单向链表双向链表更具灵活性可以朝两个方向遍历链表但相应地也需要占用更多的内存空间。