基础数据结构之双向链表

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。

相关文章

从基础到进阶详解Pandas时间数据处理指南

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据
阅读更多...
Linux链表操作方式

Linux链表操作方式

《Linux链表操作方式》：本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与
阅读更多...
安装centos8设置基础软件仓库时出错的解决方案

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》：本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas
阅读更多...
Linux基础命令@grep、wc、管道符的使用详解

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》：本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三，带选项 -nwc概念语法作用wc，不带选项-c，统计字节数-
阅读更多...
python操作redis基础

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对（Key-Value）存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re
阅读更多...
SpringBoot基础框架详解

SpringBoot基础框架详解

《SpringBoot基础框架详解》SpringBoot开发目的是为了简化Spring应用的创建、运行、调试和部署等,使用SpringBoot可以不用或者只需要很少的Spring配置就可以让企业项目快... 目录SpringBoot基础 – 框架介绍1.SpringBoot介绍1.1 概述1.2 核心功能2
阅读更多...
Spring Boot集成SLF4j从基础到高级实践(最新推荐)

Spring Boot集成SLF4j从基础到高级实践(最新推荐)

《SpringBoot集成SLF4j从基础到高级实践(最新推荐)》SLF4j(SimpleLoggingFacadeforJava)是一个日志门面（Facade）,不是具体的日志实现,这篇文章主要介... 目录一、日志框架概述与SLF4j简介1.1 为什么需要日志框架1.2 主流日志框架对比1.3 SLF4
阅读更多...
Spring Boot集成Logback终极指南之从基础到高级配置实战指南

Spring Boot集成Logback终极指南之从基础到高级配置实战指南

《SpringBoot集成Logback终极指南之从基础到高级配置实战指南》Logback是一个可靠、通用且快速的Java日志框架,作为Log4j的继承者,由Log4j创始人设计,：本文主要介绍... 目录一、Logback简介与Spring Boot集成基础1.1 Logback是什么？1.2 Sprin
阅读更多...
MySQL复合查询从基础到多表关联与高级技巧全解析

MySQL复合查询从基础到多表关联与高级技巧全解析

《MySQL复合查询从基础到多表关联与高级技巧全解析》本文主要讲解了在MySQL中的复合查询,下面是关于本文章所需要数据的建表语句,感兴趣的朋友跟随小编一起看看吧... 目录前言：1.基本查询回顾：1.1.查询工资高于500或岗位为MANAGER的雇员，同时还要满足他们的姓名首字母为大写的J1.2.按照部门
阅读更多...
Android Mainline基础简介

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline？Android Mainline 的工作原理关键
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2