定义双向链表

双向链表只是在原来的单链表中加入了一个前驱指针，因此，在双链表中执行按值查找和循秩查找与单链表是相同的。但在插入和删除操作中和单链表有着较大的不同。此外双链表还能很方便的找到其前驱结点，因此，除了找到插入结点外，插入和删除结点的时间复杂度仅为\(O(1)\)。

typedef struct DNode {    ElemType data;  //数据域    struct DNode *pred, *succ;  //前驱和后继域}DNode, *DLinkList;

---

双向链表的尾插法初始化：

//尾插法void InitList(DLinkList &L, int n){    DNode *p, *q;    L = (DNode*)malloc(sizeof(DNode));    if(!L) exit(0);    L->succ = L->pred = NULL;    p = L;    for(int i = 1; i <= n; ++i) {        q = (DNode*)malloc(sizeof(DNode));        q->data = i;        if(!q) exit(0);        q->succ = NULL;        p->succ = q;        q->pred = p;        p = q;    }}

双向链表中的插入操作

在双向链表中第i个位置插入节点s的算法：

//在第i个位置之后插入新的元素bool InsertDNode(DLinkList &L, int i, int e){    int j = 1;    DNode *p, *q, *s;    p = L;    while(p && j < i) {        p = p->succ;        j++;    }    if(!p || j > i) return false;    s = (DNode*)malloc(sizeof(DNode));    s->data = e;    s->pred = p;  //第一步    s->succ = p->succ; //第二步    p->succ->pred = s; //第三步    p->succ = s;  //第四步}

上述的语句顺序不是唯一的，但也不是任意的，一二步必须在第四步之前，否则*p的后继结点的指针就丢掉了，导致插入失败。

---

双向链表的删除操作

删除双向链表中第i个位置的后继节点q的算法：只需要越过结点i处理i的前驱结点和后继节点即可。

bool DeleteDNode(DLinkList &L, int i, int &e){    int j = 1;    DNode *p, *q, *s;    p = L;    while(p && j <= i) {  //找到结点i所在位置        p = p->succ;        j++;    }    if(!p || j > i + 1) return false;    p->pred->succ = p->succ;    p->succ->pred = p->pred;    free(p);    return true;}

总结

双向链表相对于单链表来说，要更复杂一些，因为它多了前驱指针，所以在插入和删除操作时要格外小心，另外，由于它每个结点都要记录两份指针，所以略占空间，不过，由于它良好的对称性，使得对某个结点的前后结点的操作带来了方便，可以有效提高算法的时间性能，说白了就是用空间置换时间。