【数据结构】带头+双向+循环链表(DList)(增、删、查、改)详解

简介: 【数据结构】带头+双向+循环链表(DList)(增、删、查、改)详解

一、带头双向循环链表的定义和结构

1、定义

带头双向循环链表,有一个数据域两个指针域。一个是前驱指针,指向其前一个节点;一个是后继指针,指向其后一个节点。

// 定义双向链表的节点
typedef struct ListNode
{
  LTDataType data; // 数据域
  struct ListNode* prev; // 前驱指针
  struct ListNode* next; // 后继指针
}ListNode;

2、结构

带头双向循环链表:在所有的链表当中 结构最复杂,一般用在 单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多 优势,实现反而简单了。


二、带头双向循环链表接口的实现

1、创建文件

  • test.c(主函数、测试顺序表各个接口功能)
  • List.c(带头双向循环链表接口函数的实现)
  • List.h(带头双向循环链表的类型定义、接口函数声明、引用的头文件)


2、List.h 头文件代码

// List.h
// 带头+双向+循环链表增删查改实现
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int LTDataType;
 
// 定义双向链表的节点
typedef struct ListNode
{
  LTDataType data; // 数据域
  struct ListNode* prev; // 前驱指针
  struct ListNode* next; // 后继指针
}ListNode;
 
// 动态申请一个新节点
ListNode* BuyListNode(LTDataType x);
// 创建返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 双向链表的判空
bool ListEmpty(ListNode* phead);
// 获取双向链表的元素个数
size_t ListSize(ListNode* phead);

三、在 List.c 上是实现各个接口函数

1、动态申请一个新结点

// 动态申请一个新节点
ListNode* BuyListNode(LTDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  newnode->data = x;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}

2、创建返回链表的头结点(初始化头结点)

// 创建返回链表的头结点
ListNode* ListCreate()
{
  ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); // 哨兵位头结点
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

也可以用下面这个函数(道理一样):

// 初始化链表
void ListInit(ListNode** pphead)
{
  *pphead = BuyListNode(-1); // 动态申请一个头节点
  (*pphead)->prev = *pphead; // 前驱指针指向自己
  (*pphead)->next = *pphead; // 后继指针指向自己
}

头指针初始指向 NULL,初始化链表时,需要改变头指针的指向,使其指向头节点,所以这里需要传二级指针。


初始化带头双向循环链表,首先动态申请一个头结点头结点的前驱和后继指针都指向自己,形成一个循环


3、双向链表的销毁

// 双向链表的销毁
void ListDestroy(ListNode** pphead)
{
  assert(pphead);
  assert(*pphead);
 
  ListNode* cur = (*pphead)->next;
  while (cur != *pphead)
  {
    ListNode* next = cur->next; // 记录cur的直接后继节点
    free(cur);
    cur = next;
  }
  free(*pphead); // 释放头节点
  *pphead = NULL; // 置空头指针
}

销毁链表,最后要将头指针 plist 置空,所以用了二级指针来接收。这里也可以用一级指针,但要在函数外面置空 plist 。

一级指针写法:

void ListDestroy(ListNode* phead)
{
  assert(phead);
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    ListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
  phead = NULL;
}

4、双向链表的打印

// 打印双向链表
void ListPrint(ListNode* phead)
{
  assert(phead);
 
  ListNode* cur = phead->next; // 记录第一个节点
  printf("head <-> ");
  while (cur != phead)
  {
    printf("%d <-> ", cur->data);
    cur = cur->next;
  }
  printf("head\n");
}

5、双向链表的尾插

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead); // 头指针不能为空
 
  /* ListNode* newnode = BuyListNode(x); // 动态申请一个节点
  ListNode* tail = phead->prev; // 记录尾节点
  tail->next = newnode; // 尾节点的后继指针指向新节点
  newnode->prev = tail; //2、新节点的前驱指针指向尾节点
  newnode->next = phead; // 新节点的后继指针指向头节点
  phead->prev = newnode; // 头节点的前驱指针指向新节点 */
 
    ListInsert(phead, x);
}


6、双向链表的尾删

// 双向链表的尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除
 
  /* ListNode* tail = phead->prev; // 记录尾节点
  ListNode* tailPrev = tail->prev; // 记录尾节点的直接前驱
  
  tailPrev->next = phead; // 尾节点的前驱节点的next指针指向头节点
  phead->prev = tailPrev; // 头节点的prev指针指向尾节点的前驱节点
  free(tail); // 释放尾节点 */
 
    ListErase(pHead->prev);
}


7、双向链表的头插

// 双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);
 
  /* ListNode* newnode = BuyListNode(x); // 申请新节点
  ListNode* pheadNext = phead->next; // 记录第一个节点
  
  // 头节点和新节点建立链接
  phead->next = newnode;
  newnode->prev = phead;
  // 新节点和第一个节点建立链接
  newnode->next = pheadNext;
  pheadNext->prev = newnode; */
 
    ListInsert(phead->next, x);
}


8、双向链表的头删

// 双向链表的头删
void ListPopFront(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除
 
  /* ListNode* pheadNext = phead->next; // 记录第一个节点
  // 头节点和第一个节点的后继节点建立链接
  phead->next = pheadNext->next;
  pheadNext->next->prev = phead;
    free(pheadNext); // 头删 */
 
    ListErase(phead->next);
}


9、查找双向链表中的元素

// 在双向链表中查找元素,并返回该元素的地址
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);
 
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;  //找到了 返回该元素的地址
    }
    cur = cur->next;
  }
  return NULL;  //没找到 返回NULL
}

10、在指定pos位置之前插入元素

// 在指定pos位置之前插入元素
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
 
  ListNode* newnode = BuyListNode(x); // 申请一个节点
  ListNode* posPrev = pos->prev; // 记录pos的直接前驱
 
  // pos的直接前驱和新节点建立链接
  posPrev->next = newnode;
  newnode->prev = posPrev;
 
  // 新节点和pos建立链接
  newnode->next = pos;
  pos->prev = newnode;
}

实现了该函数后,可以尝试改进头插函数(pos相当于链表的第一个节点)和尾插函数(pos相当于链表的头节点),这样写起来更简便


11、删除指定pos位置的元素

// 删除指定pos位置的元素
void ListErase(ListNode* pos)
{
  assert(pos);
 
  ListNode* posPrev = pos->prev; // 记录pos的直接前驱
  ListNode* posNext = pos->next; // 记录pos的直接后继
 
  // pos的直接前驱和直接后继建立链接
  posPrev->next = posNext;
  posNext->prev = posPrev;
  
  free(pos); // 释放pos位置的元素
    //pos = NULL;
}

实现了该函数后,可以尝试改进函数(pos相当于链表的第一个节点)和尾删函数(pos相当于链表的最后一个节点),这样写起来更简便


12、双向链表的判空

// 双向链表的判空
bool ListEmpty(ListNode* phead)
{ 
  assert(phead);
  return phead->next == phead; //为空 返回ture 否则返回false
}

13、获取双向链表的元素个数

// 获取双向链表的元素个数
size_t ListSize(ListNode* phead)
{
  assert(phead);
 
  size_t size = 0;
  ListNode* cur = phead->next; // 记录第一个节点
  while (cur != phead)
  {
    size++;
    cur = cur->next;
  }
  return size;
}

四、代码整合

// List.c
#include "List.h"
 
// 动态申请一个新节点
ListNode* BuyListNode(LTDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  newnode->data = x;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}
 
// 创建返回链表的头结点
ListNode* ListCreate()
{
  ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); // 哨兵位头结点
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
 
// 双向链表的销毁
void ListDestroy(ListNode** pphead)
{
  assert(pphead);
  assert(*pphead);
 
  ListNode* cur = (*pphead)->next;
  while (cur != *pphead)
  {
    ListNode* next = cur->next; // 记录cur的直接后继节点
    free(cur);
    cur = next;
  }
  free(*pphead); // 释放头节点
  *pphead = NULL; // 置空头指针
}
 
// 打印双向链表
void ListPrint(ListNode* phead)
{
  assert(phead);
 
  ListNode* cur = phead->next; // 记录第一个节点
  printf("head <-> ");
  while (cur != phead)
  {
    printf("%d <-> ", cur->data);
    cur = cur->next;
  }
  printf("head\n");
}
 
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead); // 头指针不能为空
    ListInsert(phead, x);
}
 
// 双向链表的尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除
    ListErase(pHead->prev);
}
 
// 双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);
    ListInsert(phead->next, x);
}
 
// 双向链表的头删
void ListPopFront(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除
    ListErase(phead->next);
}
 
// 在双向链表中查找元素,并返回该元素的地址
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);
 
  ListNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;  //找到了 返回该元素的地址
    }
    cur = cur->next;
  }
  return NULL;  //没找到 返回NULL
}
 
// 在指定pos位置之前插入元素
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
 
  ListNode* newnode = BuyListNode(x); // 申请一个节点
  ListNode* posPrev = pos->prev; // 记录pos的直接前驱
 
  // pos的直接前驱和新节点建立链接
  posPrev->next = newnode;
  newnode->prev = posPrev;
 
  // 新节点和pos建立链接
  newnode->next = pos;
  pos->prev = newnode;
}
 
// 删除指定pos位置的元素
void ListErase(ListNode* pos)
{
  assert(pos);
 
  ListNode* posPrev = pos->prev; // 记录pos的直接前驱
  ListNode* posNext = pos->next; // 记录pos的直接后继
 
  // pos的直接前驱和直接后继建立链接
  posPrev->next = posNext;
  posNext->prev = posPrev;
  
  free(pos); // 释放pos位置的元素
    //pos = NULL;
}
 
// 双向链表的判空
bool ListEmpty(ListNode* phead)
{ 
  assert(phead);
  return phead->next == phead; //为空 返回ture 否则返回false
}
 
// 获取双向链表的元素个数
size_t ListSize(ListNode* phead)
{
  assert(phead);
 
  size_t size = 0;
  ListNode* cur = phead->next; // 记录第一个节点
  while (cur != phead)
  {
    size++;
    cur = cur->next;
  }
  return size;
}


相关文章
|
14天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
14 0
|
14天前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
19 0
|
14天前
|
算法
数据结构和算法学习记录——习题-移除链表元素
数据结构和算法学习记录——习题-移除链表元素
11 0
|
3天前
|
存储 算法 Linux
【内核链表】数据结构——深入理解内核链表的概念和操作&笔记
【内核链表】数据结构——深入理解内核链表的概念和操作&笔记
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
|
5天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
5天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
8 0
|
9天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
10 0
|
9天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
8 0
|
9天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
7 0

热门文章

最新文章