基础数据结构之双向链表

2024-09-04 15:20
文章标签 基础 链表 数据结构 双向

本文主要是介绍基础数据结构之双向链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

 基础定义

节点的定义

节点的初始化

创建双链表

1.前插法

2.尾插法

双向链表的遍历输出

指定位置插入

双向链表的按位取值

任意位置删除

双向链表销毁

主程序入口​​​​​​​

 基础定义

所谓的双向链表就是单向链表多了一个前驱指针。双向链表是由一个个结点组成每个结点之间通过链接关系串联起来每个结点都有前驱结点和后继结点第一个结点的前驱结点为空结点最后一个结点的后继结点为空结点。

由链接关系A <- >B组织起来的两个结点B被称为A的后继结点A被称为B的前驱结点因为是双向的所以被称为双向链表由于链表是由一个个结点组成。

节点的定义

// c++ 代码示例typedef struct DoubleLinkList
{int data ;DoubleLinkList* prev ;DoubleLinkList* next ;
}DoubleLinkList, DoubleLinkNode ;

# python 代码示例class DoubleLinkList :def __init__(self, val) :self.val = valself.next = Noneself.pre = None#  None <- 节点 -> None

节点的初始化

// c++ 代码示例bool DoubleLinkListInit(DoubleLinkList* &L)
{L = new DoubleLinkNode ;if (!L){return false ;}L -> prev = NULL ;L -> next = NULL ;L -> data = -1 ;return true ;
}
# python 代码示例
class DoubleLinkNode :def __init__(self, data = None) :self.data = dataself.next = Noneself.prev = None
def DoubleLinkListInit() :try :L = DoubleLinkNode()L.data = -1return Lexcept Exception as e :print(f"Error Initializing List: {e}")return None
# 使用示例
L = DoubleLinkListInit()
if L:print("双向链表初始化成功")
else:print("双向链表初始化失败")

创建双链表

1.前插法
bool DoubleLinkInsertFront(DoubleLinkList*& L, DoubleLinkNode* node)
{if (!L || !node){return false ;}if (L -> next == NULL){node -> next = NULL ;node -> prev = L ;L -> next = node ;}else{L -> next -> prev = node ;node -> next = L -> next ;node -> prev = L ;L -> next = node ;}return true ;}
# python 代码示例def double_link_insert_front(L, node):  if L is None or node is None:  return False  if L.next is None:  node.next = None  node.prev = L  L.next = node  else:  L.next.prev = node  node.next = L.next  node.prev = L  L.next = node  return True
2.尾插法
# python 代码示例def double_link_list_insert_back(L, node):  if L is None or node is None:  return False  last = L  while last.next:  last = last.next  node.next = None  node.prev = last  last.next = node  return True  
// c++ 代码示例
bool DoubleLinkListInsertBack(DoubleLinkList*& L, DoubleLinkNode* node)
{DoubleLinkNode* last = NULL ;if (!L || !node){return false ;}last = L ;  while (last -> next){last = last -> next ;}node -> next = NULL ;node -> prev = last ;last -> next = node ;return true ;
}

双向链表的遍历输出

// c++ 代码示例void DoubleLinkListPrint(DoubleLinkList* &L)
{DoubleLinkNode* p = L ;if (!L){cout << "链表为空" << endl ;return ;}cout << p -> data << " " ;while (p -> next){cout << p -> next -> data << " " ;p = p -> next ;}cout << endl << "逆向打印" << endl ;while (p){cout << p -> data << " " ;p = p -> prev ;}cout << endl ;return ;
}
# python 代码示例ef double_link_list_print(L):  if L is None:  print("链表为空")  return  p = L  print(p.data, end=" ")  while p.next:  p = p.next  print(p.data, end=" ")  print("\n逆向打印")  while p:  print(p.data, end=" ")  p = p.prev  print()

指定位置插入

// c++代码示例bool DoubleLinkListInsert(DoubleLinkList* L, int i, int e)
{if (!L || !L -> next){return false ;}if (i < 1){return false ;}int j = 0 ;DoubleLinkList* p , * s ;p = L ;while (p && j < i){p = p -> next ;j++ ;}if (!p || j != i){cout << "结点不存在" << i << endl ;return false ;}s = new DoubleLinkNode ;s -> data = e ;   s -> next = p ;s -> prev = p -> prev ;p -> prev -> next = s ;p -> prev = s ;return true ;
}
# python 代码示例def double_link_list_insert(L, i, e):  if L is None or L.next is None:  return False  if i < 1:  return False  j = 0  p = L  while p and j < i:  p = p.next  j += 1  if p is None or j != i:  print(f"结点不存在 {i}")  return False  s = DoubleLinkNode(data=e)  s.next = p  s.prev = p.prev  p.prev.next = s  p.prev = s  return True

双向链表的按位取值

// c++ 代码示例bool DoubleLinkListGetElem(DoubleLinkList* &L, int i, int& e)
{int index ;DoubleLinkList* p ;if (!L || !L -> next){return false ;}p = L -> next ;index = 1 ;while (p || index < i){p = p -> next ;    index++ ;}if (!p || index > i){return false ;}e = p -> data ;return true ;
}
# python 代码示例def double_link_list_get_elem(L, i):  if L is None or L.head.next is None:  return False, None  p = L.head.next  index = 1  while p and index < i:  p = p.next  index += 1  if p is None or index > i:  return False, None  return True, p.data

任意位置删除

// c++ 代码示例bool DoubleLinkListDelete(DoubleLinkList*& L, int i)
{DoubleLinkList* p ;int index = 0 ;if (!L || !L -> next){cout << "双向链表为空！" << endl ;return false ;}if (i < 1 ) {cout << "不能删除头结点！" << endl ;return false ;}p = L ;while (p && index < i){p = p -> next ;index++ ;}if (!p){return false ;}p -> prev -> next = p -> next ;if (p -> next != nullptr){p -> next -> prev = p -> prev ;}delete p ;return true ;
}
# python 代码示例def double_link_list_delete(L, i):  if L is None or L.head.next is None:  print("双向链表为空！")  return False  if i < 1:  print("不能删除头结点！")  return False  p = L.head.next  index = 1  while p and index < i:  p = p.next  index += 1  if p is None:  return False  # 更新前后节点的链接  p.prev.next = p.next  if p.next is not None:  p.next.prev = p.prev  del p  # 删除节点  return True

双向链表销毁

// c++ 代码示例void DoubleLinkListDestory(DoubleLinkList* &L)
{DoubleLinkList* p = L ;cout << "销毁链表" << endl ;while (p){L = L -> next ;delete p ;p = L ;}
}
# python 代码示例def double_link_list_destroy(L):  print("销毁链表")  p = L.head  # 从头节点开始  while p:  next_node = p.next  # 保存下一个节点  del p  # 删除当前节点  p = next_node  # 移动到下一个节点  L.head = None  # 清空链表的头节点引用

主程序入口

// c++ 代码示例
int main()
{DoubleLinkList* L ;DoubleLinkList* s ;if (DoubleLinkListInit(L)){cout << "初始化链表成功！" << endl ;}else{cout << "初始化链表失败！" << endl ;}int n ;cout << "前插法" << endl ;cout << "输入元素个数" ;cin >> n ;cout << endl << "依次输入" << n << "个元素：" ;while ( n > 0 ){s = new DobleLinkNode ;cin >> s -> data ;DoubleLinkListInsertFront(L, s) ;n-- ;}DoubleLinkListPrint(L) ;for (int j = 0 ; j < 3 ; j++){int i , x ;cout << "请输入要插入的位置和元素（用空格隔开）" ;cin >> i >> x ;if (DoubleLinkListInsert(L, i, x)){cout << "插入成功！" << endl ;}else{cout << "插入失败！" << endl ;}DoubleLinkListPrint(L) ;}if (DoubleLinkListDelete(L, 2)){cout << "删除链表第2个元素成功！" << endl ;}else{cout << "删除链表第2个元素失败！" << endl ;}DoubleLinkListPrint(L);DoubleLinklistDestroy(L);return 0;
}
# python 代码示例def main():  L = DoubleLinkList()  print("初始化链表成功！")  n = int(input("前插法\n输入元素个数: "))  print(f"依次输入 {n} 个元素：")  while n > 0:  data = input()  node = DoubleLinkListNode(data)  L.insert_front(node)  n -= 1  L.print_list()  for _ in range(3):  i, x = map(int, input("请输入要插入的位置和元素（用空格隔开）: ").split())  new_node = DoubleLinkListNode(x)  if L.insert_front(new_node) and L.delete(i):  print("插入成功！")  else:  print("插入失败！")  L.print_list()  if L.delete(2):  print("删除链表第2个元素成功！")  else:  print("删除链表第2个元素失败！")  L.print_list()  L.destroy()  if __name__ == "__main__":  main()

这篇关于基础数据结构之双向链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1136328。

相关文章

从基础到高级详解Python数值格式化输出的完全指南

从基础到高级详解Python数值格式化输出的完全指南

《从基础到高级详解Python数值格式化输出的完全指南》在数据分析、金融计算和科学报告领域,数值格式化是提升可读性和专业性的关键技术,本文将深入解析Python中数值格式化输出的相关方法,感兴趣的小伙... 目录引言：数值格式化的核心价值一、基础格式化方法1.1 三种核心格式化方式对比1.2 基础格式化示例
阅读更多...
redis-sentinel基础概念及部署流程

redis-sentinel基础概念及部署流程

《redis-sentinel基础概念及部署流程》RedisSentinel是Redis的高可用解决方案,通过监控主从节点、自动故障转移、通知机制及配置提供,实现集群故障恢复与服务持续可用,核心组件包... 目录一. 引言二. 核心功能三. 核心组件四. 故障转移流程五. 服务部署六. sentinel部署
阅读更多...
从基础到进阶详解Python条件判断的实用指南

从基础到进阶详解Python条件判断的实用指南

《从基础到进阶详解Python条件判断的实用指南》本文将通过15个实战案例,带你大家掌握条件判断的核心技巧,并从基础语法到高级应用一网打尽,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录​引言：条件判断为何如此重要一、基础语法：三行代码构建决策系统二、多条件分支：elif的魔法三、
阅读更多...
Python WebSockets 库从基础到实战使用举例

Python WebSockets 库从基础到实战使用举例

《PythonWebSockets库从基础到实战使用举例》WebSocket是一种全双工、持久化的网络通信协议,适用于需要低延迟的应用,如实时聊天、股票行情推送、在线协作、多人游戏等,本文给大家介... 目录1. 引言2. 为什么使用 WebSocket？3. 安装 WebSockets 库4. 使用 We
阅读更多...
redis数据结构之String详解

redis数据结构之String详解

《redis数据结构之String详解》Redis以String为基础类型,因C字符串效率低、非二进制安全等问题,采用SDS动态字符串实现高效存储,通过RedisObject封装,支持多种编码方式（如... 目录一、为什么Redis选String作为基础类型？二、SDS底层数据结构三、RedisObject
阅读更多...
Java集合中的链表与结构详解

Java集合中的链表与结构详解

《Java集合中的链表与结构详解》链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序的通过链表中的引用链接次序实现,文章对比ArrayList与LinkedList的结构差异,详细讲解了链表... 目录一、链表概念与结构二、当向单链表的实现2.1 准备工作2.2 初始化链表2.3 打印数据、链表长
阅读更多...
从基础到高阶详解Python多态实战应用指南

从基础到高阶详解Python多态实战应用指南

《从基础到高阶详解Python多态实战应用指南》这篇文章主要从基础到高阶为大家详细介绍Python中多态的相关应用与技巧,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、多态的本质：python的“鸭子类型”哲学二、多态的三大实战场景场景1：数据处理管道——统一处理不同数据格式
阅读更多...
MySQL数据类型与表操作全指南( 从基础到高级实践)

MySQL数据类型与表操作全指南( 从基础到高级实践)

《MySQL数据类型与表操作全指南(从基础到高级实践)》本文详解MySQL数据类型分类（数值、日期/时间、字符串）及表操作（创建、修改、维护）,涵盖优化技巧如数据类型选择、备份、分区,强调规范设计与... 目录mysql数据类型详解数值类型日期时间类型字符串类型表操作全解析创建表修改表结构添加列修改列删除列
阅读更多...
Python 函数详解:从基础语法到高级使用技巧

Python 函数详解:从基础语法到高级使用技巧

《Python函数详解:从基础语法到高级使用技巧》本文基于实例代码,全面讲解Python函数的定义、参数传递、变量作用域及类型标注等知识点,帮助初学者快速掌握函数的使用技巧,感兴趣的朋友跟随小编一起... 目录一、函数的基本概念与作用二、函数的定义与调用1. 无参函数2. 带参函数3. 带返回值的函数4.
阅读更多...
python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2