自己动手实现java数据结构（二） 链表

　　链表基于下标的增删改查操作都需要进行下标的越界检查。这里优化了前面"向量篇"博客中提到的缺陷，针对不同的错误，会抛出不同类型的自定义异常，使客户端可以进行更细致的异常处理。

   
     * 插入时,下标越界检查
     *  index 下标值
     void rangeCheckForAdd( index){
        :::如果大于size的值,抛出异常
        :::注意：插入时,允许插入线性表的末尾,因此(index == size)是合法的
        if(index > .size){
            throw new OutOfIndexBoundException("index error  index=" + index + " size=" + .size) ;
        }
        if(index < 0new NegativeOfIndexException("index error  index=" + index + " size=" + .size) ;
        }
    }

    
     * 下标越界检查
     * void rangeCheck(:::如果大于等于size的值,抛出异常
        if(index >= .size) ;
        }
    }

　　同时，链表基于下标的操作都需要先查询出下标对应的内部节点，通过操纵对应的内部节点来进行相关操作。因此需要抽象出一个通用的查询方法。

   
     * 返回下标对应的 内部节点
     * private Node<E> find(:::要求调用该方法前,已经进行了下标越界校验
        :::出于效率的考虑,不进行重复校验

        :::判断下标在当前列表的大概位置（前半段 or 后半段）尽量减少遍历查询的次数
        if(index < this.size/2:::下标位于前半段

            :::从头部结点出发,进行遍历(从左到右)
            Node<E> currentNode = .first.right;
            :::迭代(index)次
            int i=0; i<index; i++){
                currentNode = currentNode.right;
            }

             currentNode;
        }:::下标位于后半段

            :::从尾部结点出发,进行遍历(从右到左)
            Node<E> currentNode = .last.left;
            :::迭代(size-index-1)次
            int i=index; i<size-1; i++ currentNode.left;
            }
             currentNode;
        }
    }

find方法的时间复杂度?:

　　可以看到，find方法会根据下标所处的大概位置决定开始遍历的方向(尽量减少迭代查询的次数)，下标越接近头部或者尾部，查询次数越少。因此下标在靠近头部、尾部时效率较高，而在居中位置效率较低。

（编辑：网站开发网_盐城站长网 ）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!