双向链表相比单链表的优势

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
你可能会说，我刚讲到单链表的插入、删除操作的时间复杂度已经是 O(1) 了，双向链表还
能再怎么高效呢？其实说单链表插入、删除操作的时间复杂度为O(1)是不准确的，或者说是有先决条件的。

我们先来看删除操作。
在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：

1. 删除结点中“值等于某个给定值”的结点；
2. 删除给定指针指向的结点。

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从
头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后将其删除。
尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。

但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！
同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。

除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。