JAVA实现单链表

心已赠人 2022-09-22 13:52 244阅读 0赞

# 解释透明，代码通过亲测没毛病，可直接赋值粘贴运行^\_^ #

# 定义节点类: #

package 链表;
    
    public class Node {
        
        public  int Element;
        public  Node next;
        public Node(int Element,Node next){
            this.Element=Element;
            this.next=next;
        }
    
    }

# 定义链表的操作方法类: #

package 链表;
    
    public class LinkedList {
        
        //定义头结点
        private Node head;
        public Node getHead(){
            return this.head;
        }
        private int size;
        //定义操作:
         //添加元素
        public void add(int e){
            //创建一个新的节点
            Node node=new Node(e,null);
            //如果头结点为空，那么就直接将第一个节点作为头结点
            if(head==null){
                head=node;
                size++;
                return;
            }
            //如果头结点不为空，那么就找到最后一个节点,将新来的元素加在这个最后一个节点的后面
            Node  temp=head;
            while(temp.next!=null){
                temp=temp.next;
            }
            temp.next=node;
            size++;
        }
         //打印输出元素
        public String toString(){
            Node temp=head;
            StringBuffer message=new StringBuffer("[");
            if(temp!=null){
                while(temp.next!=null){
                    message.append(temp.Element);
                    temp=temp.next;
                    message.append("   ");
                }
                message.append(temp.Element+"  ");
            }
            message.append("]");
            return message.toString();
    
        }
        //判断链表是否为空:
        public boolean isEmpty(){
            if(head==null){
                return true;
            }
            return false;
        }
    
        //链表的长度:
        public int size(){
            return size;
        }
    //  5.根据索引返回元素(先练习)
        public int get(int index){
            Node temp=head;
            if(index>=size){
                throw new RuntimeException("outOfIndexException--超出链表的所允许的下标范围");
            }
            while(index!=0){
                temp=temp.next;
                index--;
            }
            return temp.Element;
        }
    //  6、按照索引位置新增的实现(先练习)
        public void add(int index,int e){
            //1.找到这个节点:
            Node temp=head;
            if(index>=size){
                throw new RuntimeException("OutOfIndexException----超出链表所能允许的下标范围");
            }
            //如果是插在头结点的位置，那么就让该节点的下一个节点指向头结点，并且把这个新加入的节点作为头结点
            if(index==0){
                Node node=new Node(e,head);
                head=node;
                return;
            }
            //如果插入的节点位置不是头结点，那么首先找到索引对应位置的前一个节点，这个节点的新加入的节点的后继应该是
            //前一个节点的后继，然后，前一个节点的后继改成新加入的节点即可
            while(index!=1){
                temp=temp.next;
                index--;
            }
            //2.新建一个Node,并给数据区域赋值
            Node node=new Node(e,temp.next);
            //3.将新节点加入当中【改变引用指向】
            temp.next=node;
        }
    //  7、按照索引删除的实现(先练习)
        public void delete(int index){
            //考虑特殊情况:1,越界  2.删除的是头结点 
            Node temp=head;
            if(index>=size){
                throw new RuntimeException("OutOfIndexException----超出链表所能允许的下标范围");
            }
            //删除头结点，直接让头结点变成头结点的下一个节点即可，然后把被删的头结点置空，等待垃圾gc回收
            if(index==0){
              head=temp.next;//如果只有一个元素，那么下一个是null,那么整个链表就为空了呗
              return;
            }
            //删除非头结点，找到索引对应位置的前一个元素，然后，让前一个元素的后继指向被删节点的后继，再把被删节点释放掉
            while(index!=1){
                temp=temp.next;
                index--;
            }
            Node delNode=temp.next;
            temp.next=delNode.next;
            delNode=null;
        }
    //  8、按照元素删除的实现(先练习)
        public void del(int e){
            //考虑到具有重复元素的情况，都给它删了
            Node temp=head;
            if(temp.Element==e){
                head=temp.next;
                temp=head;
            }
            //特殊情况处理:如果删除的是中间节点
            while(temp.next.next!=null){
                if(temp.next.Element==e){
                    Node node=temp.next;
                    temp.next=node.next;
                    node=null;
                }
                temp=temp.next;
            }
            if(temp.next.next==null&&temp.next.Element==e){
                temp.next=null;
            }
        }
    //  9、判断某个元素是否在集合中(先练习)
        public boolean isIn(int e){
            Node temp=head;
            //如果链表没到末尾或者说没找到元素的时候，不断循环，直到不满足条件退出循环
            if(temp==null){
                throw new RuntimeException("链表为空");
            }
            while(temp.Element!=e&&temp.next!=null){
                temp=temp.next;
            }
            //退出循环的情况:1.元素在中间某个结点上，此时退出链表没到末尾，表示找到
            //            2.元素刚好在末尾，此时最后一个结点的值等于要找的值，并且链表达到末尾，即同时不满足两个循环条件
            //            3.没有找到元素，链表达到末尾并且最后一个元素不等于要找的值
            /*if((temp.next==null&&temp.Element==e)||temp.next!=null){
                return true;
            }*/
            if(temp.next==null&&temp.Element!=e){
                return false;
            }
            return  true;
        }
           // 判断两个集合是否相等
            public boolean  isEqual(LinkedList list)
            {
                //首先判断两个链表的大小是否相等,如果大小不等直接false
                if(list!=null&&!list.isEmpty()){
       //用了短路与进行判断传入list的状态
                    if(this.size!=list.size()){
                        return false;
                    }
                    //2.如果长度相等，判断每个节点是否对应相等,如果有一个不相等就false掉
                    Node temp1=head;
                    Node temp2=list.getHead();
                    int k=this.size;
                    while(k!=0&&temp1!=null){
                        if(temp1.Element!=temp2.Element){
                            return false;
                        }
                        temp1=temp1.next;
                        temp2=temp2.next;
                        k--;
                    }
                    return true;
                }
               throw new RuntimeException("链表为空");
            }
            //合并集合
            public void merge(LinkedList list)
            {
                //循环另一个链表，将另一个链表中的元素添加到当前链表中
                if(list==null||list.isEmpty()){
       //用了短路与进行判断传入list的状态
                     throw new RuntimeException("输入链表为空");
                }
                Node temp=list.getHead();
                while(temp!=null){
                    this.add(temp.Element);
                    temp=temp.next;
                }
            }
            //清空链表:
            public void empty(){
                this.head=null;
                size=0;
            }
    
    
    
    
    
    }