单链表的遍历删除修改的实现
本帖最后由 holistic杀手 于 2022-12-10 18:27 编辑大家好，这是一个没有用索引完成的单向链表的部分功能（删除、修改、获取全部元素）的代码。感觉用索引会好一些，因为可能存在一个元素重复存储的情况。{:10_254:} {:10_254:} {:10_254:}
/*
单链表中的节点：
节点是单向链表中的基本的单元。
每一个节点Node都有两个属性。
一个属性：是存储的数据。
另一个属性：是下一个节点的内存地址。
*/
public class Node<E> {
//数据
E element;
//下一个节点的内存地址
Node next;
public Node() {
}
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
}
/*
链表类。(单向链表)
*/
public class Link<E> {
//头节点
private Node header;
private int size =0;
public int getSize(){
return size;
}
// 向链表中添加元素的方法（向末尾添加）
public void add(E data){
//public void add(Object data){
if (header == null){
// 说明还没有节点。
// new一个新的节点对象，作为头节点对象。
// 这个时候的头节点既是一个头节点，又是一个末尾节点。
header = new Node(data,null);
}else{
// 说明头不是空！
// 头节点已经存在了！
// 找出当前末尾节点，让当前末尾节点的next是新节点。
Node currentLastNode = findLast(header);
currentLastNode.next = new Node(data,null);
}
size++;
}
/**
* 专门查找末尾节点的方法。
* @param node 传进来的节点
* @return 传进来的节点的next为空，返回该节点;不为空进行递归，直到找到某个节点的next为空，返回该节点。
*/
private Node findLast(Node node) {
// 如果一个节点的next是null
// 说明这个节点就是末尾节点
if (node.next==null){
return node;
}
//程序能够到这里说明：node不是末尾节点。
return findLast(node.next);//递归
}
// 删除链表中某个数据的方法****************
public void remove(E data){
Node node = contains(data,header);
if (node==null){
throw new ElementNotFoundException("ExceptionWarning:ElementNotFound！");
}else {
if (node==header){
header =node.next;
node.next =null;
}else if(node==findLast(header)){
findprev(data,header).next=null;
}else {
Node prevnode = findprev(data, header);
prevnode.next = node.next;
}
size--;
}
}
/**
* 找该节点的上一个节点
*/
private Node findprev(E data,Node node) {
if (node.next.element == data){
return node;
}
return (findprev(data,node.next));
}
/*
看链表中是否包含该数据
*/
private Node contains(E data,Node node) {
if (node.element==data){
return node;
}else if(node.next != null){
return contains(data,node.next);
}
return null;
}
//修改链表中某个数据的方法
public void modify(E olddata,E newdata) {
if (contains(olddata,header)==null){
throw new ElementNotFoundException("ExceptionWarning:ElementNotFound！");
}else{
contains(olddata,header).element=newdata;
}
}
//遍历***************
public void getAll(){
Node node = header;
while (node!=null){
System.out.println(node.element);
node=node.next;
}
}
}
class ElementNotFoundException extends RuntimeException{
public ElementNotFoundException(){}
public ElementNotFoundException(String s){
super(s);
}
}
页:
[1]