Java链表数据结构及其简单使用方法解析
作者:??行百里er?? 发布时间:2022-11-20 23:42:53
认识链表结构
单向链表
单链表在内存中的表示:
可以看到,一个链表的节点包含数据域和指向下一个节点的引用,链表最后一个节点指向null(空区域)。
我们可以根据这一定义,用Java语言表示一下单向链表的结构:
public class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
在链表的结构中,有数据域value,以及一个指向下一个节点的引用next。
TIP:这里的value还可以定义成泛型的。
双向链表
我们再来看一下双向链表的结构:
双向链表中的节点有数值域,和指向它前一个节点的引用以及指向它后一个节点的引用,据此我们可以定义出
双向链表的结构:
public class DoubleNode {
public int value;
public DoubleNode pre;
public DoubleNode next;
public DoubleNode(int value) {
this.value = value;
}
}
加深对链表结构的理解
实现单向和双向链表的反转
说明:
对于一个链表如图所示:
反转的意思是,将原来链表上的节点指针指向反转,原来的指向是:a -> b -> c -> d -> null,变成现在的指向:d -> c -> b -> a -> null,
即反转后的结构如图所示:
这个题目不难,我们转换一下指针的指向就行了。
设计这样一个函数,函数的过程是调整链表各节点的指针指向,那么这个函数的要素有:
返回值是链表的新的头结点,这样能保证函数执行完,原链表变成一个有新的头结点的链表
需要传入一个链表,用头结点表示
解题技巧:定义两个Node引用辅助我们反转指针指向。
代码实现:
public static Node reverseNode(Node head) {
Node pre = null;
Node next = null;
//最终让head指向null
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
我们来模拟一下这个函数的执行过程。
链表原始状态:
方法开始执行,此时 head.next
不为空,所以,执行如下步骤:
next = head.next:让next指向head(当前节点)的下一个节点,即b
head.next = pre:让当前节点的下一个节点指向pre,即null
此时当前节点从原来指向b,改为指向null。
pre = head:让pre指向当前节点
head = next:让当前节点指向next,相当于移动head节点,直到将head节点移动到原来tail节点的位置
第一次循环执行结束,此时 head
为b,不是null,所以继续循环,执行流程:
此时 head
为c,不是null,所以继续循环,执行流程如下:
同理,此时 head 为d,不是null,继续循环:
这是就完成了单链表的反转步骤。
有了单链表反转的经验,我们很容易就能实现双向链表的反转,代码如下:
public DoubleNode reverseDoubleNode(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
//操作(移动)当前节点
head.next = pre;
head.pre = next;
pre = head;
head = next;
}
return pre;
}
实现把链表中给定的值都删除
题如:给定一个单链表头节点head,以及一个整数,要求把链表中值为给定整数的节点都删除。
实现思路:
要实现的函数需要给我传一个头节点以及给定的数值,头节点确定链表。func(Node head, int num)。
函数给不给返回值,返回值是什么?试想,针对链表
3 -> 5 -> 4 -> 3 -> 4 -> 5
,假如要删除4,那么新链表就是3 -> 5-> 3 -> 5
,头节点仍然是原来的节点3;而如果要删除值为3的节点呢,删除后就是5 -> 4 -> 4 -> 5
,头节点变了。因此,我们要设计的这个函数需要返回新链表的头节点。上述分析得知,需要返回新链表的头节点,因此也就是要返回第一个不是给定值的节点(因为给定值的节点都要被删除掉)。
//head移动到第一个不需要删除的位置:边界条件
while (head != null) {
if (head.value != num) {
break;
}
//head右移
head = head.next;
}
//跳出循环之后,head的情况:
//1. head = null,这种情况是链表中的值全部是给定值,全删了
//2. head != null
// 中间操作
//最终返回head:第一个不是给定值的节点
return head;
head移动到第一个不需要删除的位置后,head若为null,表示所有节点都删除了,直接返回就可以了;若head不为null,借助两个辅助变量Node pre和cur,从head处开始往next走,遇到给定值就跳过。
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
这一执行过程图解如下:
通过上述分析,写出完整实现代码:
public static Node remove (Node head, int num) {
while (head != null) {
if (head.value != num) {
break;
}
head = head.next;
}
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
小结
针对链表这种数据结构进行了一些简单的分析,通过两个例子熟悉了链表的结构。
针对链表的操作,需要注意的就是指针指向以及边界问题,后续关于链表的算法还会遇到。
来源:https://juejin.cn/post/7116350143703547935


猜你喜欢
- 最近因为用的发送邮件的地方,就查询了资料,总结以下几个方法1、利用新浪邮箱发送2、利用公司邮箱发送3、利用CDO发送,这种方式要引用Inte
- 双向链表(Doubly linked list)什么是双向链表?双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直
- AutoCompleteTextView是实现动态匹配输入内容的一种输入框(EditText),如输入“and”时,会提示“Android”
- 前言上一节我们说到从HttpWebHandlerAdapter的handle方法说起到DispatcherHandler的调用流程那么Htt
- 在Java解析XML文件的过程中,有时需要获取符合某些特定条件的节点,以下是实现代码。import javax.xml.xpath.XPat
- 正在编译...1>Ipv4IPv6traceroutesrc.cpp1>d:\研究生\c++\study\test\test\i
- 本文所述实例为使用伪随机数进行用户密码加密,这段代码为核心部分主要代码,需要配合其它的程序实现,感兴趣的读者可以自己进一步加以完善,不费话了
- 昨天下午快下班的时候,无意中听到公司两位同事在探讨批量向数据库插入数据的性能优化问题,顿时来了兴趣,把自己的想法向两位同事说了一下,于是有了
- 1.需在jsp页面引入头文件:<%@ taglib prefix="form" uri="http://
- 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。代码public cla
- 在混淆编译之前,我的程序可以正常运行,混淆编译时,报告如下错误: Error:Execution failed for task ‘:gvi
- 以下实例演示了如何使用 retainAll () 方法来计算两个数组的交集:Main.java 文件:import java.util.Ar
- ReadWriteLock 和 ReentrantReadWriteLock介绍ReadWriteLock,顾名思义,是读写锁。它维护了一对
- 前言poi的解析方式是dom解析,把结果一次都读入内存操作,这样的操作平时是不会有问题的,但是并发量上来的时候就会出现OOM,EasyExc
- 前言最近在学习安卓开发的时候遇到了一个问题,使用Android Studio在为Button设置背景颜色的时候发现设置好后却在运行 * 上失
- 基本步骤三数取中在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。在此我们采用三数取中法,也就是取左端、中间
- 从接收输入值说起在日常的开发应用中,有时候需要直接接收外部设备如键盘等的输入值,而对于这种数据的接收方式,我们一般有三种方法:字节流读取,字
- 前言首先,啊,先简单介绍一下优先队列的概念,学数据结构以及出入算法竞赛的相信都对队列这一数据结构十分熟悉,这是一个线性的数据结构.针对队列这
- 前言本文主要介绍的是关于CentOS 7配置自定义JDK的方法教程,分享出来供大家参考学习,下面来一起看看详细的介绍:配置教程由于选择的是C
- 一.总体设计1.寻找规律,公式化的生成坐标系。2.将生成坐标系的关键参数设置为可自定义,从而可变的可以生成自己想要的坐标系。3.将需要绘制的