数据结构初阶之双向链表的介绍与双向链表的实现

一、概念与结构

带头双向循环链表

next ：指向下一个结点（后继结点）

prev ：指向前一个结点（前驱结点）

二、实现双向链表

项目创建的时候，要创建一个头文件（.h）List.h ，两个源文件（.c）List.c ，test.c 。List.h 用于定义结构体和声明函数；List.c 用于实现函数；test.c 用于测试函数，每实现一个函数要进行相应的测试。编写代码过程中要勤测试，避免写出大量代码后再测试，如果出现问题，问题无从定位。

1、List.h

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

//定义双向链表的结构
typedef int DataType;
typedef struct ListNode
{
   DataType data;
   struct ListNode* next;
   struct ListNode* prev;
}ListNode;

//申请一个新节点
ListNode* buy_Node(DataType x);

//双向链表的初始化，申请一个头结点
ListNode* init_List(void);

//打印双向链表
void print_List(ListNode* head);

//尾插一个结点
void pushback_Node(ListNode* head, DataType x);

//头插一个结点
void pushfront_Node(ListNode* head, DataType x);

//判断链表是否为空链表
bool empty_List(ListNode* head);

//尾删一个结点
void popback_Node(ListNode* head);

//头删一个结点
void popfront_Node(ListNode* head);

//查找指定结点
ListNode* find_Node(ListNode* head, DataType x);

//在 pos 位置之后插入一个结点
void insert_Node(ListNode* pos, DataType x);

//删除指定 pos 位置的结点
void erase_Node(ListNode* pos);

//销毁双向链表
void destory_List(ListNode* head);

2、List.c

#include"List.h"

//申请一个新节点
ListNode* buy_Node(DataType x)
{
   ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
   if (!newnode)
   {
       perror("malloc fail!");
       exit(1);
   }
   newnode->data = x;
   newnode->next = newnode->prev = newnode;
   return newnode;
}

//双向链表的初始化，申请一个头结点
ListNode* init_List(void)
{
ListNode* plist = buy_Node(-1);
return plist;
}

//打印双向链表
void print_List(ListNode* head)
{
   ListNode* pcur = head->next;
   while (pcur != head)
   {
       printf("%d -> ", pcur->data);
       pcur = pcur->next;
   }
   printf("\n");
}

//判断链表是否为空链表
bool empty_List(ListNode* head)
{
assert(head);
return head->next != head;
}

//尾插一个结点
void pushback_Node(ListNode* head, DataType x)
{
   assert(head);
   ListNode* newnode = buy_Node(x);
   newnode->next = head;
   newnode->prev = head->prev;
   head->prev->next = newnode;
   head->prev = newnode;
}

//头插一个结点
void pushfront_Node(ListNode* head, DataType x)
{
   assert(head);
   ListNode* newnode = buy_Node(x);
   newnode->next = head->next;
   newnode->prev = head;
   head->next->prev = newnode;
   head->next = newnode;
}

//尾删一个结点
void popback_Node(ListNode* head)
{
   assert(empty_List(head));
   ListNode* del = head->prev;
   head->prev = del->prev;
   del->prev->next = head;
   free(del);
   del = NULL;
}
//头删一个结点
void popfront_Node(ListNode* head)
{
   assert(empty_List(head));
   ListNode* del = head->next;
   del->next->prev = head;
   head->next = del->next;
   free(del);
   del = NULL;
}

//查找指定结点
ListNode* find_Node(ListNode* head, DataType x)
{
   assert(head);
   ListNode* pcur = head->next;
   while (pcur != head)
   {
       if (pcur->data == x)
           return pcur;
       pcur = pcur->next;
   }
   return NULL;
}

//在 pos 位置之后插入一个结点
void insert_Node(ListNode* pos, DataType x)
{
   assert(pos);
   ListNode* newnode = buy_Node(x);
   newnode->next = pos->next;
   newnode->prev = pos;
   pos->next->prev = newnode;
   pos->next = newnode;
}

//删除指定 pos 位置的结点
void erase_Node(ListNode* pos)
{
   assert(pos);
   pos->next->prev = pos->prev;
   pos->prev->next = pos->next;
   free(pos);
   pos = NULL;
}

//销毁双向链表
void destory_List(ListNode** head)
{
   ListNode* pcur = (*head)->next;
   while (pcur != *head)
   {
       ListNode* next = pcur->next;
       free(pcur);
       pcur = next;
   }
   free(*head);
   *head = NULL;
}