15.Java实现自己的带虚拟头节点的单链表

深藏阁楼爱情的钟 2022-02-28 14:36 117阅读 0赞

package com.cl.set;
    
    public class LinkedList<E> {
    
         private class Node{
             public E e;
             public Node next;
    
             public Node(E e, Node next) {
                 this.e = e;
                 this.next = next;
             }
    
             public Node(E e) {
               this(e,null);
             }
    
             public Node() {
                 this(null,null);
             }
    
             @Override
             public String toString() {
                 return e.toString();
             }
         }
    
         private Node dummyHead;
         private int size;
         //private Node tail;//tail删除元素仍旧为O(n),添加元素为O（1）
    
        public LinkedList(Node head, int size) {
            this.dummyHead = head;
            this.size = size;
        }
    
        public LinkedList() {
            //虚拟头节点，不存放元素
            dummyHead =new Node();
            size=0;
        }
    
        public int getSize(){
            return size;
        }
    
        public boolean isEmpty(){
            return size==0;
        }
    
        /** O(n)
         * index从0开始算,练习用的
         * @param e
         * @param index
         */
        public void add(E e,int index){
    
            if(index<0||index>size)
                throw new IllegalArgumentException("Add Faile,index Illegal");
            Node pre = dummyHead;
            for(int i=0;i<index;i++){
                pre=pre.next;
            }
       /*     Node node = new Node(e);
            node.next=pre.next;
            pre.next=node;*/
            pre.next= new Node(e,pre.next);
            size++;
        }
    
        /**
         *  O(1)
         * @param e
         */
    
        public void addFirst(E e){
            add(e,0);
        }
    
        /**
         * O(n)
         * 链尾处理元素
         * @param e
         */
        public void addLast(E e){
            add(e,size);
        }
    
        /**O(n)
         * index从0开始
         * @param index
         * @return
         */
        public E get(int index){
            if(index<0||index>size)
                throw new IllegalArgumentException("get Faile,index Illegal");
            Node cur = dummyHead.next;
            for(int i =0;i<index ;i++){
                cur=cur.next;
            }
            return cur.e;
        }
    
        /**
         *  O(1)
         * @return
         */
        public E getFirst(){
            return get(0);
        }
    
        // O(n)
        public E getLast(){
            return get(size-1);
        }
    
        /** O(n)
         * 修改
         * @param index
         * @param e
         */
        public void set(int index ,E e){
            if(index<0||index>size)
                throw new IllegalArgumentException("set Faile,index Illegal");
            Node cur = dummyHead.next;
            for(int i=0;i<index;i++){
                cur=cur.next;
            }
            cur.e=e;
        }
    
        /**
         *  O(n)
         *  是否包含
         * @param e
         * @return
         */
        public boolean contains(E e){
            Node cur = dummyHead;
            while (cur.next!=null){
                if(cur.next  .e.equals(e)){
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }
    
        /**
         *  O(n)
         * @param index
         * @return
         */
        public E remove(int index){
            if(index<0||index>size)
                throw new IllegalArgumentException("remove Faile,index Illegal");
            Node pre = dummyHead;
            for (int i=0;i<index;i++){
                pre = pre.next;
            }
            Node ret = pre.next;
            pre.next=ret.next;
            ret.next=null;
            size--;
            return ret.e;
    
        }
    
        /**
         *  O(1)
         * @return
         */
        public E removeFirst(){
            return remove(0);
        }
    
        // O(n)
        public E removeLast(){
            return remove(size-1);
        }
    
        public void removeElement(E e){
            Node pre = dummyHead;
            while(pre.next!=null){
                if(pre.next.e.equals(e)){
                   break;
                }
                pre = pre.next;
            }
            if(pre.next!=null){
                Node deNode = pre.next;
                pre.next=deNode.next;
                deNode.next=null;
            }
        }
        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
    //        Node cur = dummyHead.next;
    //        while(cur!=null) {
    //            ret.append(cur+"-->");
    //            cur=cur.next;
    //        }
    
            for (Node cur =dummyHead.next;cur!=null;cur=cur.next){
                ret.append(cur+"-->");
            }
            ret.append("null");
            return ret.toString();
        }
    }