3.2 链式表1. 单向链表1. 数组和链表各自的优缺点1. 数组空间连续访问元素方便元素必须有上限无法做到无限个元素插入删除效率低2. 链表空间不需要连续访问元素不太方便增大存储空间主要空间足够元素可以没有上限插入、删除效率高2. 单向链表结构此处将展开单向链表的具体结构说明2. 双向链表1. 双向链表结构双向链表Doubly Linked List是链表的一种与单向链表的主要区别在于每个节点包含两个指针一个指向后继节点next另一个指向前驱节点prev。双向链表的基本结构如下节点结构包含数据域data、前驱指针prev和后继指针next头节点第一个节点prev 指针为 null尾节点最后一个节点next 指针为 null2. 双向链表的优缺点优点可以从两个方向遍历链表查找效率更高删除节点时不需要查找前驱节点操作更方便在某些场景下如 LRU 缓存实现更简单缺点每个节点需要额外存储一个指针空间开销更大插入和删除操作需要维护两个指针代码更复杂3. 双向链表的基本操作插入操作在指定位置插入新节点需要更新前后节点的指针删除操作删除指定节点需要更新前后节点的指针遍历操作可以从头到尾或从尾到头遍历查找操作可以根据需要选择从头或从尾开始查找