Java与数据结构的实现:线性表(链式:带头结点的单链表)_java构建完整的带头结点单链表使其拥有插入,删除和遍历三大功能。 并通过main方法-程序员宅基地

技术标签: java  单链表  

分析:
先要满足以下基本的要求,遇到问题再做完善。

单链表的属性
      结点类:
            数据项 data
            结点类型的变量 next
      单链表类:
            结点类型的变量 head
单链表类要实现的方法
      判断链表是否为空
      清空链表
      求链表长度
      遍历链表并输出
      插入(头插,尾插,索引位置插)
      删除(头删,尾删,索引位置删)
      查找(给定元素索引,给定索引元素)
      更改(更改指定索引位置为元素值)

注意事项
1.结点类型的成员变量head永远是头节点的引用,所以不要直接对head进行操作,通过Node temp = head,对临时变量temp进行操作,不会影响到head;
2.因将链表长度存储在了头节点的数据项,所以在对链表中元素个数产生影响的方法要及时调整head.data的值。
属性设置

//结点类属性
	int data;//数据项
	Node next;//后继结点
	public Node(int data) {
    //仅能通过此构造方法生成结点对象
		this.data = data;
	}
//单链表类属性
Node head = new Node(0);//初始化头节点,并用头节点的数据项存储单链表长度

方法实现
1.判断链表是否为空:
      两种方法:
            头节点的next’属性为null则为空
            头节点的数据项data为0则为空

	public boolean isEmpty(){
    //判空
		if(head.next == null)
			return true;
		return false;
	}
	public boolean isEmpty1(){
    
		if(head.data == 0)
			return true;
		return false;
	}

2.清空链表:
      头节点的数据项data设为0,后继结点next设为null

public void clear(){
    //清空
		head.next = null;
		head.data = 0;
}

3.长度:
      返回头节点的数据项data即可

public int getLength(){
    //返回单链表长度
		return head.data;
	}

4.遍历:
      通过使用结点的后继结点next属性来一直后移即可。
      图解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public void travers(){
    //遍历
		if(head.next == null){
    
			System.out.println("当前单链表为空");
			return;
		}
		
		Node temp = head;
		
		System.out.print("[");
		while(temp.next != null){
    
			temp = temp.next;
			if(temp.next == null){
    
				System.out.println(temp.data + "]");
			}else{
    
				System.out.print(temp.data + ",");
			}
		}
	}

5.插入:(头插)
      图解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public void insertHead(int value){
    //头插
		Node node = new Node(value);
		node.next = head.next;
		head.next = node;
		
		head.data++;
	}

6.插入(尾插):
      图解:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public void insertEnd(int value){
    //尾插
		Node node = new Node(value);
		Node temp = head;
	
		while(temp.next != null){
    
			temp = temp.next;
		}
		
		temp.next = node;
		
		head.data++;
	}

7.插入(索引位置插入):
      temp移动到索引位置的前一项,然后执行类似于5中头插法的操作即可。图解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public void insert(int index,int value){
    //索引位置插
		if(index < 1 || index > head.data+1){
    
			System.out.println("索引值不合法!");
			return;
		}
		Node node = new Node(value);
		Node temp = head;
		for(int i = 0;i < index - 1;i++){
    
			temp = temp.next;
		}
		
		node.next = temp.next;
		temp.next = node;
		
		head.data++;
	}

8.删除(头删):
      head.next指向haed.next.next即可
      temp图解:
在这里插入图片描述

public void deleteHead(){
    //删头
		if(head.data == 0){
    
			System.out.println("空链表!无法再执行删除!");
			return;
		}
		
		head.next = head.next.next;
		
		head.data--;
	}

9.删除(尾删):
      temp移动到尾部元素的直接前驱,然后temp.next指向null即可(后移次数用head.data控制,移动head.data-1次后,temp指向末尾的直接前驱,即倒数第二个元素)
      图解:
在这里插入图片描述
在这里插入图片描述
10.删除(删除索引位置元素):
      temp移动到指定索引位置的直接前驱,通过,用给定的索引值index控制移动次数,移动index-1次,然后通过temp.next = temp.next.next;来删除索引位置元素。
      图解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public void deleteEnd(){
    //删尾
		if(head.data == 0){
    
			System.out.println("空链表!无法再执行删除!");
			return;
		}
		
		Node temp = head;
		
		for(int i = 0 ;i < head.data - 1;i++){
    
			temp = temp.next;
		}
		
		temp.next = null;
		
		head.data--;
	}

11.查找(指定元素求索引):
      与4中遍历的操作一致,在遍历每个结点时插入比较temp.data == value;为true则return 遍历过的结点数;为false:继续遍历,直到找到或者temp.next == null,遍历完还未找到即return -1;

	
	public int locateElement(int value){
    //定位指定元素索引(首次出现  不存在返回-1
		Node temp = head;
		
		for(int i = 0;i < head.data;i++){
    
			temp = temp.next;
			if(temp.data == value){
    
				return i+1;
			}
		}
		
		return -1;
	}

12.查找:(指定索引元素)
      同上,通过temp=temp.next后移,用给定的索引值index值控制移动次数,因为要到index处的结点,所以移动index次,移动完成后,通过return temp.data;返回该结点的数据项;

public int getElement(int index){
    //返回指定索引值元素  索引非法返回-1
		
		if(index < 1 || index > head.data){
    
			return -1;
		}
		
		Node temp = head;
		
		for(int i = 0;i < index;i++){
    
			temp = temp.next;
		}
		
		return temp.data;
		
	}

13.更改(更改指定索引位置元素值):
      同上,遍历到索引为index处的结点,通过temp.data = value;更改索引位置的元素值;

public void update(int index,int value){
    //更改指定索引位置的元素值
		
		if(index < 1 || index > head.data){
    
			System.out.println("索引值非法");
		}
		
		Node temp = head;
		
		for(int i = 0;i < index;i++){
    
			temp = temp.next;
		}
		
		temp.data = value;
	}

综上,带头结点的单链表基本实现。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/afsfdgags/article/details/106676185

智能推荐

vue element-ui中组件v-infinite-scroll,无限触发loadMore事件解决_infinitescroll loadmore 滚动分页连续请求的问题-程序员宅基地

文章浏览阅读5.7k次。使用element-ui组件v-infinite-scroll出现了无限触发滚动事件,关键问题代码如下:<template> <div ref="ullist" :style="autoHeight" class="infinite-list-wrapper" style="overflow:auto"> <ul v-infinite-scroll="loadMore" infinite-scroll-disabled="busy"> <li v-._infinitescroll loadmore 滚动分页连续请求的问题

mysql修改成utf8mb4依然无法插入emoji表情问题_utf8mb4格式 org.springframework.jdbc.uncategorizedsq-程序员宅基地

文章浏览阅读6k次。最近做项目需要用到emoji表情,好不容易把前端搞定,提交数据到后台发现无法插入数据库,异常提示如下:org.springframework.jdbc.UncategorizedSQLException: ### Error updating database. Cause: java.sql.SQLException: Incorrect string value: '\xF0\x9F\x..._utf8mb4格式 org.springframework.jdbc.uncategorizedsqlexception:

OCiOS开发:音频播放器 AVAudioPlayer-程序员宅基地

文章浏览阅读6.1k次。简介AVAudioPlayer音频播放器可以提供简单的音频播放功能,其头文件包含在AVFoudation.framework中。AVAudioPlayer未提供可视化界面,需要通过其提供的播放控制接口自行实现。AVAudioPlayer仅能播放本地音频文件,并支持以下格式文件:.mp3、.m4a、.wav、.caf、.aif
。常用方法初始化方法// 1、NSURL 它只能从file:/

Android事件分发详解(三)——ViewGroup的dispatchTouchEvent()源码学习_viewgroup dispatchtouchevent(三)-程序员宅基地

文章浏览阅读3.1k次,点赞9次,收藏7次。package cc.aa;import android.os.Environment;import android.view.MotionEvent;import android.view.View;public class UnderstandDispatchTouchEvent { /** * 该示例的重点: * 1 ViewGroup的dispatc_viewgroup dispatchtouchevent(三)

codeforces 785D. Anton and School - 2(组合计数,二项系数计算)_2项式的计算方法-程序员宅基地

文章浏览阅读749次。Problem LinkD. Anton and School - 2 分析官方题解已经写的很好了,不过我有点不理解它的证明,我,即他说的那个一一对应的那部分, 想一下如果上图3个13个1的位置刚好在左括号的位置这样不就没有匹配了吗?不知道是不是我英文不好的原因23333 不过我们如果限定了最后一个开括号的位置就会很容易给定在这种情况一定是对应着(x+y−1x)\binom{x+y-1}{_2项式的计算方法

随便推点

基于MSP430 红外避障-遥控小车(电赛必备 附项目代码)_msp430红外循迹小车-程序员宅基地

文章浏览阅读6.7k次,点赞42次,收藏135次。项目简介:小车可分为3种工作模式,每种工作模式都会打印在OLED显示屏上,通过按键转换工作模式。模式1:小车红外循迹,通过超声波实时监测障碍物距离,若超出规定路线,距离障碍物相对较近时,原地停止,等待指令。模式2: 自主驾驶,通过超声扫描各障碍物距离,当小于一定距离时原地左转。模式3:蓝牙远程遥控本项目用到的模块有:1. MSP430F5529开发板2. 红外循迹模块 TCRT5000L3. 超声波 HC-SR044. 蓝牙 ATK_HC-055. 显示屏 四针OLED6. 充电电池 _msp430红外循迹小车

人工智能:模拟退火初始温度值的计算_模拟退火算法初始温度如何定-程序员宅基地

文章浏览阅读1.2w次,点赞5次,收藏17次。1.模拟退火法简介模拟退火法是一种状态空间的局部搜索算法,它属于比较通用的寻找最优解的算法。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。2.模拟退火法算法描述function Simulated-Annealing(problem, schedule) returns a soluti_模拟退火算法初始温度如何定

Random rand = new Random(47);的简单解释-程序员宅基地

文章浏览阅读7.7k次。Random rand = new Random(47);是java中的一个随机数的生成方法,其中47是作为一个种子,也就是一个实参,你可以写成20,30等等。如果是Random rand = new Random();这样,那么种子也就是实参为系统的时间。这里声明了一个对象rand,后面就用rand来构造随机数的范围和类型了。_new random(47)

LVM逻辑卷企业实战实例_由于在生产环境中,无法估量硬盘分区在日后的使用情况,某企业在linux服务器中新镇-程序员宅基地

文章浏览阅读573次。LVM逻辑卷企业实战实例_由于在生产环境中,无法估量硬盘分区在日后的使用情况,某企业在linux服务器中新镇

【NOIP2018】游记_noip2018游记-程序员宅基地

文章浏览阅读779次。Day0考前想着怎么也该考一考数据结构或者图论或者数轮吧敲了手Splay的模板,二位树状数组模板,线段树模板,然后就回寝室打三国杀了(雾)Day1T1原题,敲完就去看T2了T2想了想,是个完全背包,敲完就解决了T3我想到了二分加上贪心合并,但里面在维护最多数量时并没有想到怎么尽量让上传的足够大这时候放弃了T3回去看T1,首尾相连,这莫不是个环,没有什么时间推样例了,急急..._noip2018游记

CF 1065F F. Up and Down the Tree( 树形dp)_up and down dp-程序员宅基地

文章浏览阅读602次。文章目录题目连接分析code题目连接F. Up and Down the Tree分析官网题解个人翻译:可以分两步dp:dp[u] : 以 uuu 为根的节点访问完所有能访问的叶子节点并回到 uuu 所能获得的最大叶子数目,low[u], 这种情况下所能获得的最低的叶子深度(dep最小),这两个东西是完全独立的可以一起弄ans[u]: 以 uuu 为根的节点所能获得的最大叶子数目..._up and down dp

推荐文章

热门文章

相关标签