数据词典：双链表（Double Linked List）

赵老师

单链表中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点，只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。

双链表在单链表的结点中增加了一个指向其前驱的prior指针，因此双链表中的按值查找按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为在“链”变化时也需要对prior指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入和删除操作的时间复杂度都是O(1)。

【出处】王道论坛.王道数据结构考研复习指导,电子工业出版社，2020年1月第1版。