数据结构: 线性表(带头双向循环链表实现)

这篇具有很好参考价值的文章主要介绍了数据结构: 线性表(带头双向循环链表实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


之前一章学习了单链表的相关操作, 但是单链表的限制却很多, 比如不能倒序扫描链表, 解决方法是在数据结构上附加一个域, 使它包含指向前一个单元的指针即可.

那么怎么定义数据结构呢? 首先我们先了解以下链表的分类

1. 链表的分类

链表的结构非常多样, 以下情况组合起来就有 8 中链表结构

  • 单向或者双向
    数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • 带头或者不带头
    数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • 循环或者非循环
    数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表


虽然有这么多的链表的结构, 但是我们实际上最常用的还是两种结构:

数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

无头单向非循环链表

结构简单,一般不会单独用来存放数据.实际上更多是作为其他数据结构的子结构, 如哈希桶, 图的邻接表等等. 另外这种结构在笔试面试中出现很多

带头双向循环链表

结构最复杂, 一般用于单独存储数据.实际上使用的链表数据结构, 都是带头双向循环链表. 虽然结构复杂, 但是实现相关功能比较简单.

严格来说只用实现 InsertErase 两个功能, 就可以实现 “二十分钟” 写完一个链表的任务.

2. 带头双向循环链表

2.1 带头双向循环链表的定义

typedef int LTDataType;     //LTDataType = int
typedef struct ListNode
{
  LTDataType data;          //数据域
  struct ListNode* prev;    //指向前一个结点
  struct ListNode* next;    //指向后一个结点
}ListNode;  //重命名为 ListNode
  1. 相比较单链表的数据结构, 只需要多一个域用来指向前面一个结点就可以了.
  2. 这里使用ListNode来命名这个数据结构, 方便后续学习 STL 进行知识迁移

2.2 接口函数

// 创建并返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestroy(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos);

3. 接口函数的实现

因为有虚拟结点的存在, 所以除了创建头结点的函数, 其余接口函数都不会修改结构体指针, 只是修改结构体.

为了统一接口形式, 统一使用一级指针作为函数的形参类型. 需要修改头结点的函数接口, 直接用返回值的方法达到修改头结点指针的目的.

3.1 创建并返回链表的头结点 (ListCreate)

数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

创建链表即为创建头结点, 它是一个虚拟结点(dummy node), 实际的值没有意义.它的两个指针都指向自己.

  • ListList.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* ListCreate();

修改头结点指针, 使用返回值接受头结点的指针

  • ListList.c
// 创建返回链表的头结点
ListNode* ListCreate()
{
  // 动态开辟空间创建头结点, 如果开辟失败直接结束程序
  ListNode* head = BuyListNode(0);
  
  // 处理链表数据, 数据域随机值, 两个指针指向自己
  head->next = head;
  head->prev = head;

  return head;
}
  1. 这里的 BuyListNode() 是一个我自己定义的静态函数, 方便后续复用. 函数的功能是用来从堆中申请空间用来创建一个新结点.
// 创建一个新结点
static ListNode* BuyListNode(LTDataType x)
{
  ListNode* newNode = (ListNode*)malloc(sizeof(struct ListNode));

  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }

  newNode->data = x;
  newNode->next = NULL;
  newNode->prev = NULL;

  return newNode;
}
  1. 创建头结点后, 使头结点指向自己
  • test.c
void LinkListTest1()
{
  ListNode* head = ListCreate();

  free(head);
}

测试调试结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

头结点创建成功, 并且头结点两个指针都指向了自己

3.2 双向链表打印 (ListPrint)

从第一个结点开始遍历链表每个结点, 并且将结点的数据域打印出来, 直到遇到头结点结束
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • ListList.h
void ListPrint(ListNode* phead);
  • ListList.c
// 双向链表打印
void ListPrint(ListNode* phead)
{
  assert(phead);  //确保头结点存在

  printf("head <=> ");

  ListNode* cur = phead->next;  //从第一个结点开始遍历, 直到遇到头结点结束
  while (cur != phead)
  {
    printf("%d <=> ", cur->data);
    cur = cur->next;
  }

  printf("\n");
}
  1. 确保头结点存在
  1. cur第一次定位到头结点后面一个结点, 即第一个有效结点
  1. 顺序遍历并且打印
  • test.c

后续调试其他函数功能都会使用到 ListPrint 函数, 这里就先不调试了.

3.3 双向链表尾插 (ListPushBack)

先找到链表尾结点的位置, 在尾结点和头结点之间插入一个新结点

数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • ListList.h
void ListPushBack(ListNode* phead, LTDataType x);
  • ListList.c
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保头结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点 
  ListNode* tail = phead->prev;       //找到尾结点
  
  //更改链接关系
  tail->next = newNode;
  newNode->prev = tail;
  phead->prev = newNode;
  newNode->next = phead;

}
  1. 确保头结点存在
  1. 更改链接关系, 需要修改一共四根指针的指向关系
  • test.c
void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);
}

测试结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

3.4 双向链表尾删 (ListPopBack)

找到新的尾结点位置, 更改链接关系后将原尾结点删除
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • ListList.h
void ListPopBack(ListNode* phead);
  • ListList.c
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);                    //确保头结点存在
  assert(phead->next != phead);     //确保有结点可删

  ListNode* tail = phead->prev;     //找到要删除的尾结点
  ListNode* tailPrev = tail->prev;  //找到新的尾结点

  //更改链接关系
  tailPrev->next = phead;
  phead->prev = tailPrev;

  free(tail); //释放空间
}
  • test.c
void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPopBack(head);
  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPrint(head);
  
  ListDestroy(head);
}

测试结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

3.5 双链表头插 (ListPushFront)

找到原第一个有效节点, 在头结点和这个结点之间插入一个新结点
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • ListList.h
void ListPushFront(ListNode* phead, LTDataType x);
  • ListList.c
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保头结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* first = phead->next;      //找到原来的第一个结点

  //更新链接关系
  phead->next = newNode;
  newNode->prev = phead;
  newNode->next = first;
  first->prev = newNode;
}
  1. 确保头结点存在
  1. 在头结点和第一个有效结点之间插入新结点
  • test.c
void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);
}

测试运行结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

3.6 双链表头删 (ListPopFront)

先找到第一个和第二个有效结点, 更新头结点和第二个有效结点之间的链接关系后, 释放第一个结点的空间.
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • ListList.h
void ListPopFront(ListNode* phead);
  • ListList.c
// 双向链表头删
void ListPopFront(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在
  assert(phead->next != phead); //确保链表不为空

  ListNode* first = phead->next;  //找到头结点位置
  ListNode* second = first->next; //找到头结点后一个结点的位置

  //更新链接关系
  phead->next = second;
  second->prev = phead;

  free(first); //释放空间
}
  • test.c
void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);

  ListPrint(head);
  
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPrint(head);

  ListDestroy(head);
}

测试结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

3.7 双链表查找 (ListFind)

从第一个有效结点开始向后遍历链表, 判断是否有想要查找的数据, 直到遇到头结点. 未查找到返回空指针, 查找到返回该结点的地址
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • ListList.h
ListNode* ListFind(ListNode* phead, LTDataType x);
  • ListList.c
// 双向链表查找
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;
}

  • test.c
void LinkListTest3()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;
  pos = ListFind(head, 2);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");

  pos = ListFind(head, 6);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");
}

测试运行结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

3.8 双向链表在 pos 的前面进行插入 (LinkInsert)

先找到 pos 的前面一个结点的位置, 随后在这个结点和 pos 之间插入新结点
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • LinkList.h
void ListInsert(ListNode* pos, LTDataType x);
  • LinkList.c
// 双向链表在 pos 之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);  //确保pos合法

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* posPrev = pos->prev;      //找到 pos 前一个结点的位置

  //更新链接方式
  posPrev->next = newNode;
  newNode->prev = posPrev;

  newNode->next = pos;
  pos->prev = newNode;
}
  • test.c
void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListInsert(pos, -1);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListInsert(pos, -4);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListInsert(pos, -6);
    ListPrint(head);
  }

  ListDestroy(head);
}

测试运行结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

3.9 双向链表删除 pos 位置的结点 (ListErase)

先找到 pos 的前后两个结点的位置, 随后更新两个结点之间的链接关系, 最后删除 pos 结点
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

  • LinkList.h
void ListErase(ListNode* pos);
  • LinkList.c
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos)
{
  assert(pos);  //确保 pos 合法

  ListNode* posPrev = pos->prev;    //找到 pos 前一个结点的位置
  ListNode* posNext = pos->next;    //找到 pos 后一个结点的位置

  //更新链接方式
  posPrev->next = posNext;
  posNext->prev = posPrev;

  free(pos);  //释放空间
}
  • test.c
void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  ListDestroy(head);
}

测试运行结果如下:
数据结构: 线性表(带头双向循环链表实现),数据结构,数据结构,链表

3.10 双向链表销毁 (ListDestroy)

  • LinkList.h
void ListDestroy(ListNode* phead);
  • LinkList.c
// 双向链表销毁
void ListDestroy(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    ListNode* nextNode = cur->next;
    free(cur);
    cur = nextNode;
  }
  free(phead);
}

4. 总结

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续,但物理上不一定连续
随机访问 支持: O ( 1 ) O(1) O(1) 不支持: O ( N ) O(N) O(N)
任意位置插入或者删除元素 可能需要搬移元素, 效率低 O ( N ) O(N) O(N) 只需要修改指针指向
插入 动态顺序表, 空间不够时, 需要扩容 没有容量的概念
应用场景 元素高效存储 + 频繁访问 任意位置插入和删除频繁
缓存利用率

5. 完整代码

  • LinkList.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* ListCreate();
// 双向链表销毁
void ListDestroy(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos);

  • LinkList.c
#include "LinkList.h"

// 创建一个新结点
static ListNode* BuyListNode(LTDataType x)
{
  ListNode* newNode = (ListNode*)malloc(sizeof(struct ListNode));

  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }

  newNode->data = x;
  newNode->next = NULL;
  newNode->prev = NULL;

  return newNode;
}

// 创建返回链表的头结点
ListNode* ListCreate()
{
  // 动态开辟空间创建头结点, 如果开辟失败直接结束程序
  ListNode* head = BuyListNode(0);
  
  // 处理链表数据, 数据域随机值, 两个指针指向自己
  head->next = head;
  head->prev = head;

  return head;
}

// 双向链表打印
void ListPrint(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在

  printf("head <=> ");

  ListNode* cur = phead->next;  //从头结点开始遍历, 直到遇到哨兵结点结束
  while (cur != phead)
  {
    printf("%d <=> ", cur->data);
    cur = cur->next;
  }

  printf("\n");
}

// 双向链表销毁
void ListDestroy(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    ListNode* nextNode = cur->next;
    free(cur);
    cur = nextNode;
  }
  free(phead);
}

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点 
  ListNode* tail = phead->prev;       //找到尾结点
  
  //更改链接关系
  tail->next = newNode;
  newNode->prev = tail;
  phead->prev = newNode;
  newNode->next = phead;

}

// 双向链表尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);                    //确保哨兵结点存在
  assert(phead->next != phead);     //确保有结点可删

  ListNode* tail = phead->prev;     //找到要删除的尾结点
  ListNode* tailPrev = tail->prev;  //找到新的尾结点

  //更改链接关系
  tailPrev->next = phead;
  phead->prev = tailPrev;

  free(tail); //释放空间
}

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* first = phead->next;      //找到原来的头结点

  //更新链接关系
  phead->next = newNode;
  newNode->prev = phead;
  newNode->next = first;
  first->prev = newNode;

}

// 双向链表头删
void ListPopFront(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在
  assert(phead->next != phead); //确保链表不为空

  ListNode* first = phead->next;  //找到头结点位置
  ListNode* second = first->next; //找到头结点后一个结点的位置

  //更新链接关系
  phead->next = second;
  second->prev = phead;

  free(first); //释放空间
}

// 双向链表查找
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;
}

// 双向链表在 pos 之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);  //确保pos合法

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* posPrev = pos->prev;      //找到 pos 前一个结点的位置

  //更新链接方式
  posPrev->next = newNode;
  newNode->prev = posPrev;

  newNode->next = pos;
  pos->prev = newNode;
}
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos)
{
  assert(pos);  //确保 pos 合法

  ListNode* posPrev = pos->prev;    //找到 pos 前一个结点的位置
  ListNode* posNext = pos->next;    //找到 pos 后一个结点的位置

  //更新链接方式
  posPrev->next = posNext;
  posNext->prev = posPrev;

  free(pos);  //释放空间
}

  • test.c
#include "LinkList.h"

void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPopBack(head);
  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPrint(head);
  
  ListDestroy(head);
}

void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);

  ListPrint(head);
  
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPrint(head);

  ListDestroy(head);
}

void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  ListInsert(pos, 0);
  ListErase(pos);
  ListPrint(head);

  pos = ListFind(head, 4);
  ListInsert(pos, 10);
  ListPrint(head);

  pos = ListFind(head, 11);
  ListInsert(pos, 12);
  ListPrint(head);

  ListDestroy(head);
}

void LinkListTest4()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);

  ListNode* pos;

  pos = ListFind(head, 2);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");

  pos = ListFind(head, 6);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");
}

void LinkListTest5()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListInsert(pos, -1);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListInsert(pos, -4);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListInsert(pos, -6);
    ListPrint(head);
  }

  ListDestroy(head);
}

void LinkListTest6()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  ListDestroy(head);
}

int main(void)
{
  //LinkListTest1();
  //LinkListTest2();
  //LinkListTest3();
  //LinkListTest4();
  //LinkListTest5();
  LinkListTest6();
  return 0;
}

本章完.文章来源地址https://www.toymoban.com/news/detail-626859.html

到了这里,关于数据结构: 线性表(带头双向循环链表实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构,它的结构是很完美的,它弥补了单链表的许多不足,让我们一起来了解一下它是如何实现的吧!         它的节点中存储着数据和两个指针,一个 指针_prev 用来记录前一个节点的地址,另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(46)
  • 【数据结构】双向带头循环链表的实现

    前言:在前面我们学习了顺序表、单向链表,今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学习!一起努力! 带头双向循环链

    2024年01月15日
    浏览(49)
  • 【数据结构 -- C语言】 双向带头循环链表的实现

    目录 1、双向带头循环链表的介绍 2、双向带头循环链表的接口 3、接口实现 3.1 开辟结点 3.2 创建返回链表的头结点 3.3 判断链表是否为空 3.4 打印 3.5 双向链表查找 3.6 双向链表在pos的前面进行插入 3.6.1 头插 3.6.2 尾插 3.6.3 更新头插、尾插写法 3.7 双向链表删除pos位置的节点

    2024年02月09日
    浏览(61)
  • 【数据结构】—带头双向循环链表的实现(完美链表)

    链表结构一共有八种形式,在前面的文章里已经讲完了不带头单向非循环链表的实现,但是我们发现该链表实现尾插与尾删时比较麻烦,要先从头节点进行遍历,找到尾节点,时间复杂度为O(N),而本次所讲的带头双向循环单链表,则可以直接找到尾节点。 虽然该链表看起来

    2024年01月25日
    浏览(60)
  • 数据结构之双向带头循环链表函数功能实现与详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言 2.带头双向循环链表函数实现 3.总结         在前面我

    2024年02月05日
    浏览(51)
  • 【数据结构和算法】实现带头双向循环链表(最复杂的链表)

    前文,我们实现了认识了链表这一结构,并实现了无头单向非循环链表,接下来我们实现另一种常用的链表结构,带头双向循环链表。如有仍不了解单向链表的,请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表,并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(76)
  • 数据结构:链表基础OJ练习+带头双向循环链表的实现

    目录 一.leetcode剑指 Offer II 027. 回文链表 1.问题描述 2.问题分析与求解 (1) 快慢指针法定位链表的中间节点 (2) 将链表后半部分进行反转 附:递归法反转链表 (3) 双指针法判断链表是否回文 二.带头双向循环链表的实现 1.头文件 2.节点内存申请接口和链表初始化接口 3.链表的打

    2024年02月02日
    浏览(49)
  • 追梦之旅【数据结构篇】——详解C语言动态实现带头结点的双向循环链表结构

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年01月17日
    浏览(59)
  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

    2024年01月16日
    浏览(60)
  • 数据结构——带头双向循环链表

    在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针,目的在与存储前一个节点的地址,便于将整个链表连在一起。 动态申请内存结点,函数返回的是一个指针类型,用malloc开辟一个LTNode大小的空间,并用node指向这个空间,再判断

    2024年02月09日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包