双链表的算法之插入节点

1.尾部插入和头部插入

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

struct node
{
    int data;           //有效数据
    struct node* pPrev; //前向指针，指向前一个节点
    struct node* pNext; //后向指针，指向后一个节点
};

struct node* create_node(int data)
{
    struct node* p = (struct node*)malloc(sizeof(struct node));
    if(NULL == p)
    {
        printf("create_node malloc failed\n");
        return NULL;
    }
    p->data = data;
    p->pPrev = NULL;
    p->pNext = NULL;

    return p;
}
//蒋新节点new插入到链表pH的尾部
void insert_tail(struct node* pH, struct node* new)
{
    //第一步：先走到链表的尾结点
    struct node* p = pH;
    while(NULL != p->pNext)
    {
        p = p->pNext;  //第一次循环走过了头结点
    }
    //循环结束后p就指向了原来的最后一个节点
    //第二步：将新节点插入到原来的尾结点的后面
    p->pNext = new;  //后向指针关联
    new->pPrev = p;   //前向指针关联
}
//将新节点new前插入链表pH中
void insert_head(struct node* pH, struct node* new)
{
    //新节点的next指针指向原来的第1个有效节点的地址
    new->pNext = pH->pNext;
    //原来第一个有效节点的prev指针指向新节点的地址
    if(NULL != pH->pNext) //只有头结点，没有第一个有效节点时，pH->pNext = NULL
        pH->pNext->pPrev = new;
    //第一步：头结点的next指针指向新节点的地址
    pH->pNext = new;
    //新节点的prev指针指向头结点的地址
    new->pPrev = pH;
    
    
}

int main()
{
    struct node* pHeader = create_node(0);  //头指针
    insert_head(pHeader, create_node(1));
    insert_head(pHeader, create_node(2));
    insert_head(pHeader, create_node(3));

    //遍历
    printf("node 1 data: %d\n", pHeader->pNext->data);
    printf("node 2 data: %d\n", pHeader->pNext->pNext->data);
    printf("node 3 data: %d\n", pHeader->pNext->pNext->pNext->data);

    struct node* p = pHeader->pNext->pNext->pNext; //p指向了最后一个节点
    printf("node 3 data: %d\n", p->data);
    printf("node 2 data: %d\n", p->pPrev->data);
    printf("node 1 data: %d\n", p->pPrev->pPrev->data);


    return 0;
}