基础数据结构之双向链表

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。

相关文章

MySQL中my.ini文件的基础配置和优化配置方式

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面：幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【Linux 从基础到进阶】Ansible自动化运维工具使用

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具，采用无代理架构（agentless），基于 SSH 连接进行管理，具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用，旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2