模仿LinkList实现一个双向链表

小咪咪 2023-10-02 17:18 25阅读 0赞

### 实现一个双向链表 ###

直接看代码，可以根据注释整理思路

package cn.com.suanfa;
    
    /**
     * 实现一个简单的链表
     */
    public class LinkListYsx<E> {
        
    
        private NodeYsx<E> first;
        private NodeYsx<E> last;
        int size = 0;
    
        /**
         * 获取指定下标的值
         * @param index
         * @return
         */
        public E get(int index){
        
            if (checkIndex(index)){
        
                NodeYsx<E> nodeYsx = node(index);
                return nodeYsx.obj;
            }else {
        
                return null;
            }
        }
    
        /**
         * 在链表头部新增节点
         * @param obj
         */
        public void addFirst(E obj){
        
            NodeYsx<E> f = first;
            NodeYsx<E> newNodeYsx = new NodeYsx<E>(null, obj, f);
            first = newNodeYsx;
            if (f == null){
        
                last = newNodeYsx;
            }else {
        
                f.prev = newNodeYsx;
            }
            size++;
        }
    
        /**
         * 在链表尾部新增节点
         * @param obj
         */
        public void addLast(E obj){
        
            NodeYsx<E> l = last;
            NodeYsx<E> newNodeYsx = new NodeYsx<>(l, obj, null);
            last = newNodeYsx;
            if (l == null){
        
                first = newNodeYsx;
            }else {
        
                l.next = newNodeYsx;
            }
            size++;
        }
    
        /**
         * 在链表指定节点新增节点
         * @param index
         * @param obj
         */
        public void add(int index, E obj) {
        
            if (checkIndex(index)){
        
                NodeYsx<E> nodeYsx = node(index);
                NodeYsx<E> prev = nodeYsx.prev;
                NodeYsx<E> newNodeYsx = new NodeYsx<>(prev, obj, nodeYsx);
                prev.next = newNodeYsx;
                nodeYsx.prev = newNodeYsx;
                size++;
            }
        }
    
        /**
         * 删除链表头节点
         * @return
         */
        public E removeFirst(){
        
            NodeYsx<E> f = first;
            E value = f.obj;
            NodeYsx<E> next = f.next;
            f.obj = null;
            f.next = null;
            if (next == null){
        
                last = null;
            }else {
        
                next.prev = null;
            }
            size--;
            return value;
        }
    
        /**
         * 删除链表尾节点
         * @return
         */
        public E removeLast(){
        
            NodeYsx<E> l = last;
            E value = l.obj;
            NodeYsx<E> prev = l.prev;
            l.obj = null;
            l.prev = null;
            last = prev;
            if (prev == null){
        
                first = null;
            }else {
        
                prev.next = null;
            }
            size--;
            return value;
        }
    
        /**
         * 判断下标是否超出链表范围
         * @param i
         * @return
         * @throws Exception
         */
        private boolean checkIndex(int i) {
        
            if (i >= 0 && i < size){
        
                return true;
            }else {
        
                throw new IndexOutOfBoundsException();
            }
        }
    
        /**
         * 获取指定下标的节点
         * @param index
         * @return
         */
        private NodeYsx<E> node(int index){
        
            if (index < size / 2){
        
                NodeYsx<E> result = first;
                for (int i = 0; i < index; i++) {
        
                    result = result.next;
                }
                return result;
            }else{
        
                NodeYsx<E> result = last;
                for (int i = size-1; i > index; i--) {
        
                    result = result.prev;
                }
                return result;
            }
        }
    
        /**
         * 链表的Node节点
         * @param <E>
         */
        private class NodeYsx<E> {
        
            private NodeYsx<E> prev;
            private E obj;
            private NodeYsx<E> next;
    
            public NodeYsx(NodeYsx<E> prev, E obj, NodeYsx<E> next) {
        
                this.prev = prev;
                this.obj = obj;
                this.next = next;
            }
        }
    }