Java数据结构之单链表详解
一、图示
二、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向、双向
带头、不带头
循环、非循环
今天，我们实现的是一个 单向 无头 非循环的链表。
下面是此链表的结构组成。
三、单链表的实现
（1）定义一个节点类型
我们创建一个 ListNode 的类作为节点类型，那么我们如何定义成员属性呢？
通过上面的结构分析，我们需要定义两个成员变量 val --作为该节点的存储的数值， next – 保存下一个节点的地址/引用。
同时定义之后，他们的默认值为 0 ，null ，所以要想赋予这个节点数值，要写一个构造方法去首先保存数值。
这里我们提供了两个构造方法，一个是实现提供数值的节点，另一个是没有提供数值的节点，方便我们之后使用。
之后我们在 MyListNode 的类中实现单链表的各种方法。
（2）头插法
以上述结构为例，这个单链表没有专门的傀儡节点来充当头节点，首个节点就定义为头节点，所以头插法，就是我们定义一个节点，插在这个链表的最前面，作为新的 head。
代码实现：
1.定义一个插入的节点
ListNode cur = new ListNode(2);
此时我们就创建了一个val 为2 的节点。
2.插在头节点的前面
这里分两种情况，
第一次插入节点
不是第一次插入节点
头插之后的结构：
代码实现：
（3）尾插法
和头插法类似，同样插入一个节点，在链表的最后。
这里插入也分为两种情况
第一次插入节点
不是第一次插入节点
代码实现：
（4）根据下标插入节点
第一个数据节点为0号下标，任意位置插入节点。
还以上面的链表为例，我们想将新的节点插入到2 号位置
如果想插到2号位置，我们需要改变原来的 1号位置节点和2号位置节点的相关属性。
思路实现：
1.先判断传入的 index 下标位置是否合法
2.如果传入的index==0，头插法
3.如果传入的index==sizeof(),尾插法
4.如果 sizeof() > index > 0 在链表中间插入,我们首先要找到 index-1 位置的节点 prev
查找 index-1
修改 prev节点的属性 以及 新节点的属性
node.next = prev.next
prev.next = node;
代码实现过程
（5）查找关键字
以上面的链表为例，我们现在要查找这个链表中是否出现 val=20 的节点，如果存在，那么返回true，如果不存在，则返回 false.
遍历链表，走过每一个节点，如果 cur.val == key，则 return ture ，遍历完后还未找到 key，那么return false.
（6）删除第一次出现的关键字
思路实现：
代码实现：
（7）得到单链表的长度
（8）单链表打印展示
不能是this.head.next != null 这样写 最后一个节点是不能被打印的
（9）节点的回收
节点的回收有两种方式：
1.暴力法
直接将head 置空
2. 挨个置空
遍历单链表，将每一个节点的next都置为 null.
四、完整代码的展示
到此这篇关于Java数据结构之单链表详解的文章就介绍到这了,更多相关Java单链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Java单链表的简单操作实现教程
前言 用Java实现单链表的简单操作,阅读本文和上一篇文章体会Java中类与C++中结构体指针的区别 提示:以下是本篇文章正文内容,下面案例可供参考 一.基本实现思路 构造结点类 构造链表类 具体测试实现 二.代码实现 1.定义结点类 package list.test01; /* *定义结点类 */ public class Node { private int data; public Node next; public Node(int data) { this.data = data;
-
Java 8实现任意参数的单链表
本文实例为大家分享了Java 8实现任意参数的单链表,供大家参考,具体内容如下 1.实现功能 1)add():链表末尾添加元素: 2)pop():移除链表尾部元素: 3)insert():指定索引处添加元素: 4)delete():指定索引处删除元素: 5)getSize():获取链表当前长度: 6)display():展示链表当前元素. 2.代码 package DataStructure; /** * @author: Inki * @email: inki.yinji@qq.com * @
-
Java单链表反转图文教程
前言 最近在回顾链表反转问题中,突然有一些新的发现和收获,特此整理一下,与大家分享
-
Java 单链表数据结构的增删改查教程
我就废话不多说了,大家还是直接看代码吧~ package 链表; /** * *1)单链表的插入.删除.查找操作: * 2)链表中存储的是int类型的数据: **/ public class SinglyLinkedList { private Node head = null; //查找操作 public Node findByValue(int value){ Node p = head; //从链表头部开始查找 while(p.next != null && p.data != va
-
用JAVA实现单链表，检测字符串是否是回文串
一.需求 使用JAVA实现单链表,使用单链表检测字符串是否是回文串 二.需求分析 回文串最重要的就是对称,那么最重要的问题就是找到那个中心,用快指针每步走两格,当他到达链表末端的时候,慢指针刚好到达中心,慢指针在遍历过程中(快指针到达末端时)把走过的节点进行反向操作,此时从中位点分为前后两部分,此时前半部分的指针开始往回指(取next的时候,取的是前一个节点),而慢指针继续向前,跟前半部分的数据依次进行比对,当慢指针扫完整个链表,就可以判断这是回文串,否则就提前退出,同时在前半部分往回遍历的过程
-
Java实现单链表反转的多种方法总结
对于单链表不熟悉的可以看一下基于Java实现单链表的增删改查 一.原地反转 1.新建一个哨兵节点下一结点指向头结点 2.把待反转链表的下一节点插入到哨兵节点的下一节点 反转之前的链表:1–>2–>3–>4>–>5 加入哨兵节点:dummp–>1–>2–>3–>4>–>5 原地反转: 定义:prev=dummp.next; pcur=prev.next; prev.next=pcur.next; pcur.next=dummp.next; d
-
java 实现单链表逆转详解及实例代码
java 实现单链表逆转详解 实例代码: class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.o
-
Java单链表的实现代码
下面是小编给大家分享的一个使用java写单链表,有问题欢迎给我留言哦. 首先定义一个Node类 public class Node { protected Node next; //指针域 public int data;//数据域 public Node( int data) { this. data = data; } //显示此节点 public void display() { System. out.print( data + " "); } } 接下来定义一个单链表,并实现
-
Java实现单链表翻转实例代码
Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node
-
java实现简单单链表
本文实例为大家分享了java实现简单单链表的具体代码,供大家参考,具体内容如下 一.定义: 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(相当于JAVA中的引用,指示后继元素存储位置,),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据. 二.结构: 如图所示,data就是当前节点的数据,next是指针,指针存放的是内存地址,是当前结点的下一结点内存地址,顺着这个地址就能找
-
Java实现单链表的各种操作
主要内容: 单链表的基本操作 删除重复数据 找到倒数第k个元素 实现链表的反转 从尾到头输出链表 找到中间节点 检测链表是否有环 在不知道头指针的情况下删除指定节点 如何判断两个链表是否相交并找出相交节点 直接上代码,就是这么奔放~~~ package pers.ty.$1101datastructure; import java.util.Hashtable; /** * @author Administrator * 实现单链表的基本操作,增加删除节点.排序.打印.计算长度 */ publi
-
Java数据结构之简单链表的定义与实现方法示例
本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点
-
java实现单链表增删改查的实例代码详解
package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node&l
-
java 数据结构单链表的实现
java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n
-
Java如何实现单链表的增删改查
一.新建学生节点类 Stu_Node节点包含: 学号:int num; 姓名:String name; 性别:String gender; 下一个节点:Stu_Node next; 为了便于打印节点内容需要重写toString方法 class Stu_Node{ int num; String name; String gender; Stu_Node next; @Override public String toString() { return "Stu_Node{" + &qu