【数据结构】线性表之双向链表

双向链表(double linked list)定义

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针。所以在双向链表中的结点都有两个指针域：一个指向直接后继，一个指向直接前驱。

线性表的双向链表存储结构代码实现

typedef struct DulNode{
    
    ElemType data;
    struct DulNode *prior;  /* 直接前驱指针 */
    struct DulNode *next;   /* 直接后继指针 */
    
}DulNode, *DuLinkList;

循环双向链表图示

• 双向链表的循环带头结点的空链表：

  
  双向链表的循环带头结点的空链表

• 非空的循环的带头结点的双向链表：

  
  非空的循环的带头结点的双向链表

特点

• 对于链表中的某个结点p，它的后继的前驱是它自己，同样，它的前驱的后继也是它自己
  p->next->prior = p; p->prior->next = p;

---

双向链表的操作

双向链表是单链表扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength,查找元素的GetElem,获得元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可。

插入操作

插入操作并不复杂，但是顺序很重要，一定不能写反。

假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间。

双向链表的插入操作图解
核心代码：

    s->prior = p;          /* 把 p 赋值给 s 的前驱 */
    s->next = p->next;     /* 把 p->next 赋值给 s 的后继 */
    p->next->prior = s;    /* 把 s 赋值给 p->next 的前驱 */
    p->next = s;           /* 把 s 赋值给 p 的后继 */

注意:关键在于他们的顺序，有第二步和第三部都用到了p->next。如果第四步先执行，则会使得p->next提前变成了s,使得插入的工作完不成。

删除操作

删除操作比插入操作更加简单。如果要删除p，只需要两步。

双向链表的删除操作图解
核心代码

    p->prior->next = p->next;    /* 把 p->next 赋值给 p->prior 的后继 */
    p->next->prior = p->prior;   /* 把 p->prior 赋值给 p->next 的前驱 */
    free(p);