双向链表就是在单项链表的基础上增加了一个前向指针域。基本操作还是一样的，该双向链表是带有头节点的，最后一个节点的next指针域是为空的，不是指向首节点的。

双向链表的结构定义

typedef char datatype;
typedef struct node
{
    datatype data;
    struct node *prior, *next;
}linknode;
typedef linknode *linklist;

创建一个链表

linklist CreatDlist(void)
{
    char ch;
    linklist head;
    linknode *p, *h, *r;

    head = (linknode *)malloc(sizeof(linknode));
    head->next = NULL;
    h = head;
    r = head;
    while((ch = getchar()) != "
")
    {
        p = (linknode *)malloc(sizeof(linknode));
        p->data = ch;
        p->next = NULL;
        if(r == head)
        {
            r->next = p;
        }
        else
        {
            r->next = p;
            r->prior = h;
            h = h->next;
        }
        r = p;
    }

    return head;
}

找到链表中一个节点

linknode * GetNode(linklist head, int i)
{
    linknode *p = head;
    int j = 0;

    while(p && j<i)
    {
        p = p->next;
        j++;
    }

    return p;
}

插入一个节点

void InsetDlist(linklist head, datatype ch, int i)
{
    linknode *p = head->next, *t;
    int j = 0;

    while(p && j < i-1)
    {
        p = p->next;
        j++;
    }
    t = (linknode *)malloc(sizeof(linknode));
    t->data = ch;
    t->prior = p;
    t->next = p->next;
    p->next = t;
    t->next->prior = t;
}

删除一个节点

void DeleteDlist(linklist head, int i)
{
    linknode *p = head->next;
    int j = 0;

    while(p && j < i-1)
    {
        p = p->next;
        j++;
    }
    p->next->prior = p->prior;
    p->prior->next = p->next;
    puts("a");
    free(p);
}

显示整个双向链表

void ShowDlist(linklist head)
{
    linknode *p = head;

    while(p)
    {
        printf("%c", p->data);
        p = p->next;
    }
    putchar("
");
}

释放整个双向链表

void FreeDlist(linklist head)
{
    linknode *p;
    int i = 0;

    p = head;
    while(p)
    {
        free(p);
        head = head->next;
        p = head;
        i++;
    }
    printf("
the dlist free is ok.the node has %d.
", i);
}

双向链表的测试程序

#include <stdio.h>
#include <stdlib.h>

#include "dlist.h"

void show(linknode *p)
{
    printf("p->prior:%c
", p->prior->data);
    printf("p->data:%c
", p->data);
    printf("p->next:%c
", p->next->data);
}

int main(void)
{
    linklist head;
    //linknode *p;

    head = CreatDlist();
    ShowDlist(head->next);

    p = GetNode(head, 3);
    show(p);
    DeleteDlist(head, 3);
    p = GetNode(head, 3);
    show(p);

    InsetDlist(head, "x", 2);
    ShowDlist(head->next);
    FreeDlist(head);

    return 0;
}