AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

最最容易实现的链表结构——双向链表（数据结构C语言实现4）

2022-08-15 107
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 最最容易实现的链表结构——双向链表（数据结构C语言实现4）

双链表结构

单链表

之前我们已经知道单向链表的结构：

逻辑结构


image.png

//类型创建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType data;   //存值
      struct SListNode* next; //存下一节点的指针
  }SLNode;

结构体存放了一个date数据和一个next结构体指针指向下一个节点！

我们再来看一下物理结构

image.png

这便是单链表，结构简单，但我们实现起来却比较复杂的一种链表结构，我们今天来看一下双向链表！


双向链表

所谓双向链表顾名思义就是，节点方向是双向的，不像单链那样，只能从头节点出发到尾结点!


typedef int LDataType;
typedef struct ListNode
{
 struct ListNode*prev;
 LDataType data;
 struct ListNode*next;
}LisNode;

image.png

从上面的逻辑结构我们可以看出这个双向循环链表是带哨兵位，就是带头，并且第一个节点与最后一个节点相连说明是循环的！所以上面的结构是带头双向循环链表我们今天要实现的链表也是这种最特殊的链表！

链表的分类：

image.png

image.png



image.png

双向链表的实现

image.png

我们先来创建一个双向链表的结构体节点


//节点类型创建
typedef int LDataType;
typedef struct ListNode
{
  struct ListNode* prev;
  LDataType data;
  struct ListNode* next;
}ListNode;

接口实现

创建新的节点


//创建新的节点
ListNode* ListBuyNewNode(LDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode)
  {
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
  }
  else
  {
  printf("malloc fail!\n");
  return NULL;
  }
}

链表初始化返回头节点


//初始化链表返回头结点
ListNode* ListInit()
{
  ListNode* head=ListBuyNewNode(0);
  head->next = head;
  head->prev = head;
  return head;
}

链表不用了销毁

//回收
void ListDestroy(ListNode* head)
{
  head->next=head->prev = NULL;
}

打印


//打印
void ListPrint(ListNode* head)
{
  assert(head);
  ListNode* cur = head->next;
  while (cur!=head)
  {
  printf("%d ", cur->data);
  cur = cur->next;
  }
  printf("\n");
}

头插

和单向不带头链表不一样，因为链表带了头节点就只需要传一级指针就可以进行头插！因为头节点是不会改变的


//头插
void ListFrontPush(ListNode* head, LDataType x)
{
  ListNode* newnode = ListBuyNewNode(x);
  newnode->next = head->next;
  newnode->prev = head;
  head->next->prev= newnode;
  head->next = newnode;
}

image.png

**注：**如果我们直接像上面一样不创建其他变量，直接插入节点，我们需要先连接new的指针，再改变head和head->next的指针，先连后改如果我们现将head->next改变指向了new我们就无法找到head->next节点了！其他接口也是如此！

头插接口测试

image.png


头删


//头删
void ListFrontPop(ListNode* head)
{
  ListNode* ret = head->next;
  head->next = ret->next;
  ret->next->prev = head;
  free(ret);
  ret = NULL;
}

头删接口测试

image.png


ListNode* head = ListInit();
  ListFrontPush(head, 1);
  ListFrontPush(head, 2);
  ListFrontPush(head, 3);
  ListFrontPush(head, 4);
  ListPrint(head);
  ListFrontPop(head);
  ListFrontPop(head);
  ListPrint(head);


image.png


//尾插
void ListBackPush(ListNode* head, LDataType x)
{
  ListNode* new = ListBuyNewNode(x);
  new->next = head;
  new->prev = head->prev;
  head->prev->next= new;
  head->prev = new;
}

尾插接口测试


ListNode* head = ListInit();
  ListFrontPush(head, 1);
  ListFrontPush(head, 2);
  ListFrontPush(head, 3);
  ListFrontPush(head, 4);
  ListPrint(head);
  ListBackPush(head, 1);
  ListBackPush(head, 2);
  ListBackPush(head, 3);
  ListBackPush(head, 4);
  ListBackPush(head, 5);
  ListPrint(head);


image.png


//尾删
void ListBackPop(ListNode* head)
{
  ListNode* tail = head->prev;
  head->prev = tail->prev;
  tail->prev->next = head;
  free(tail);
  tail = NULL;
}

尾删接口测试


ListNode* head = ListInit();
  ListFrontPush(head, 1);
  ListFrontPush(head, 2);
  ListFrontPush(head, 3);
  ListFrontPush(head, 4);
  ListPrint(head);
  ListBackPush(head, 1);
  ListBackPush(head, 2);
  ListBackPush(head, 3);
  ListBackPush(head, 4);
  ListBackPush(head, 5);
  ListPrint(head);
  ListBackPop(head);
  ListBackPop(head);
  ListBackPop(head);
  ListPrint(head);

image.png

查找


//查找x节点并返回
ListNode* ListFind(ListNode* head, LDataType x)
{
  ListNode* ret = head->next;
  while (ret!= head)
  {
  if (ret->data == x)
  {
    return ret;
  }
  ret = ret->next;
  }
  return NULL;
}

pos节点修改


//在pos前插入
void ListInsert(ListNode* head, ListNode* pos,LDataType x)
{
  ListNode* new = ListBuyNewNode(x);
  new->next = pos;
  new->prev = pos->prev;
  pos->prev->next = new;
  pos->prev = new;
}

pos节点删除


//pos节点删除
void ListErase(ListNode* head, ListNode* pos)
{
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
  pos = NULL;
}

接口测试


void test1()
{
  ListNode* head = ListInit();
  ListFrontPush(head, 1);
  ListFrontPush(head, 2);
  ListFrontPush(head, 3);
  ListFrontPush(head, 4);
  ListPrint(head);
  ListNode* pos = ListFind(head, 3);
  if (pos)
  {
  ListInsert(head, pos, 33);
  ListPrint(head);
  ListErase(head, pos);
  ListPrint(head);
  }
}

image.png


源码

List.h头文件


#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//节点类型创建
typedef int LDataType;
typedef struct ListNode
{
  struct ListNode* prev;
  LDataType data;
  struct ListNode* next;
}ListNode;
//创建新的节点
ListNode*ListBuyNewNode(LDataType x);
//初始化链表返回头结点
ListNode* ListInit();
//回收
void ListDestroy(ListNode*head);
//打印
void ListPrint(ListNode* head);
//头插
void ListFrontPush(ListNode* head,LDataType x);
//头删
void ListFrontPop(ListNode* head);
//尾插
void ListBackPush(ListNode* head,LDataType x);
//尾删
void ListBackPop(ListNode* head);
//查找
ListNode* ListFind(ListNode* head, LDataType x);
//pos节点删除
void ListErase(ListNode* head, ListNode* pos);
//在pos前插入
void ListInsert(ListNode* head, ListNode* pos , LDataType x);

List.c所有接口源码


//创建新的节点
ListNode* ListBuyNewNode(LDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode)
  {
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
  }
  else
  {
  printf("malloc fail!");
  return NULL;
  }
}
//初始化链表返回头结点
ListNode* ListInit()
{
  ListNode* head=ListBuyNewNode(0);
  head->next = head;
  head->prev = head;
  return head;
}
//回收
void ListDestroy(ListNode* head)
{
  head->next=head->prev = NULL;
}
//打印
void ListPrint(ListNode* head)
{
  assert(head);
  ListNode* cur = head->next;
  while (cur!=head)
  {
  printf("%d ", cur->data);
  cur = cur->next;
  }
  printf("\n");
}
//头插
void ListFrontPush(ListNode* head, LDataType x)
{
  ListNode* newnode = ListBuyNewNode(x);
  newnode->next = head->next;
  newnode->prev = head;
  head->next->prev= newnode;
  head->next = newnode;
}
//头删
void ListFrontPop(ListNode* head)
{
  ListNode* ret = head->next;
  head->next = ret->next;
  ret->next->prev = head;
  free(ret);
  ret = NULL;
}
//尾插
void ListBackPush(ListNode* head, LDataType x)
{
  ListNode* new = ListBuyNewNode(x);
  new->next = head;
  new->prev = head->prev;
  head->prev->next= new;
  head->prev = new;
}
//尾删
void ListBackPop(ListNode* head)
{
  ListNode* tail = head->prev;
  head->prev = tail->prev;
  tail->prev->next = head;
  free(tail);
  tail = NULL;
}
//查找
ListNode* ListFind(ListNode* head, LDataType x)
{
  ListNode* ret = head->next;
  while (ret!= head)
  {
  if (ret->data == x)
  {
    return ret;
  }
  ret = ret->next;
  }
  return NULL;
}
//pos节点删除
void ListErase(ListNode* head, ListNode* pos)
{
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
  pos = NULL;
}
//在pos前插入
void ListInsert(ListNode* head, ListNode* pos,LDataType x)
{
  ListNode* new = ListBuyNewNode(x);
  new->next = pos;
  new->prev = pos->prev;
  pos->prev->next = new;
  pos->prev = new;
}

文章标签：
C语言
关键词：
数据结构c语言
数据结构结构
链表c语言
数据结构链表
C语言数据结构
bug郭
目录
相关文章
ephemerals__
|
23天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
109 9
ephemerals__
|
22天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
60 16
ephemerals__
|
22天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
76 8
ephemerals__
|
24天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
50 4
ephemerals__
|
24天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
40 0
那年春天
|
13天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
22 1
德国都芳最好
|
16天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
61 21
html的七十二变
|
19天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
28 2
dufadayang
|
21天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
47 4
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
33 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器