实现单链表的基本操作

痛定思痛。 2023-06-11 11:29 17阅读 0赞

实现单链表的基本操作

1.  头插
2.  尾插
3.  获取长度
4.  包含元素
5.  移除元素

package Demo;
    
    public class LinkedList {
        
        private LinkedNode head = null;
        public void addFirst(int elem){
        
            //先创建一个节点，让这个节点的值就是 elem
            LinkedNode node = new LinkedNode(elem);
            if(this.head == null) {
        
                //空链表的情况
                this.head = node;
                return;
            }
            //如果不是空链表，就需要把新的节点放到链表的开始位置上
            node.next = head;
            this.head = node;
            return;
        }
    
        public void addLast(int elem) {
        
            LinkedNode node = new LinkedNode(elem);
            //如果是空链表，直接把这个节点放在去即可
            if(this.head == null){
        
                this.head =  node;
                return;
            }
            //非空的情况，需要先找到最后一个节点
            LinkedNode cur = this.head;
            while(cur.next != null) {
        
                cur = cur.next;
            }
            cur.next = node;
        }
    
        public void addIndex(int index,int elem){
        
            LinkedNode node = new LinkedNode(elem);
            //1.先对 pos 进行一个合法性的校验，需要知道链表的长度
            int len size();
            if(index < 0 || index > len) {
        
                return;
            }
            //2.处理头插的情况
            if(index == 0) {
        
                addFirst(elem);
                return;
            }
            //3.处理尾插
            if(index == len) {
        
                addFirst(elem);
                return;
            }
            //4.处理插入到中间位置的情况
            //prev 这个引用就对应到 index - 1的位置
            LinkedNode prev = getIndexPos(index -1);
            //5.完成具体的插入过程
            node.next = prev.next;
            prev.next = node;
        }
    
        private LinkedNode getIndexPos(int index){
        
            //是否要判断一下index 是在有效范围中呢
            LinkedNode cur = this.head;
            for(int i = 0; i < index; i++){
        
                cur = cur.next;
            }
            return  cur;
        }
    
        public  int size(){
        
            int size = 0;
            for(LinkedNode cur = this.head; cur != null; cur = cur.next) {
        
                size ++;
            }
            return size;
        }
       public boolean contains(int toFind){
        
            //直接遍历链表，依次比较每个元素就行
           for(LinkedNode cur = this.head;cur != null; cur = cur.next) {
        
               if(cur.data ==toFind){
        
                   return turn;
               }
           }
           return false;
       }
       
       public void remove(int toRamove) {
        
            //1.先单独处理下空链表的情况
           if(head == null) {
        
               return;
           }
           //2.先考虑是否要删除的是头结点
           if(head.data == toRamove) {
        
               this.head = this.head.next;
               return;
           }
           //3.删除中间的节点，找到要删除元素的前一个元素
           LinkedNode prev = searchPrev(toRemove);
           LinkedNode nodToRemove = prev.next;
           prev.next = nodeToRemove.next;
       }
       
       private LinkedNode searchPrev(int toRemove) {
        
            //找到要删除元素的前一个位置
           if(this.head == null) {
        
               return null;
           }
           LinkedNode prev = this.head;
           while (prev.next != null) {
        
               if(prev.next.data == toRemove) {
        
                   return prev;
               }
               prev = prev.next;
           }
           //返回 null表示没找到
           return null;
       }
       
       public  void display(){
        
            //打印链表中的所有元素
           System.out.print("[");
           for(LinkedNode node = this.head; node != null; node = node.next) {
        
               System.out.println(node.data);
               if(node.next !=null) {
        
                   //如果不是最后一个元素就加上，否则不加
                   System.out.println(",");
               }
           }
           System.out.println("]");
       }
    }