数据结构 ——链表（虚拟头结点）

秒速五厘米 2023-10-12 08:03 41阅读 0赞

public class LinkedList2<E> {
    
        //另外一种思路
        // 内存空间不是连续的 即物理空间不是连续的 逻辑空间依赖着next指向是连续的
        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;
    
        public LinkedList2(){
            dummyHead = new Node();
            size = 0;
        }
    
        //获取链表中元素个数
        public int getSize(){
            return size;
        }
    
        public boolean isEmpty(){
            return size == 0;
        }
    
        public void addFirst(E e){
            add(0,e);
        }
    
        //在指定位置添加结点
        // 由于并不常见 所以我们定义head 为 第 0 个元素
        public void add(int index, E e){
            if (index < 0 || index > size){
                throw new IllegalArgumentException("指定位置越界");
            }
            if(index == 0){
                addFirst(e);
            }else{
                Node pre = dummyHead;
                for (int i = 0 ; i < index ; i++){
                    pre = pre.next;
                }
    
                /*Node c = new Node(e);
                c.next = pre.next;
                pre.next = c;*/
                pre.next = new Node(e,pre.next);
                size--;
            }
        }
        public void addLast(E e){
            add(size,e);
        }
    
        public E get(int index ){
            if (index < 0 || index > size){
                throw new IllegalArgumentException("越界");
            }
    
            Node cur = dummyHead.next;
            for (int i = 0 ; i < index ; i++) {
                cur = cur.next;
    
            }
            return cur.e;
        }
        public E getFirst(){
            return get(0);
        }
        public E getLast(){
            return get(size);
        }
    
        // 查询是否存在元素e
        public boolean contains(E e) {
            Node cur = dummyHead.next;
            for (int i = 0; i < size; i++) {
    
                if (cur.e == e) {
                    return true;
                }
                cur = cur.next;
            }
             return false;
        }
    
        public E remove(int index){
            if (index < 0 || index > size){
                throw new IllegalArgumentException("下标越界");
            }
            Node cur = dummyHead;
            for (int i =0 ; i < index ; i++){
                cur = cur.next;
            }
            Node t = new Node();
            cur.next = t;
            cur.next = t.next;
            t.next = null;
            size --;
            return t.e;
    
        }
    
        public E removeFirst(){
            return remove(0);
        }
    
        public E removeLast(){
            return remove(size);
        }
    
    }

在head 结点的前面的创建虚拟头结点。 为了使修改删除 ，让head结点和普通结点一视同仁

转载于:https://www.cnblogs.com/JTrun/p/11331661.html