头插法建立双向链表_双向链表头插法

单链表只能向后访问其他节点的数据，若需要寻找某节点前面节点的数据，则需要从表头开始，重新进行遍历，效率不高，为了克服单链表单向性的缺点，可以利用双向链表

双向链表有两个指针域，一个指向直接后继，一个指向直接前驱，头插法建立双链表的方法如下

结构体定义如下

typedef struct DuLNode{
    int data;
    struct DuLNode *prior, *next;
}DuLNode, *DuLNode;

prior代表前驱，next代表后继

初始化头节点head,前驱和后继均指向空

head->next = head->prior = NULL;

图形表示如下图

对于头插法来说，插入第一个元素和插入第一个元素后面的元素有区别，因为第一个元素不需要考虑该插入元素同后面元素的节点连接关系。

插入的节点为p

首先执行代码

head->next = p;

建立head节点与p节点的后继关系（head的后继是p,head节点的下一个是p）

图形化表示为

接着执行代码

p->prior = head;

建立head节点与p节点的前驱关系（p节点的前驱是head,p节点的前一个是head）

图形化表示为

此时就将第一个节点插入到了头节点后面，并且建立了前驱和后继的关系

下面考虑插入第二个节点的情况（第三个，第四个....节点的插入情况同第二个节点相同）

插入的节点名称是P

首先执行代码

p->next = head->next;

head->next指向的是头节点的下一个节点，由于要在头节点和头节点的下一个节点之间插入节点，所以执行该语句将节点p指向的头节点的下一个节点

接着执行

head->next->prior = p;

head->next表示的是头节点的下一个节点，将该节点的前驱定义为p，建立他们之间的前驱关系

执行完毕后图像化表示为

此时，节点P同head的下一个节点A1的前驱后继关系建立完毕，接着要建立head同p的前驱后继关系

代码为

head->next = p;
p->prior = head;

图形化表示

至此，上述操作建立了新的前驱和后继关系，实现了头节点链表的建立，完整代码如下

#include <stdio.h>
#include <stdlib.h>
 
typedef struct DuLNode{
    int data;
    struct DuLNode *prior, *next;
}DuLNode, *DuLinklist;
 
 
//尾插法创建双向链表
void CreateTailList(DuLinklist *L, int n){//创建大小长度为n的链表
    DuLinklist p, r;
    (*L) = (DuLNode *)malloc(sizeof(DuLNode));
    (*L)->next = NULL;
    (*L)->prior = NULL;
    r = (*L);
    int i = 0;
    for(i = 0; i < n; i ++){
        p = (DuLNode *)malloc(sizeof(DuLNode));
        p->data = i;
        r->next = p;
        p->prior = r;
        r = p;
 
 
    }
    r->next = NULL;
}
//头插法建立双向链表
void CreteHeadList(DuLinklist *L, int n){
    DuLinklist p, r;
    (*L) = (DuLNode *)malloc(sizeof(DuLNode));
    (*L)->next = NULL;
    (*L)->prior = NULL;
    r = (*L);
    int i = 0;
    for(i = 0; i < n; i ++){
        p = (DuLNode *)malloc(sizeof(DuLNode));
        p->data = i;
        if(r->next == NULL){//插入第一个节点时与其他方法不一样
            r->next = p;
            p->prior = r;
            p->next = NULL;
        }
        else{
            p->next = r->next;
            r->next->prior = p;
            r->next = p;
            p->prior = r;
        }
    }
}
void TraverseList(DuLinklist *L){
    DuLinklist p;
    p = (*L);
    while(p->next != NULL){
        printf("%d\n", p->next->data);
        p = p->next;
    }
}
int main()
{
 
    DuLinklist La;
    CreteHeadList(&La, 5);
    TraverseList(&La);
    return 0;
}