链表【java版】

男娘i 2024-04-03 09:46 69阅读 0赞

#### 文章目录 ####

*  List接口
 *  AbstractList
 *  双向链表
 *  单向循环链表
 *  双向循环链表
 *  相关测试代码

*  以前学的知识，现在有时间重新整理一下。

## List接口 ##

package 数据结构.Day03;
    
    /**
     * @author 缘友一世
     * @date 2022/8/28-17:14
     */
    public interface List<E> {
        
        int size();
        int indexOf(E element);//查看元素的位置 考虑空值的情况
        boolean contains(E element);//是否包含某个元素
        E get(int index);//返回index位置对应的元素
        E set(int index,E element);//设置index位置的元素
        void clear();//清除所有元素
        void add(E element);//添加元素到最后面
        void add(int index,E element);//向index位置添加元素
        E remove(int index);//删除index位置对应的元素
        boolean isEmpty();//是否为空
    }

## AbstractList ##

package 数据结构.Day03;
    
    /**
     * @author 缘友一世
     * @date 2022/8/28-17:26
     */
    //公共代码 抽象类
    public abstract class AbstractList<E> implements List<E>  {
        
        protected int size=0;
        protected static final int ELEMENT_NOT_FOUND=-1;
    
        /**
         * 元素个数
         * @return
         */
        @Override
        public int size() {
        
            return size;
        }
    
        /**
         * 是否包含某个元素
         * @param element
         * @return
         */
        public boolean contains(E element) {
        
            return indexOf(element)!=ELEMENT_NOT_FOUND;
        }
    
        @Override
        public void add(E element) {
        
            add(size,element);
        }
    
        /**
         * 判断是否为空
         * @return true空| false 非空
         */
        public boolean isEmpty() {
        
            return size==0;
        }
    
        //判断是否越界
        public void checkIndex(int index) {
        
            if(index<0 || index>=size) {
        
                throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+(size-1)+"当前索引为："+index);
            }
        }
        public void checkAddIndex(int index) {
        
            if(index<0 || index>size) {
        
                throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+size+"当前索引为："+index);
            }
        }
    }

## 双向链表 ##

package 数据结构.Day04;
    
    import 数据结构.Day03.AbstractList;
    
    /**
     * @author 缘友一世
     * @date 2022/8/28-17:35
     */
    public class LinkedListDouble<E> extends AbstractList<E> {
        
        private Node<E> first;
        private Node<E> last;
        //内部类
        private class Node<E> {
        
            E element;//存储的数据
            Node<E> pre;//上一个node的地址
            Node<E> next;//下一个node的地址
    
            public Node(Node<E> pre, Node<E> next, E element) {
        
                this.element = element;
                this.pre = pre;
                this.next = next;
            }
    
            @Override
            public String toString() {
        
                StringBuilder sb = new StringBuilder();
                if(pre!=null) {
        
                    sb.append(pre.element);
                }else {
        
                    sb.append("null");
                }
                sb.append("<-").append(element).append("->");
                if(next!=null) {
        
                    sb.append(next.element);
                }else {
        
                    sb.append("null");
                }
                return sb.toString();
            }
        }
    
        @Override
        public E get(int index) {
        
            //下标越界处理
            checkIndex(index);
            return node(index).element;
        }
    
        private Node<E> node(int index) {
        
            //下标越界处理
            checkIndex(index);
            if(index< (size>>1)) {
        
                //拿到first
                Node<E> node=first;
                for(int i=0;i<index;i++) {
        
                    node = node.next;
                }
                return node;
            }else {
        
                //从后往前
                Node<E> node=last;
                for(int i=size-1;i>index;i--) {
        
                    node=node.pre;
                }
                return node;
            }
        }
    
        @Override
        public E set(int index,E element) {
        
            //下标越界处理
            checkIndex(index);
            //通过node(index)获取element
            Node<E> node = node(index);
            E old = node.element;
            node.element=element;
            return old;
        }
    
        @Override
        public void clear() {
        
            size=0;
            first=null;
            last=null;
        }
    
        @Override
        public int indexOf(E element) {
        
            Node<E> node=first;
            //当元素为空时，依次遍历寻找
            if(element==null) {
        
                for(int i=0;i<size;i++) {
        
                    if(node.element==null) {
        
                        return i;
                    }
                    node=node.next;
                }
            }else {
        
                for(int i=0;i<size;i++) {
        
                	//使用equals方法进行判断，返回下标
                    if(element.equals(node.element)) {
        
                        return i;
                    }
                    //迭代的条件
                    node=node.next;
                }
            }
            return ELEMENT_NOT_FOUND;
        }
    
        @Override
        public void add(int index, E element) {
        
            //下标越界处理 index可以等于size——在末尾添加
            checkAddIndex(index);
            if(index==size) {
        
                Node<E> oldLast=last;
                last=new Node<E>(oldLast,null,element);
                if(oldLast==null) {
        
                    first=last;
                }else {
        
                    oldLast.next=last;
                }
            }else {
        
                Node<E> next = node(index);
                Node<E> pre = next.pre;
                Node<E> node = new Node<E>(pre, next, element);
                next.pre=node;
                if(pre==null) {
        
                    first = node;
                }else {
        
                    pre.next=node;
                }
            }
            size++;
        }
    
        @Override
        public E remove(int index) {
        
            //下标越界检查 index==size
            checkIndex(index);
           //记录被删除的节点
            Node<E> node = node(index);
            //记录被删除节点的前一个节点
            Node<E> pre = node.pre;
            //记录被删除节点的后一个节点
            Node<E> next = node.next;
            if(pre==null) {
        
                first=next;
            }else {
        
                //将前一个节点的next指向后一个节点
                pre.next=next;
            }
            if(next==null) {
        //index=size-1 删除最后一个元素
                last=pre;
            }else {
        
                //将最后一个节点的pre指向前一个节点
                next.pre=pre;
            }
            size--;
            return node.element;
        }
        @Override
        public String toString() {
        
            StringBuilder sb = new StringBuilder();
            sb.append("size:" + size + " => [");
            Node<E> node=first;
            for(int i=0;i<size;i++) {
        
                if(i!=0) {
        //只要不是第一个元素就拼接一个逗号和空格
                    sb.append(" ,");
                }
                sb.append(node.toString());//拼接每个元素
                node=node.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }

## 单向循环链表 ##

package 数据结构.Day04;
    
    import 数据结构.Day03.AbstractList;
    
    /**
     * @author 缘友一世
     * @date 2022/8/28-17:35
     */
    public class LinkedListSingleCircle<E> extends AbstractList<E> {
        
        private Node<E> first;
        //内部类
        private class Node<E> {
        
            E element;//存储的数据
            Node<E> next;//下一个node的地址
    
            public Node( Node<E> next,E element) {
        
                this.element = element;
                this.next = next;
            }
        }
    
        @Override
        public E get(int index) {
        
            //下标越界处理
            checkIndex(index);
            return node(index).element;
        }
    
        private Node<E> node(int index) {
        
            //下标越界处理
            checkIndex(index);
    
            Node<E> node=first;
            for(int i=0;i<index;i++) {
        
                node = node.next;
            }
            return node;
        }
    
        @Override
        public E set(int index,E element) {
        
            //下标越界处理
            checkIndex(index);
            //通过node(index)获取element
            Node<E> node = node(index);
            E old = node.element;
            node.element=element;
            return old;
        }
    
        @Override
        public void clear() {
        
            size=0;
            first=null;
        }
    
        @Override
        public int indexOf(E element) {
        
            Node<E> node=first;
            if(element==null) {
        
                for(int i=0;i<size;i++) {
        
                    if(node.element==null) {
        
                        return i;
                    }
                    node=node.next;
                }
            }else {
        
                for(int i=0;i<size;i++) {
        
                    if(element.equals(node.element)) {
        
                        return i;
                    }
                    node=node.next;
                }
            }
            return ELEMENT_NOT_FOUND;
        }
    
        @Override
        public void add(int index, E element) {
        
            //下标越界处理 index可以等于size——在末尾添加
            checkAddIndex(index);
            //在头处添加节点
            if(index==0) {
        
                /*
                * 注意：first=newFirst必须要在获取last之后，因为一旦first提前指向新的首节点，
                * 那么size-1,就不是最后一个节点，而是倒数第二个的节点
                * */
                //创建新的节点
                Node<E> newFirst = new Node<>(first, element);
                //获取最后位置的节点,让其next指向新的首节点
                //判断新添加的节点，是不是第一个兼最后一个节点
                Node<E> last = (size==0)? newFirst: node(size - 1);
                last.next=newFirst;
                //让指向原来的首节点first指向新的首节点
                first=newFirst;
            }else {
        
                //获取前一个节点的地址
                Node<E> pre = node(index - 1);
                //获取取后一个节点【相较于插入的节点】的地址
                Node<E> next = pre.next;
                //创建新的节点，并将本节点的地址
                pre.next=new Node(next,element);
            }
            //最后节点个数加1
            size++;
        }
    
        @Override
        public E remove(int index) {
        
            //下标越界检查 index<size
            checkIndex(index);
            //获取待删除的节点
            Node<E> oldNode=first;//0x444
            if(index==0) {
        
                if(size==1) {
        //只有一个节点
                    first=null;
                }else {
        
                    //获取最后一个节点(一定是在改变first指向值之前拿到最后一个节点不然就会下标越界)
                    Node<E> last = node(size - 1);
                    //改变first指向待删除节点后面的节点
                    first=first.next;//0x888
                    //最后的节点指向开始的节点
                    last.next=first;
                }
            }else {
        
                //获取前一个节点
                Node<E> pre = node(index - 1);
                oldNode = pre.next;//0x666
                pre.next=pre.next.next;//0x777
            }
            size--;
            return oldNode.element;
        }
        @Override
        public String toString() {
        
            StringBuilder sb = new StringBuilder();
            sb.append("size:" + size + " => [");
            Node<E> node=first;
            for(int i=0;i<size;i++) {
        
                if(i!=0) {
        //只要不是第一个元素就拼接一个逗号和空格
                    sb.append(" ,");
                }
                sb.append(node.element);//拼接每个元素
                node=node.next;
            }
            sb.append("]");
            return sb.toString();
        }
    
    }

## 双向循环链表 ##

package 数据结构.Day04;
    
    import 数据结构.Day03.AbstractList;
    
    /**
     * @author 缘友一世
     * @date 2022/8/28-17:35
     */
    public class LinkedListDoubleCircle<E> extends AbstractList<E> {
        
        private Node<E> first;
        private Node<E> last;
        //内部类
        private class Node<E> {
        
            E element;//存储的数据
            Node<E> pre;//上一个node的地址
            Node<E> next;//下一个node的地址
    
            public Node(Node<E> pre, Node<E> next, E element) {
        
                this.element = element;
                this.pre = pre;
                this.next = next;
            }
    
            @Override
            public String toString() {
        
                StringBuilder sb = new StringBuilder();
                if(pre!=null) {
        
                    sb.append(pre.element);
                }else {
        
                    sb.append("null");
                }
                sb.append("<-").append(element).append("->");
                if(next!=null) {
        
                    sb.append(next.element);
                }else {
        
                    sb.append("null");
                }
                return sb.toString();
            }
        }
    
        @Override
        public E get(int index) {
        
            //下标越界处理
            checkIndex(index);
            return node(index).element;
        }
    
        private Node<E> node(int index) {
        
            //下标越界处理
            checkIndex(index);
            if(index< (size>>1)) {
        
                //拿到first
                Node<E> node=first;
                for(int i=0;i<index;i++) {
        
                    node = node.next;
                }
                return node;
            }else {
        
                //从后往前
                Node<E> node=last;
                for(int i=size-1;i>index;i--) {
        
                    node=node.pre;
                }
                return node;
            }
        }
    
        @Override
        public E set(int index,E element) {
        
            //下标越界处理
            checkIndex(index);
            //通过node(index)获取element
            Node<E> node = node(index);
            E old = node.element;
            node.element=element;
            return old;
        }
    
        @Override
        public void clear() {
        
            size=0;
            first=null;
            last=null;
        }
    
        @Override
        public int indexOf(E element) {
        
            Node<E> node=first;
            if(element==null) {
        
                for(int i=0;i<size;i++) {
        
                    if(node.element==null) {
        
                        return i;
                    }
                    node=node.next;
                }
            }else {
        
                for(int i=0;i<size;i++) {
        
                    if(element.equals(node.element)) {
        
                        return i;
                    }
                    node=node.next;
                }
            }
            return ELEMENT_NOT_FOUND;
        }
    
        @Override
        public void add(int index, E element) {
        
            //下标越界处理 index可以等于size——在末尾添加
            checkAddIndex(index);
            if(index==size) {
        //在最后添加节点
                Node<E> oldLast=last;
                last=new Node<E>(oldLast,first,element);
                if(oldLast==null) {
        //链表中没有节点
                    first=last;
                    first.pre=first;
                    first.next=first;
                }else {
        
                    oldLast.next=last;
                    first.pre=last;//将开始的pre指向last
                }
            }else {
        
                Node<E> next = node(index);
                Node<E> pre = next.pre;
                Node<E> node = new Node<E>(pre, next, element);
                next.pre=node;
                pre.next=node;
                if(index==0) {
        
                    first = node;
                }
            }
            size++;
        }
    
        @Override
        public E remove(int index) {
        
            //下标越界检查 index==size
            checkIndex(index);
            Node<E> node=first;//主要作用：提升作用域，避免返回报错
            if(size==1) {
        //只有一个节点的情况
                first=null;
                last=null;
            }else {
        
                //记录被删除的节点
                node = node(index);
                //记录被删除节点的前一个节点
                Node<E> pre = node.pre;
                //记录被删除节点的后一个节点
                Node<E> next = node.next;
                //将前一个节点的next指向后一个节点
                pre.next=next;
                //将最后一个节点的pre指向前一个节点
                next.pre=pre;
                if(index==0) {
        //删除第一个元素
                    first=next;
                }
                if(index==size-1) {
        //index==size-1 删除最后一个元素
                    last=pre;
                }
            }
            size--;
            return node.element;
        }
        @Override
        public String toString() {
        
            StringBuilder sb = new StringBuilder();
            sb.append("size:" + size + " => [");
            Node<E> node=first;
            for(int i=0;i<size;i++) {
        
                if(i!=0) {
        //只要不是第一个元素就拼接一个逗号和空格
                    sb.append(" ,");
                }
                sb.append(node.toString());//拼接每个元素
                node=node.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }

## 相关测试代码 ##

package 数据结构.Day04;
    
    /**
     * @author 缘友一世
     * @date 2022/8/30-22:51
     */
    public class Test04 {
        
        public static void main(String[] args) {
        
            //双向链表
            System.out.println("双向链表：");
            LinkedListDouble<Object> doubleList = new LinkedListDouble<>();
            doubleList.add(1);
            doubleList.add(2);
            doubleList.add(3);
            System.out.println(doubleList);
            doubleList.add(0,4);
            System.out.println(doubleList);
            doubleList.remove(3);
            System.out.println(doubleList);
    
            //单循环链表
            System.out.println("单循环链表：");
            LinkedListSingleCircle<Object> sc = new LinkedListSingleCircle<>();
            sc.add(1);
            sc.add(2);
            sc.add(3);
            System.out.println(sc);
            sc.add(0,4);
            System.out.println(sc);
            sc.remove(1);
            System.out.println(sc);
    
            //双循环链表
            System.out.println("双循环链表：");
            LinkedListDoubleCircle<Object> db = new LinkedListDoubleCircle<>();
            db.add(2);
            db.add(3);
            db.add(4);
            db.add(1,6);//[2,6,3,4]
            System.out.println(db);
            db.remove(0);
            System.out.println(db);//[6,3,4]
        }
    }