java模拟实现双向链表
作者:小码农叔叔 发布时间:2022-06-05 09:16:16
标签:java,双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点
下图是双向链表的逻辑结构图,和单链表不同的是,双向链表中每个节点包含两个节点的指针引用,和一个数据域,这两个节点分别指向前一个节点和后一个节点;
双向链表的这种结构比起单链表,其改进之处正在于此,通过对前后节点的引用可以使得在整个链表中,通过给定的值,可以从前或者向后遍历,大大提升了遍历查询的效率,一定程度上解决了单链表的性能问题,但与此同时,链表的存储开销也增大了,我们熟悉的linkedList,其底层就是这个原理实现的.
废话不多说,相信通过上面的解释大家已经很明白了,下面直接上代码,可以结合代码和图结构理解双向链表,
public class DoubleLinkTest<T> {
/**
* 内部构造节点类
*
* @param <T>
*/
private class Node<T> {
private T data;
private Node next; // 指向下一个节点的引用
private Node prev; // 指向前一个节点的引用
public Node(T data) {
this.data = data;
}
}
private Node<T> head; // 模拟头结点
private Node<T> last; // 模拟尾部节点
private Node<T> other; // 暂定一个临时节点,用作指针节点
private int length;
public void DoubleLinkTest() {
head = new Node<T>(null);
last = head;
length = 0;
}
public void DoubleLinkTest(T data) {
head = new Node<T>(data);
last = head;
length = 0;
}
/**
* 链表是否为空
*
* @return
*/
public boolean isEmpty() {
return length == 0;
}
/**
* 普通添加,往链表尾部添加
*
* @param data
*/
public void add(T data) {
if (isEmpty()) { // 链表为空,新创建一个链表
head = new Node<T>(data);
last = head;
length++;
} else {
other = new Node<T>(data);
other.prev = last;
last.next = other; // 将新的节点与原来的尾部节点进行结构上的关联
last = other; // other将成为最后一个节点
length++;
}
}
/**
* 在指定的数据后面添加数据
*
* @param data
* @param insertData
*/
public void addAfter(T data, T insertData) {
other = head;
while (other != null) { // 我们假定这个head是不为空的。
if (other.data.equals(data)) {
Node<T> t = new Node<T>(insertData);
t.prev = other;
t.next = other.next;// 对新插入的数据进行一个指向的定义
other.next = t;
if (t.next == null) {
last = t;
}
length++;
}
other = other.next;
}
}
/**
* 删除,删除指定的数据
*
* @param data
*/
public void remove(T data) {
other = head;// 我们假定这个head是不为空的。
while (other != null) {
if (other.data.equals(data)) {
other.prev.next = other.next;
length--;
}
other = other.next;
}
}
/**
* 测试打印数据
*/
public void printList() {
other = head;
for (int i = 0; i < length; i++) {
System.out.println(other.data + " ");
other = other.next;
}
}
public static void main(String[] args) {
DoubleLinkTest<Integer> link = new DoubleLinkTest<Integer>();
link.add(1);
link.add(2);
link.add(3);
link.add(5);
link.add(6);
link.add(7);
link.printList();
System.out.println(" ============== ");
System.out.println(" ==== 在3后面添加一个数据开始========== ");
link.addAfter(3, 99);
link.printList();
System.out.println(" ==== 在3后面添加一个数据结束========== " + "\r\n");
System.out.println(" ==== 移除一个数据开始========== ");
link.remove(99);
link.printList();
System.out.println(" \r\n");
}
}
运行main函数,可以看到控制台的打印输出:
来源:https://blog.csdn.net/zhangcongyi420/article/details/88383069
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- 本文实例为大家分享了Java Socket聊天室功能的具体代码,供大家参考,具体内容如下Client.javaimport java.io.
- springboot集成swagger3swagger3的springboot启动器jar包<!-- https://mvnrepos
- 什么是队列结构一种线性结构,具有特殊的运算法则【只能在一端(队头)删除,在另一端(队尾)插入】。分类:顺序队列结构链式队列结构基本操作:入队
- 前言最近一直被无尽的业务需求淹没,没时间喘息,终于接到一个能让我突破代码舒适区的活儿,解决它的过程非常曲折,一度让我怀疑人生,不过收获也很大
- 本文实例为大家分享了PropertyDescriptor反射调用set和get方法,供大家参考,具体内容如下第一段:package com.
- Linux Hadoop 2.7.3 安装搭建Hadoop实现了一个分布式文件系统(Hadoop Distributed File Syst
- 本文讲述了在Java中如何创建和结束线程的最基本方法,只针对于Java初学者。一些高级知识如线程同步、调度、线程池等内容将会在后续章节中逐步
- spring开启声明式事务导入依赖pom.xml<dependencies>  
- 本文实例为大家分享了flutter实现底部导航栏的具体代码,供大家参考,具体内容如下一.flutter底部导航栏常用组件BottomNavi
- 导读 Spring Boot方式的项目开发已经逐步成为Java应用开发领域的主流框架,它不仅可以方便地创建生产级的Spring应用
- 本章将具体讲解下拉菜单的交互。使用下拉菜单(Dropdown)插件,您可以向任何组件(比如导航栏、标签页、胶囊式导航菜单、按钮等)添加下拉菜
- 背景SpringBoot 版本<parent> <groupId>org.springfr
- 运行远程主机上的shell脚本下面的例子是教给大家如何通过java程序,运行远程主机上的shell脚本。(我讲的不是一个黑客学习教程,而是使
- 问题分析疑惑满满小枫听到这个面试题的时候,心想这是什么水面试官,怎么问这么简单的题目,心想一个for循环加上equal判断再删除不就完事了吗
- 前言在Java System#exit 无法退出程序的问题一文末尾提到优雅停机的一种实现方案,要借助Shutdown Hook进行实现,本文
- 本文实例讲述了Java基于JDBC实现事务,银行转账及货物进出库功能。分享给大家供大家参考,具体如下:1. 转账业务转账必须执行2个sql语
- 一、Spring Bean 集合注入在【Spring学习笔记(三)】已经讲了怎么注入基本数据类型和引用数据类型,接下来介绍如何注入比较特殊的
- 原因:feign传值出错无法接收到传值由于是POST所以添加@RequestBody进行尝试解决:错误原因是未添加@RequestBody尝
- 在实际开发中,我们经常会需要在页面跳转的时候携带路由参数,典型的例子就是从列表到详情页的时候,需要携带详情的 id,以便详情页获取对应的数据
- 1. Mybatis JdbcType与Oracle、MySql数据类型对应列表MybatisJdbcTypeOracleMySqlJdbc