首页 > 编程语言 >日撸Java三百行(day13:链表)

日撸Java三百行(day13:链表)

时间:2024-08-05 20:57:50浏览次数:13  
标签:Node 结点 Java tempNode next 链表 day13 null

目录

一、链表的基础知识

二、链表的代码实现

1.链表创建

2.链表遍历

3.链表定位查找

4.链表插入

5.链表删除

6.数据测试

7.完整的程序代码

总结


一、链表的基础知识

在之前顺序表的学习中,我们其实提到过链表。链表它是线性表在不同的物理存储方式下派生出来的,链表不像顺序表,它的数据元素在物理存储结构上并不连续,其数据元素的逻辑顺序是通过链表中的引用链接次序实现的,总结一下就是链表在逻辑上连续,在物理上不连续。

链表中的每一个元素称为结点,因此链表其实是由一系列结点组成的。而每个结点包括两个部分:一个是存储数据元素的数据域data,另一部分则是存储下一个结点地址的指针域next,通过这个指针域我们就可以轻松访问到当前结点的下一个结点,直到某个结点的next域为null。这样,就相当于把所有的结点都串联起来,进行链式访问,所以叫做“链表”。图解如下:

在实际情况中,链表可以分为:

  • 单向or双向

  • 循环or非循环

  • 带头or不带头

组合起来,一共就有8种链表。 

二、链表的代码实现

与顺序表一样,链表也可以进行初始化、查找、插入、删除等操作,下面我们通过java来实现。

1.链表创建

在day11(顺序表一)中,我们学习了类和对象的相关知识,包括如何定义一个类、如何创建对象、如何使用对象等,基于此,我们在定义的链表类中再创建一个结点类,同时定义该结点类的成员变量(data、next)和成员方法,如下:

public class LinkedList {

	/**
	 * An inner class.
	 */
	class Node {
		/**
		 * The data.
		 */
		int data;

		/**
		 * The reference to the next node.
		 */
		Node next;

		/**
		 ******************* 
		 * The constructor
		 * 
		 * @param paraValue
		 *            The data.
		 ******************* 
		 */
		public Node(int paraValue) {
			data = paraValue;
			next = null;
		}// Of the constructor
	}// Of class Node

在上述代码中,我们有两个需要注意的问题:

  • 这里的结点类是一个内部类inner class,根据链表的基本概念,我们知道链表是由若干个结点组成,而结点又由data域和next域组成,所以其符合内部类的定义(如果外部类是由若干完整的类组成,那么这些若干完整的类就可以定义为内部类)
  • 在定义成员变量next时,使用的是Node引用,这是因为next所指向的是下一个结点的地址,而结点始终是Node类型,所以我们用Node来定义next

然后,我们再定义一个头结点,并通过new为其分配内存空间,代码如下:

    /**
	 * The header node. The data is never used.
	 */
	Node header;

	/**
	 *********************
	 * Construct an empty linked list.
	 *********************
	 */
	public LinkedList() {
		header = new Node(0);
		//header.next = null; //Redundant
	}// Of the first constructor

为什么这里要单独把头结点header拿出来定义呢?一方面是因为header是链表的特征,而不是结点的;另一方面是因为头结点的数据域data是无效的,不存放任何数据元素。

2.链表遍历

与顺序表一样,我们同样可以重写toString()方法来遍历输出链表,如下:

    /**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (header.next == null) {
			return "empty";
		} // Of if

		Node tempNode = header.next;
		while (tempNode != null) {
			resultString += tempNode.data + ", ";
			tempNode = tempNode.next;
		} // Of while

		return resultString;
	}// Of toString

根据之前学过的如何使用一个对象,可以知道if语句中的header.next(对象名.成员变量)即表示头结点后的下一个结点的地址,如果其等于null,那么该链表显然为空,所以我们需要提前排除这种情况;排除后,我们将头结点后的下一个结点定义为tempNode(结点始终是Node类型,所以用Node定义);再通过while循环进行迭代,其中tempNode.data(对象名.成员变量)表示该结点所存放的数据,而tempNode = tempNode.next;则实现了对象的迭代,相当于由指向前一个结点移动为指向下一个结点,即可访问下一个结点的相关数据,这其实与数组中索引值递增的作用有点类似;最后通过循环条件tempNode != null来控制,当tempNode = null即到达最后一个结点时结束。

3.链表定位查找

其实链表定位查找方法创建的大体思路和顺序表没有什么差别,都是通过循环遍历,将现有的数据元素与目标元素一一比较,最大的不同就是遍历方式发生了改变,代码如下:

    /**
	 *********************
	 * Locate the given value. If it appears in multiple positions, simply
	 * return the first one.
	 * 
	 * @param paraValue
	 *            The given value.
	 * @return The position. -1 for not found.
	 *********************
	 */
	public int locate(int paraValue) {
		int tempPosition = -1;

		Node tempNode = header.next;
		int tempCurrentPosition = 0;
		while (tempNode != null) {
			if (tempNode.data == paraValue) {
				tempPosition = tempCurrentPosition;
				break;
			} // Of if

			tempNode = tempNode.next;
			tempCurrentPosition++;
		} // Of while

		return tempPosition;
	}// Of locate
  • 第一步,我们同样设置一个非法值-1,它的作用就是当在链表中没有找到目标元素时(包括链表为空、链表不为空但遍历完后没有找到目标元素这两种情况),返回非法值-1
  • 第二步,定义头结点后的下一个结点,并定义此结点的下标为0(因为前面说过头结点的data域不存放数据,所以头结点后的下一个结点相当于是第一个有效的结点,所以将其下标定为0)
  • 第三步,利用while循环进行遍历,将链表中的数据元素tempNode.data与目标元素paraValue一一比对:如果相等就将此时数据元素的下标赋给tempPosition,然后通过break语句跳出循环,再返回tempPosition的值;如果不等就通过tempNode = tempNode.next进行迭代,继续遍历

4.链表插入

由于链表在物理存储结构上不一定连续,所以它不用像顺序表那样通过大段元素移动覆盖的方式间接完成插入、删除等操作。链表的插入只需要创建一个新的结点,然后修改该新结点插入位置前后的引用链接次序即可,图解如下(图源网络):

根据图示,要完成链表插入,大体上可以分为三步:

  • 第一步,创建一个新的结点
  • 第二步,找到指定插入位置的前一个结点
  • 第三步,修改该指定插入位置前后的指针指向

代码如下: 

    /**
	 *********************
	 * Insert a value to a position. If the list is already full, do nothing.
	 * 
	 * @param paraPosition
	 *            The given position.
	 * @param paraValue
	 *            The given value.
	 * @return Success or not.
	 *********************
	 */
	public boolean insert(int paraPosition, int paraValue) {
		Node tempNode = header;
		Node tempNewNode;

		for (int i = 0; i < paraPosition; i++) {
			if (tempNode.next == null) {
				System.out.println("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = tempNode.next;
		} // Of for i

		// Construct a new node.
		tempNewNode = new Node(paraValue);

		// Now link them.
		tempNewNode.next = tempNode.next;
		tempNode.next = tempNewNode;

		return true;
	}// Of insert

第一步没什么好说的,直接创建即可;第二步中,我们需要提前考虑指定插入位置是否合法,这里将tempNode.next == null是否成立作为判断条件;确定插入位置合法之后,我们通过tempNode = tempNode.next;进行迭代,再利用i < paraPosition控制循环,使得到达指定插入位置的前一个结点;而第三步的修改链接次序,参考上图的解释就好。

5.链表删除

和链表插入同样的思想,链表删除也是通过修改链接次序来实现,不过链表删除还要更简单一点,只需要删掉目标位置前后的链接,再增加目标位置前一个结点与目标位置后一个结点之间的链接即可,图解如下(图源网络):

由于链表删除不需要创建新的结点,所以只需要两步:

  • 第一步,找到目标位置的前一个结点
  • 第二步,修改目标位置前后的链接次序

代码如下:

    /**
	 *********************
	 * Delete a value at a position.
	 * 
	 * @param paraPosition
	 *            The given position.
	 * @return Success or not.
	 *********************
	 */
	public boolean delete(int paraPosition) {
		if (header.next == null) {
			System.out.println("Cannot delete element from an empty list.");
			return false;
		} // Of if

		Node tempNode = header;

		for (int i = 0; i < paraPosition; i++) {
			if (tempNode.next.next == null) {
				System.out.println("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = tempNode.next;
		} // Of for i

		tempNode.next = tempNode.next.next;

		return true;
	}// Of delete

在执行第一步之前,我们需要考虑两个问题,第一个问题是链表是否为空,第二个问题是目标位置是否合法。对于第一个问题,直接用一个if语句进行判断即可,当header.next = null时,头节点的后一个节点的地址为null,也就是第一个有效结点的地址为null,此时链表显然为空,所以返回false;而第二个问题,需要注意与链表插入不一样,此时的判断条件不再是tempNode.next == null,而是tempNode.next.next == null。解决以上两个问题后,就可以利用tempNode = tempNode.next;进行遍历,直到找到目标位置的前一个结点。

对于第二步的修改链接次序,只需要令tempNode.next = tempNode.next.next;即可,这里的temp.next.next其实就是目标位置后一个结点的地址,将该地址赋给tempNode.next(即目标位置前一个结点的next域),这样就把目标位置前一个结点与目标位置后一个结点链接起来了,也就实现了链表删除操作。

6.数据测试

方法创建完成后,我们来进行一些数据测试,如下:

    /**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		LinkedList tempFirstList = new LinkedList();
		System.out.println("Initialized, the list is: " + tempFirstList.toString());

		for (int i = 0; i < 5; i++) {
			tempFirstList.insert(0, i);
		} // Of for i
		System.out.println("Inserted, the list is: " + tempFirstList.toString());

		tempFirstList.insert(6, 9);

		tempFirstList.delete(4);

		tempFirstList.delete(2);
		System.out.println("Deleted, the list is: " + tempFirstList.toString());

		tempFirstList.delete(0);
		System.out.println("Deleted, the list is: " + tempFirstList.toString());

		for (int i = 0; i < 5; i++) {
			tempFirstList.delete(0);
			System.out.println("Looped delete, the list is: " + tempFirstList.toString());
		} // Of for i
	}// Of main

7.完整的程序代码

package datastructure.list;

/**
 * Linked list.
 * 
 * @author Xin Lin [email protected].
 */

public class LinkedList {

	/**
	 * An inner class.
	 */
	class Node {
		/**
		 * The data.
		 */
		int data;

		/**
		 * The reference to the next node.
		 */
		Node next;

		/**
		 ******************* 
		 * The constructor
		 * 
		 * @param paraValue
		 *            The data.
		 ******************* 
		 */
		public Node(int paraValue) {
			data = paraValue;
			next = null;
		}// Of the constructor
	}// Of class Node

	/**
	 * The header node. The data is never used.
	 */
	Node header;

	/**
	 *********************
	 * Construct an empty linked list.
	 *********************
	 */
	public LinkedList() {
		header = new Node(0);
		//header.next = null; //Redundant
	}// Of the first constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (header.next == null) {
			return "empty";
		} // Of if

		Node tempNode = header.next;
		while (tempNode != null) {
			resultString += tempNode.data + ", ";
			tempNode = tempNode.next;
		} // Of while

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Reset to empty. Free the space through garbage collection.
	 *********************
	 */
	public void reset() {
		header.next = null;
	}// Of reset

	/**
	 *********************
	 * Locate the given value. If it appears in multiple positions, simply
	 * return the first one.
	 * 
	 * @param paraValue
	 *            The given value.
	 * @return The position. -1 for not found.
	 *********************
	 */
	public int locate(int paraValue) {
		int tempPosition = -1;

		Node tempNode = header.next;
		int tempCurrentPosition = 0;
		while (tempNode != null) {
			if (tempNode.data == paraValue) {
				tempPosition = tempCurrentPosition;
				break;
			} // Of if

			tempNode = tempNode.next;
			tempCurrentPosition++;
		} // Of while

		return tempPosition;
	}// Of locate

	/**
	 *********************
	 * Insert a value to a position. If the list is already full, do nothing.
	 * 
	 * @param paraPosition
	 *            The given position.
	 * @param paraValue
	 *            The given value.
	 * @return Success or not.
	 *********************
	 */
	public boolean insert(int paraPosition, int paraValue) {
		Node tempNode = header;
		Node tempNewNode;

		for (int i = 0; i < paraPosition; i++) {
			if (tempNode.next == null) {
				System.out.println("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = tempNode.next;
		} // Of for i

		// Construct a new node.
		tempNewNode = new Node(paraValue);

		// Now link them.
		tempNewNode.next = tempNode.next;
		tempNode.next = tempNewNode;

		return true;
	}// Of insert

	/**
	 *********************
	 * Delete a value at a position.
	 * 
	 * @param paraPosition
	 *            The given position.
	 * @return Success or not.
	 *********************
	 */
	public boolean delete(int paraPosition) {
		if (header.next == null) {
			System.out.println("Cannot delete element from an empty list.");
			return false;
		} // Of if

		Node tempNode = header;

		for (int i = 0; i < paraPosition; i++) {
			if (tempNode.next.next == null) {
				System.out.println("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = tempNode.next;
		} // Of for i

		tempNode.next = tempNode.next.next;

		return true;
	}// Of delete

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		LinkedList tempFirstList = new LinkedList();
		System.out.println("Initialized, the list is: " + tempFirstList.toString());

		for (int i = 0; i < 5; i++) {
			tempFirstList.insert(0, i);
		} // Of for i
		System.out.println("Inserted, the list is: " + tempFirstList.toString());

		tempFirstList.insert(6, 9);

		tempFirstList.delete(4);

		tempFirstList.delete(2);
		System.out.println("Deleted, the list is: " + tempFirstList.toString());

		tempFirstList.delete(0);
		System.out.println("Deleted, the list is: " + tempFirstList.toString());

		for (int i = 0; i < 5; i++) {
			tempFirstList.delete(0);
			System.out.println("Looped delete, the list is: " + tempFirstList.toString());
		} // Of for i
	}// Of main
}// Of class LinkedList

运行结果:

总结

昨天我们讨论了顺序表,由于其底层是一段连续的物理空间,所以当想要在顺序表中的任意位置插入或删除元素时,必须通过大段元素整体后移或前移才能完成,所以效率很低,时间复杂度为O(n),针对这一问题,java引入了链表结构。链表有一个非常好的性质就是在插入、删除元素时不用移动元素,只改变引用即可,所以效率比较高。但是链表也有不足的地方,就是当需要定位查找元素时,链表只能按链接顺序依次访问数据元素,时间复杂度为O(n)。

综上所述,顺序表的优势是支持随机访问,并且查找元素比较快,而当需要频繁进行插入、删除元素操作时,链表会更为适合。

标签:Node,结点,Java,tempNode,next,链表,day13,null
From: https://blog.csdn.net/2301_80594618/article/details/140907939

相关文章

  • 【报错提示】java.lang.RuntimeException: Can't create handler inside thread
    ​报错提示遇到一个报错: java.lang.RuntimeException:Can'tcreatehandlerinsidethreadThread[OkHttphttps://a.fxltsbl.com/...]thathasnotcalledLooper.prepare() 分析 1.这个报错提示是在一个没有调用Looper.prepare()的线程中尝试创建一个Handler对象......
  • JAVA变量类型
    一个类可以包含以下类型变量:局部变量:在方法、构造方法或者语句块中定义的变量被称为局部变量。变量声明和初始化都是在方法中,方法结束后,变量就会自动销毁。成员变量:成员变量是定义在类中,方法体之外的变量。这种变量在创建对象的时候实例化。成员变量可以被类中方法、构造方法......
  • java8-常用类型(包装类,BigDecimal,Date等)
    1.包装类1.1包装类简介java语言是面向对象的语言,但是其中的八大基本数据类型不符合面向对象的特征。因此java为了弥补这样的缺点,为这八种基本数据类型专门设计了八种符合面向对象特征的的类型,这八种具有面向对象特征的类型,统称为包装类,英文单词:wrapperclass。包装类,就是......
  • java9-泛型
    1.泛型的简介1.1什么是泛型        泛型是一种特殊的数据类型。它是Java的一个高级特性。在Mybatis、Hibernate这种持久化框架,泛型更是无处不在。在这之前,不管我们在定义成员变量时,还是方法的形参时,都要规定他们的具体类型。所以提出猜想,有没有一种可能,一次声......
  • JSON parse error: Cannot deserialize instance of `java.lang.Long` out of START_O
    这个问题的实际原因就是:    后端id(Long类型)用的雪花算法生成主键id    后端生成id位:1820397662671867904    前端查询id的结果为:1820397662671868000产生的原因:    后端生成为19位,前端接受并展示,使用的类型是number类型是16位   ......
  • java计算字符数量
      publicclassCharCountExample{publicstaticvoidmain(String[]args){Stringtext="Hello,world!Howareyou?";chartargetChar='o';intcount=countChar(text,targetChar);System.out.p......
  • JAVA应用CPU跳点自动DUMP工具
    背景在做系统监控时,CPU的使用率是一个关键的指标,它反映了系统的性能稳定性以及是否存在异常情况,能帮助我们了解系统的负载情况。通过监控CPU使用率,可以判断系统是否正常运行或者是否存在性能问题。如果CPU使用率过高,可能表示系统存在资源瓶颈,需要进行优化或升级。CPU监控的难......
  • 计算机毕业设计必看必学!! 85583 springboot高校网上选课系统,原创定制程序, java、PHP
                                                  摘要本论文主要论述了如何使用JAVA语言开发一个高校网上选课系统,本系统将严格按照软件开发流程进行各个阶段的工作,采用B/S架构,面向对象编程思想进行项目开发。在引言中,......
  • 学习笔记 韩顺平 零基础30天学会Java(2024.8.5)
    P460八大Wrapper类     黄色的父类是number,黑色的是自己独立的P461装箱和拆箱     手动装箱示例:                             intn1=100;                Intergerinterger=newInterger(n1);//......
  • JavaScript 中的闭包和事件委托
    包(Closures)闭包是JavaScript中一个非常强大的特性,它允许函数访问其外部作用域中的变量,即使在该函数被调用时,外部作用域已经执行完毕。闭包可以帮助我们实现数据的私有化、封装和模块化,使代码更简洁、易读和可维护。闭包的定义简单来说,闭包是指有权访问另一个函数作......