C语言线性表之双链表详解

前言

本教程将详细介绍C语言中双链表的实现方法以及相关操作，适合有一定C语言基础的读者。

双链表定义

双链表是一种常见的数据结构，与单链表不同，双链表中每个节点不仅有指向后续节点的指针，还有指向前续节点的指针，即“双向链表”。

双链表的节点结构体可以定义如下：

typedef struct double_node{
    int data;
    struct double_node *prev;
    struct double_node *next;
}DoubleNode;

其中，data表示节点中存储的数据，prev指向前续节点，next指向后续节点。

双链表操作

初始化双链表

在使用双链表前，需要先初始化一个空表头。代码如下：

DoubleNode* init_double_list(){
    DoubleNode* head=(DoubleNode*)malloc(sizeof(DoubleNode));
    head->next=NULL;
    head->prev=NULL;
    return head;
}

在双链表中插入节点

有两种在双链表中插入节点的方法：在表头插入节点和在表尾插入节点。

1.在表头插入节点

在双链表表头插入节点的代码如下：

void insert_head(DoubleNode* list,int data){
    DoubleNode* new_node=(DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->data=data;
    new_node->next=list->next;
    new_node->prev=list;
    list->next=new_node;
    if(new_node->next!=NULL){
        new_node->next->prev=new_node;
    }
}

2.在表尾插入节点

在双链表表尾插入节点的代码如下：

void insert_tail(DoubleNode* list,int data){
    DoubleNode* new_node=(DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->data=data;
    new_node->prev=NULL;
    new_node->next=list;
    while(list->next!=NULL){
        list=list->next;
    }
    list->next=new_node;
    new_node->prev=list;
}

在双链表中删除节点

有两种在双链表中删除节点的方法：删除表头节点和删除表尾节点。

1.删除表头节点

在双链表表头删除节点的代码如下：

void delete_head(DoubleNode* list){
    if(list->next!=NULL){
        DoubleNode* temp=list->next;
        list->next=temp->next;
        if(temp->next!=NULL){
            temp->next->prev=list;
        }
        free(temp);
    }
}

2.删除表尾节点

在双链表表尾删除节点的代码如下：

void delete_tail(DoubleNode* list){
    if(list->next!=NULL){
        while(list->next->next!=NULL){
            list=list->next;
        }
        DoubleNode* temp=list->next;
        list->next=NULL;
        free(temp);
    }
}

示例

示例1

以下代码演示了双链表的初始化、在表头插入节点和在表尾插入节点操作：

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

typedef struct double_node{
    int data;
    struct double_node *prev;
    struct double_node *next;
}DoubleNode;

DoubleNode* init_double_list(){
    DoubleNode* head=(DoubleNode*)malloc(sizeof(DoubleNode));
    head->next=NULL;
    head->prev=NULL;
    return head;
}

void insert_head(DoubleNode* list,int data){
    DoubleNode* new_node=(DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->data=data;
    new_node->next=list->next;
    new_node->prev=list;
    list->next=new_node;
    if(new_node->next!=NULL){
        new_node->next->prev=new_node;
    }
}

void insert_tail(DoubleNode* list,int data){
    DoubleNode* new_node=(DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->data=data;
    new_node->prev=NULL;
    new_node->next=list;
    while(list->next!=NULL){
        list=list->next;
    }
    list->next=new_node;
    new_node->prev=list;
}

void print_double_list(DoubleNode* list){
    while(list->next!=NULL){
        printf("%d->",list->next->data);
        list=list->next;
    }
    printf("NULL\n");
}

int main(){
    DoubleNode* list=init_double_list();
    insert_head(list,1);
    insert_head(list,2);
    insert_head(list,3);
    insert_tail(list,4);
    insert_tail(list,5);
    insert_tail(list,6);
    print_double_list(list);
    return 0;
}

输出结果如下：

3->2->1->4->5->6->NULL

示例2

以下代码演示了双链表的在表头删除节点和在表尾删除节点操作：

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

typedef struct double_node{
    int data;
    struct double_node *prev;
    struct double_node *next;
}DoubleNode;

DoubleNode* init_double_list(){
    DoubleNode* head=(DoubleNode*)malloc(sizeof(DoubleNode));
    head->next=NULL;
    head->prev=NULL;
    return head;
}

void insert_head(DoubleNode* list,int data){
    DoubleNode* new_node=(DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->data=data;
    new_node->next=list->next;
    new_node->prev=list;
    list->next=new_node;
    if(new_node->next!=NULL){
        new_node->next->prev=new_node;
    }
}

void insert_tail(DoubleNode* list,int data){
    DoubleNode* new_node=(DoubleNode*)malloc(sizeof(DoubleNode));
    new_node->data=data;
    new_node->prev=NULL;
    new_node->next=list;
    while(list->next!=NULL){
        list=list->next;
    }
    list->next=new_node;
    new_node->prev=list;
}

void delete_head(DoubleNode* list){
    if(list->next!=NULL){
        DoubleNode* temp=list->next;
        list->next=temp->next;
        if(temp->next!=NULL){
            temp->next->prev=list;
        }
        free(temp);
    }
}

void delete_tail(DoubleNode* list){
    if(list->next!=NULL){
        while(list->next->next!=NULL){
            list=list->next;
        }
        DoubleNode* temp=list->next;
        list->next=NULL;
        free(temp);
    }
}

void print_double_list(DoubleNode* list){
    while(list->next!=NULL){
        printf("%d->",list->next->data);
        list=list->next;
    }
    printf("NULL\n");
}

int main(){
    DoubleNode* list=init_double_list();
    insert_head(list,1);
    insert_head(list,2);
    insert_head(list,3);
    insert_tail(list,4);
    insert_tail(list,5);
    insert_tail(list,6);
    print_double_list(list);
    delete_head(list);
    delete_tail(list);
    print_double_list(list);
    return 0;
}

输出结果如下：

3->2->1->4->5->6->NULL
2->1->4->5->NULL

结论

本教程详细介绍了双链表的定义以及相关操作，包括初始化、插入节点、删除节点等。通过示例演示可以更好地理解双链表的相关操作。如果读者已经掌握并理解了本教程的内容，可以尝试在实际项目中应用了解到的知识。