数据结构:双向链表(1)

双向链表

  • 基本思想
  • 大体结构
  • 增加
    • 修改MyList
    • 测试
      • 遍历
        • 修改MyList
  • 删除
    • 修改MyList
    • 测试

基本思想

双向链表与单向链表大同小异,只不过双向链表还有个节点指向最后一个节点

大体结构

新建工程,结构如下
在这里插入图片描述

package list;
public class MyList {
	long size;
	Node firstNode;
	Node lastNode;
	public long getSize() {
		return size;
	}
	public Node getFirstNode() {
		return firstNode;
	}

	public void setFirstNode(Node firstNode) {
		this.firstNode = firstNode;
	}

	public Node getLastNode() {
		return lastNode;
	}

	public void setLastNode(Node lastNode) {
		this.lastNode = lastNode;
	}
	@Override
	public String toString() {
		return "MyList [size=" + size + ", firstNode=" + firstNode + ", lastNode=" + lastNode + "]";
	}
	public class Node{
		private int value;
		private Node preNode;
		private Node nextNode;
		private Node() {
			
		}
		public Node(int value)
		{
			this.value = value;
		}
		 
		private void setValue(int value) {
			this.value = value;
		}
		public int getValue() {
			return value;
		}
		public Node getPreNode() {
			return preNode;
		}
		private void setPreNode(Node preNode) {
			this.preNode = preNode;
		}
		public Node getNextNode() {
			return nextNode;
		}
		private void setNextNode(Node nextNode) {
			this.nextNode = nextNode;
		}
		@Override
		public String toString() {
			return "Node [value=" + value + "]";
		}	
	}
}

增加

修改MyList

public void setFirstNode(Node firstNode) {
		if(this.size == 0)
		{
			//如果没有节点,添加进去一个节点,而且首尾全部指向这个节点
			this.firstNode = firstNode;
			this.lastNode = firstNode;
			this.size++;
		}
		else {
			//如果有节点,替换掉原来的第一个节点
			Node currNode = this.firstNode;
			if(this.size == 1)
			{
				//如果只有一个节点,最后一个节点应该也指向firstNode
				this.lastNode = firstNode;
				this.firstNode = firstNode;
			}
			else {
				this.firstNode = firstNode;
				this.firstNode.setPreNode(currNode.getPreNode());
				this.firstNode.setNextNode(currNode.getNextNode());
			}
		}
	}
	public void setLastNode(Node lastNode) {
		if(this.size == 0)
		{
			//如果没有节点,添加进去一个节点,而且首尾全部指向这个节点
			this.firstNode = lastNode;
			this.lastNode = lastNode;
			this.size++;
		}
		else {
			//如果有节点,替换掉原来的第最后个节点
			Node currNode = this.lastNode;
			if(this.size == 1)
			{
				//如果只有一个节点,第一个一个节点应该也指向firstNode
				this.firstNode = lastNode;
				this.lastNode = lastNode;
			}
			else {				
				this.lastNode = lastNode;
				this.lastNode.setPreNode(currNode.getPreNode());
				this.lastNode.setNextNode(currNode.getNextNode());
			}
		}
	}
	public void addNode(Node node)
	{
		if(this.size == 0)
		{
			//如果没有节点,首尾全部指向这个节点
			this.firstNode = node;
			this.lastNode = node;
		}
		else {
			//如果有节点,则最后一个节点应该指向新加入的节点
			Node currNode = this.firstNode;
			while(currNode.getNextNode()!=null)
			{
				currNode = currNode.getNextNode();
			}
			currNode.setNextNode(node);
			node.setPreNode(currNode);
			this.lastNode = node;
		}
		this.size++;
	}

测试

测试1:本身没有节点,使用setFirstNode

@Test
	void testSetFirstNode1() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		myList.setFirstNode(node1);
		System.out.println(myList);
	}

结果
在这里插入图片描述
测试1:本身没有节点,使用addNode

@Test
	void testAddNode1() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		myList.addNode(node1);
		System.out.println(myList);
	}

结果
在这里插入图片描述

遍历

修改MyList

public String queryAll() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append('{');
		Node currNode = this.firstNode;
		while(currNode != null)
		{
			stringBuilder.append("->");
			stringBuilder.append(currNode.getValue());
			currNode = currNode.getNextNode();
		}
		stringBuilder.deleteCharAt(1);
		stringBuilder.deleteCharAt(1);
		stringBuilder.append('}');
		return stringBuilder.toString();
	}

测试3:使用addNode添加第一个节点,setFirstNode替换掉

@Test
	void testAddAndSetFirst() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);
		myList.addNode(node1);
		myList.setFirstNode(node2);
		System.out.println(myList);
	}

结果
在这里插入图片描述
测试4:使用setFirstNode设置第一个节点,addNode添加节点

@Test
	void testSetFirstAndAdd() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);
		myList.setFirstNode(node1);
		myList.addNode(node2);
		System.out.println("链表"+myList);
		System.out.println(myList.queryAll());
	}

结果
在这里插入图片描述
测试5 使用addNode添加第一个节点,setLastNode替换最后一个节点

@Test
	void testAddAndSetLast() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);
		myList.addNode(node1);
		System.out.println("替换前"+myList);
		myList.setLastNode(node2);
		System.out.println("替换后"+myList);
	}

结果
在这里插入图片描述
测试6:使用setFirstNode添加第一个节点,setLastNode替换最后一个节点

@Test
	void testsetFirstAndSetLast() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);
		myList.setFirstNode(node1);
		System.out.println("替换前"+myList);
		myList.setLastNode(node2);
		System.out.println("替换后"+myList);
	}
```![在这里插入图片描述](https://img-blog.csdnimg.cn/20200701120016971.png)
结果
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200701115845994.png)
测试7:当前有两个节点,使用setLastNode替换最后一个节点
```javascript
@Test
	void testSetLast() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);
		Node node3 = new MyList().new Node(3);
		myList.setFirstNode(node1);
		myList.addNode(node2);
		System.out.println("替换前"+myList);
		myList.setLastNode(node3);
		System.out.println("替换后"+myList);
	}

结果

测试8:当前没有节点,使用setLastNode添加最后一个节点

@Test
	void testSetLasttNode1() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		myList.setLastNode(node1);
		System.out.println(myList);
	}

结果
在这里插入图片描述
测试9:当前有节点,使用setLastNode添加最后一个节点

@Test
	void testSetLasttNode2() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);	
		myList.setFirstNode(node1);
		System.out.println("替换前"+myList);
		myList.setLastNode(node2);
		System.out.println("替换后"+myList);
	}

结果
在这里插入图片描述

删除

同单向链表一致,不适合做修改以及查询操作,现在还是只删除第一个节点以及最后一个节点。

修改MyList

public void deleteFirstNode() {
		if(this.size == 0) return;
		else if(this.size == 1) 
		{
			this.firstNode = null;
			this.lastNode = null;
		}
		else {
			Node currNode = this.firstNode.getNextNode();
			this.firstNode = currNode;
		}
		this.size--;
	}
	public void deleteLastNode() {
		if(this.size == 0) return;
		else if(this.size == 1) 
		{
			this.firstNode = null;
			this.lastNode = null;
		}
		else {
			Node currNode = this.lastNode.getPreNode();
			this.lastNode = currNode;
		}
		this.size--;
	}

测试

测试1:没有节点使用deleteFirstNode

@Test
	void testdeleteFirstNode() {
		MyList myList = new MyList();
		myList.deleteFirstNode();
	}

测试2:没有节点使用deleteLastNode

@Test
	void testdeleteLastNode() {
		MyList myList = new MyList();
		myList.deleteLastNode();
	}

测试3:有一个节点使用deleteFirstNode

@Test
	void testdeleteFirstNode2() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		myList.setFirstNode(node1);
		System.out.println("删除前"+myList);
		myList.deleteFirstNode();
		System.out.println("删除后"+myList);
	}

结果
在这里插入图片描述
测试4:有一个节点使用deleteLastNode

@Test
	void testdeleteLasttNode2() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		myList.setFirstNode(node1);
		System.out.println("删除前"+myList);
		myList.deleteLastNode();
		System.out.println("删除后"+myList);
	}

结果
在这里插入图片描述
测试5:有两个节点使用deleteFirstNode

@Test
	void testdeleteFirstNode3() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);
		myList.setFirstNode(node1);
		myList.addNode(node2);
		System.out.println("删除前"+myList);
		myList.deleteFirstNode();
		System.out.println("删除后"+myList);
	}

结果
在这里插入图片描述
测试6:有两个节点使用deleteLastNode

@Test
	void testdeleteLasttNode3() {
		MyList myList = new MyList();
		Node node1 = new MyList().new Node(1);
		Node node2 = new MyList().new Node(2);
		myList.setFirstNode(node1);
		myList.addNode(node2);
		System.out.println("删除前"+myList);
		myList.deleteLastNode();
		System.out.println("删除后"+myList);
	}

结果
在这里插入图片描述

热门文章

暂无图片
编程学习 ·

leetcode-341-扁平化嵌套列表迭代器-java

题目及测试package pid341; /* 扁平化嵌套列表迭代器给你一个嵌套的整型列表。请你设计一个迭代器,使其能够遍历这个整型列表中的所有整数。列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。示例 1:输入: [[1,1],2,[1,1]] 输出: […
暂无图片
编程学习 ·

SQL Server—游标(是什么?声明、打开、检索、关闭、释放)

目录游标是什么?如何创建一个游标?操作游标的四个步骤?如何判断游标的提取状态?关闭游标就可以了为什么还要释放呢?他们有什么区别?游标是什么? 是一种数据访问机制,它允许用户单独的操作数据行,而不是对整个行集进行操作。用户可以通过单独处理每一行逐条手机信息并对…
暂无图片
编程学习 ·

NLP 任务中有哪些巧妙的 idea?

文章目录1. 分布式假设(Distributional Hypothesis)2. 词袋模型(Bag-of-Words)3. 潜在语义分析(Latent Semantic Analysis)4. 概率主题模型(Probabilistic Topic Models )5. 基于BMES的中文分词或基于BIO的NER/Chunking6. 基于PageRank的TextRank转载来源:https://www…
暂无图片
编程学习 ·

springboot整合redis之史上最详步骤

springboot整合redis之史上最详步骤前言一、了解Redis一、搭建Redis环境1.Redis安装2.Redis可视化工具安装与连接二、SpringBoot整合Redis1.新建SpringBoot项目2.SpringBoot集成redis3.使用RedisTemplate操作Redis3.1实体类User3.2 工具类RedisUtil3.3 配置类RedisConfig3.4 Us…
暂无图片
编程学习 ·

自定义控件三部曲之动画篇(四)——ValueAnimator基本使用

一、概述前面,我写过几篇有关Animation的文章,讲解了传统的alpha、scale、translate、rotate的用法及代码生成方法。其实这三篇文章讲的所有动画效果叫做Tween Animation(补间动画)在Android动画中,总共有两种类型的动画View Animation(视图动画)和Property Animator(属性…
暂无图片
编程学习 ·

jackson的学习记录

Jackson对于date的反序列化只支持几种,如果不符合默认格式则会报一下错误 org.codehaus.jackson.map.JsonMappingException: Can not construct instance of java.util.Date from String value 2012-12-12 12:01:01: not a valid representation (error: Can not parse date &…
暂无图片
编程学习 ·

Java字节码增强探秘

1.字节码1.1 什么是字节码?Java之所以可以“一次编译,到处运行”,一是因为JVM针对各种操作系统、平台都进行了定制,二是因为无论在什么平台,都可以编译生成固定格式的字节码(.class文件)供JVM使用。因此,也可以看出字节码对于Java生态的重要性。之所以被称之为字节码,…
暂无图片
编程学习 ·

nginx从下载到部署全过程(Linux)

导航NGINX官网下载NGINX安装环境解压,编译,安装启动及测试NGINX官网以下列举了三个网址,分别是:NGINX官网,下载网址及官方文档。官方网站:http://nginx.org/下载网址:http://nginx.org/en/download.html官方文档:http://nginx.org/en/docs/ 下载NGINX 通过官方下载地址…
暂无图片
编程学习 ·

JQuery——实现隔行换色

基础页面显示页面代码 <!DOCTYPE html> <html lang="en"> <head><meta charset="UTF-8"><title>隔行换色</title><script src="jquery-3.5.1.js"></script><style>table{margin: auto;wi…
暂无图片
编程学习 ·

啥是智慧社区-百度人脸识别

还记得前几年大家常说的看“脸”的时代吗?现如今回家必须得看脸了,人脸识别助力智慧社区管理升级,以前我们只能在电影里看到了,刷脸进出小区,刷脸开锁等在现实中已经实现了,那使用了人脸识别的智慧社区到底是个啥?下面AI人工智能带大家一探究竟。1、人工智能赋予美好生活…
暂无图片
编程学习 ·

java常用面试题——笔试选择题解析

1.以下关于 abstract 关键字的说法,正确的是(D)。 A.abstract 可以与 final 并列修饰同一个类。 B.abstract 类中不可以有 private 的成员。 C.abstract 类中必须全部是 abstract 方法。 D.abstract 方法必须在 abstract 类或接口中。解析: final的类不能被重写和继承;而a…
暂无图片
编程学习 ·

前端学习-javascript-(1)预览

组成 DOM—Document Object Model 文档对象模型—操作返回到文档(界面) doucument对象 ———————————————— BOM—Browser Object Model 浏览器对象模型—操作浏览器本身 window对象 ———————————————— ECMAScript 解释器 ———————————…
暂无图片
编程学习 ·

整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构

前言没有必要过度关注本文中二叉树的增删改导致的结构改变,规则操作什么的了解一下就好,看不下去就跳过,本文过多的XX树操作图片纯粹是为了作为规则记录,该文章主要目的是增强下个人对各种常用XX树的设计及缘由的了解,也从中了解到常用的实现案例使用XX树实现的原因。数据…
暂无图片
编程学习 ·

在使用R和Rstdio的常见问题

在Rstdio里无法画图有两种方法:一是使用代码 dev.new() 新建一个绘图窗口(我觉得这个方法好,因为在我的plots窗口画出来的图比例是变形的);二是换一个系统缓存目录,详细教程可以自行在网上寻找。在R里无法安装包可以像上面的方法二一样,换个缓存目录,或者在缓存目录里找…
暂无图片
编程学习 ·

python学习笔记——持久化-文件

open 函数open 函数负责打开文件,带有很多参数 第一个参数:必须有,文件的路径和名称 mode:表明文件用什么方式打开r:以只读方式打开 w:写方式打开,会覆盖以前的内容 x:创建方式打开,如文件已经存在,报错 a:append 方式,以追加的方式对文件内容进行写入 b:binary 方…