Java数据结构与算法学习之双向链表

目录
  • 双向链表的储存结构示意图
  • 双向链表的初始化结构
    • 1.双向链表的结点
    • 2.双向链表的头结点
    • 3.总代码
  • 双向链表中的指定文件插入元素 
    • 1.插入的为第一个位置
    • 2.其他位置插入
    • 总代码
  • 双向链表的删除
    • 1.删除第一个元素
    • 2.删除其他位置元素
    • 总代码

双向链表的储存结构示意图

双向链表的初始化结构

1.双向链表的结点

代码实现

//双向链表的结点,包含一个数据域,两个指针域
typedef struct DoublyNode {
	ElementType date;  //数据域
	struct DoublyNode* prev;   //指向前缀结点
	struct DoublyNode* next;   //指向后缀结点
}DoublyNode;

2.双向链表的头结点

//双向链表
typedef struct DoublyLinkList {
	int length;
	DoublyNode* next;
};

3.总代码

//双向链表的结点,包含一个数据域,两个指针域
typedef struct DoublyNode {
	ElementType date;  //数据域
	struct DoublyNode* prev;   //指向前缀结点
	struct DoublyNode* next;   //指向后缀结点
}DoublyNode;

//双向链表
typedef struct DoublyLinkList {
	int length;
	DoublyNode* next;
};

双向链表中的指定文件插入元素 

1.插入的为第一个位置

代码实现

2.其他位置插入

代码实现

总代码

void InsertDoublyLinkList(DoublyLinkList* dlist, int pos, ElementType element) {
	//创建空节点
	DoublyNode* node = (DoublyLinkList*)malloc(sizeof(DoublyLinkList));
	node->date = element;
	node->prev = NULL;
	node->next = NULL;
	//在第一个位置插入结点
	if (pos == 1) {
		node->next = dlist->next;
		dlist->next = node;
		node->next->prev = node;
		dlist->length++;
		return;
	}
	DoublyLinkList* currNode = dlist->next;
	for (int i = 1; currNode && i < pos - 1; i++) {
		currNode = currNode->next;
	}
	if (currNode) {
		node->prev = currNode;
		if (currNode->next) {
			//如果前置结点非空->因为空就表示没有后继结点了
			//将插入位置的前置结点改为指向新结点
			currNode->next->prev = node;
		}
		node->next = currNode->next;
		currNode->next = node;
		dlist->length++;
	}
}

双向链表的删除

1.删除第一个元素

代码实现

2.删除其他位置元素

代码实现

总代码

void DeleteDoublyLinkList(DoublyLinkList* dlist, int pos) {
	if (pos == 1) {
		DoublyLinkList* node = dlist->next;
		if (node) {
			dlist->next;
			if (node->next) {
				//如果哟有第二个结点,那么设置第二个结点的前置结点为NULL
				node->next->prev = NULL;
			}
			free(node);
			dlist->length--;
		}
		return;
	}

	DoublyLinkList* node = dlist->next;
	for (int i = 1; i < pos; i++) {
		node = node->next;
	}
	if (node) {
		if (node->next) {
			node->next->prev = node->prve;
		}
		node->prev->next = node->next;
		free(node);
		dlist->length--;
	}
	return;
}
 

到此这篇关于Java数据结构与算法学习之双向链表的文章就介绍到这了,更多相关Java数据结构 双向链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 带你了解Java数据结构和算法之链表

    目录 1.链表(Linked List) 2.单向链表(Single-Linked List) ①.单向链表的具体实现 ②.用单向链表实现栈 4.双端链表 ①.双端链表的具体实现 ②.用双端链表实现队列 5.抽象数据类型(ADT) 6.有序链表 7.有序链表和无序数组组合排序 8.双向链表 9.总结 前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷.在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会

  • Java数据结构与算法之双向链表、环形链表及约瑟夫问题深入理解

    目录 一.双向链表 二.环形链表及其应用:约瑟夫问题 环形链表图示 构建一个单向的环形链表思路 遍历环形链表 约瑟夫问题 一.双向链表 使用带head头的双向链表实现 - 水浒英雄排行榜管理单向链表的缺点分析: 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找. 单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除节点时,总是找到temp,temp时待删除节点的前一个节点(认真体会). 分析双向链表的遍历,添加,修改,删除的操作思路 1.遍历

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • Java数据结构与算法之单链表深入理解

    目录 一.单链表(Linked List)简介 二.单链表的各种操作 1.单链表的创建和遍历 2.单链表的按顺序插入节点 以及节点的修改 3.单链表节点的删除 4.以上单链表操作的代码实现 (通过一个实例应用) 三.单链表常见面试题 1.求单链表中节点的个数 2.查找单链表中的倒数第K个节点[新浪面试题] 3.单链表的反转[腾讯面试题,有点难度] 4.从尾到头打印单链表 一.单链表(Linked List)简介 二.单链表的各种操作 1.单链表的创建和遍历 2.单链表的按顺序插入节点 以及节点的

  • Java数据结构与算法学习之循环链表

    目录 存储结构示意图 初始化循环链表  循环链表的插入 首位置 代码实现 其他位置 代码实现(总) 循环链表的删除 1.操作的为第一个元素 2.操作元素不为第一个元素 代码实现(总) 循环链表的常见操作  存储结构示意图 优点 : 能够通过任意结点遍历整个链表结构 初始化循环链表  1.循环链表的结点 typedef struct CircularNode { ElementType date; //数据域 struct CircularNode* next; //指向下一个结点的指针域 }Ci

  • Java数据结构与算法学习之双向链表

    目录 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 2.双向链表的头结点 3.总代码 双向链表中的指定文件插入元素  1.插入的为第一个位置 2.其他位置插入 总代码 双向链表的删除 1.删除第一个元素 2.删除其他位置元素 总代码 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 代码实现 //双向链表的结点,包含一个数据域,两个指针域 typedef struct DoublyNode { ElementType date; //数据域 struct

  • java数据结构和算法学习之汉诺塔示例

    复制代码 代码如下: package com.tiantian.algorithms;/** *    _|_1              |                | *   __|__2             |                | *  ___|___3            |                |            (1).把A上的4个木块移动到C上. * ____|____4           |                | *    

  • Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

  • Java数据结构与算法之稀疏数组与队列深入理解

    目录 一.数据结构和算法简介 二.稀疏数组 稀疏数组的应用实例 二维数组与稀疏数组的转换 二维数组 转 稀疏数组的思路 稀疏数组 转 原始的二维数组的思路 三.队列 数组模拟队列 代码优化:数组模拟环形队列 之前学完了Java SE的知识,掌握了面向对象的编程思想,但对集合.多线程.反射.流的使用等内容理解的还不是很深入,打算再学习数据结构与算法的同时,在空闲的时间里去图书馆看<Java核心技术 卷 I>这本书,很多大佬对这本书很推崇,之前在图书馆也看过其他Java的书籍,经过对比,这本书确实

  • java数据结构与算法之马踏棋盘

    本文实例为大家分享了java数据结构与算法之马踏棋盘的具体代码,供大家参考,具体内容如下 马踏棋盘算法也被称为骑士周游问题 将马随机放在过期象棋的8x8棋盘的某个方格中,马按走棋规则进行移动,要求每个方格只进入一次,走遍棋盘上全部64个方格 骑士周游问题结局步骤和思路 1.创建棋盘chessBoard,是一个二维数组2.将当前位置设置为已个访问,然后根据当前位置,计算马儿还能走那些位置,并放到一个集合中(ArrayList),最多8个位置3.变量ArrayList存放的所有位置,看看哪个可以走通

  • Java 数据结构与算法系列精讲之单向链表

    目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表

  • Java 数据结构与算法系列精讲之环形链表

    目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

随机推荐