单链表的遍历删除修改的实现

holistic杀手

大家好，这是一个没有用索引完成的单向链表的部分功能（删除、修改、获取全部元素）的代码。感觉用索引会好一些，因为可能存在一个元素重复存储的情况。 [/b]

/*
单链表中的节点：
    节点是单向链表中的基本的单元。
    每一个节点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);
    }
}