手写动态链表（五）(java版)

曾经终败给现在 2022-01-11 03:41 230阅读 0赞

public class LinkedList<E> {
        //链表节点类，private 外部不可访问
        private class Node{
    
            E e;
            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 head;
        //链表节点个数
        private int size;
    
        public LinkedList(){
            //虚拟节点，方便节点添加，和节点删除。
            //因为节点添加和删除会分别使添加的节点的前置节点指向新节点，要删除节点的前置节点指向删除节点的后一个节点
            //主要是为方便第一个节点的添加和删除，因为第一个节点没有前置节点
            head = new Node();
            size = 0;
        }
    
        public int getSize(){
            return size;
        }
    
        public boolean isEmpty(){
            return size == 0;
        }
        //添加节点index(0--size-1)
        public void add(int index,E e){
    
            if (index<0 || index>size)
                throw  new IllegalArgumentException("Add Failed,index is illegal");
            //前置节点
            Node prev = head;
            //因为循环是index次,而实际查询index(范围0-size-1)索引下标元素，而index索引下标的元素是第index+1个元素
            //循环index次，实际是从index为0开始，所以循环过后就是index索引下标的前置元素
            for (int i = 0;i<index;i++)
                prev = prev.next;
    
           /* Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;*/
           
           //prev.next = new Node(e,prev.next);与上面的等效
            //new Node(E e,Node next)创建的是一个节点，节点中e存储数据信息，next存储下个节点的引用
            //prev.next是添加index索引下标的节点的前置节点next，new Node(e,prev.next)就是创建当前index索引下标节点
            //然后前置节点next（pre.next）指向新节点（new Node(e,prev.next)）
            prev.next = new Node(e,prev.next);
            size++;
        }
    
        public void addFirst(E e){
            add(0,e);
        }
        public void addLast(E e){
            add(size,e);
        }
        //删除节点
        public E remove(int index){
            if (index<0 || index>size)
                throw  new IllegalArgumentException("Remove Failed,index is illegal");
            if (head.next == null)
                throw  new IllegalArgumentException("Remove Failed,Node is null");
            Node prev = head;
            for (int i = 0;i<index;i++)
                prev = prev.next;
            //当前节点
            Node cur = prev.next;
            //前置节点next 指向当前节点的下一个节点
            prev.next = cur.next;
            size--;
            //让Gc可以回收
            cur.next = null;
            return cur.e;
    
    
        }
        public E removeFirst(){
            return remove(0);
        }
    
        public E removeLast(){
            return remove(size-1);
        }
        //设置下标index的数据元素e
        public void set(int index,E e){
            if (index<0 || index>size)
                throw  new IllegalArgumentException("Set Failed,index is illegal");
            if (head.next == null)
                throw  new IllegalArgumentException("Set Failed,Node is null");
            Node node = head.next;
            for (int i = 0;i<index;i++)
                node = node.next;
    
            node.e = e;
    
    
        }
        //获取节点
        public E get(int index){
            Node node = head.next;
            if (head.next == null)
                throw  new IllegalArgumentException("Get Failed,Node is null");
            for (int i = 0;i<index;i++)
                node = node.next;
    
            return node.e;
    
        }
    
        public E getFirst(){
    
            return get(0);
        }
        public E getLast(){
    
            return get(size-1);
        }
        public boolean contains(E e){
    
            Node node = head.next;
            while (node!= null){
                if (node.e.equals(e))
                    return true;
                node = node.next;
            }
    
            return false;
        }
    
        @Override
        public String toString() {
            Node node = head.next;
            StringBuilder res = new StringBuilder();
            res.append("Node:[");
            while (node!=null){
                res.append(node.e);
                node = node.next;
                if (node!= null)
                    res.append(",");
            }
            res.append("],size:"+size);
    
            return res.toString();
        }
    
        public static void main(String[] args) {
            LinkedList<Integer> list = new LinkedList<>();
            /*for (int i = 0;i<10;i++)
                list.addLast(i);
            list.removeLast();
            System.out.println(list.contains(20));
    
            list.set(2,99);
            System.out.println(list);*/
            list.removeFirst();
            System.out.println(list.getLast());
        }
    
    
    }