双向链表(Doubly Linked List)
介绍
双向链表是链表的一种变体,其中每个节点包含三个部分:数据域、前向指针和后向指针。前向指针指向前一个节点,后向指针指向后一个节点。这种结构使得链表可以从两个方向进行遍历,增加了灵活性。

与单向链表相比,双向链表支持双向遍历,并且在某些操作上更高效,例如删除给定节点或在特定节点前插入新节点。双向链表的头结点的前向指针和尾节点的后向指针通常指向null,表示链表的边界。
核心特性
- 双向遍历:可以从前向后或从后向前遍历链表
- 两个指针:每个节点有指向前一个和后一个节点的指针
- 动态大小:可以根据需要动态增长和缩小
- 非连续存储:节点在内存中分散存储,通过指针相连
基本操作
1. 访问元素
- 时间复杂度:O(n)
- 说明:必须从头节点或尾节点开始遍历直到找到目标节点
2. 插入操作
...