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

　　链表内部维护着首、尾哨兵两个内部节点(双端)，作为链表的第一个和最后一个节点，新插入的节点总是处于这两个哨兵节点之间，用户也无法感知哨兵节点的存在。哨兵节点并不用于保存数据，其存在的主要目的是为了简化边界条件的逻辑。

　　举个例子：在节点插入时，必须判断当前是否第一个节点，来决定是否需要建立和之前节点的联系；在节点删除时，也必须判断自己的左右节点是否存在，避免空指针异常。首尾哨兵节点的引入使得任何情况下，节点插入，删除时都可以确保其左右节点一定存在，从而避免大量的异常判断。

　　可以看到，哨兵节点的引入简化了代码在边界条件时的各种判断逻辑。这提高了执行效率，更重要的是降低了复杂性，使代码变得更容易理解，也更可靠。

{
    
     * 链表 头部哨兵节点
     * private Node<E> first;
    
     * 链表 尾部哨兵节点
     *  last;
    
     * 链表 逻辑大小
     *  size;

    public LinkedList() {
        this.first = new Node<>();
        this.last = ();

        :::将首尾哨兵节点 进行连接
        this.first.right = .last;
        this.last.left = .first;

        :::初始化size
        this.size = 0;
    }
}

3.3?较为简单的?size()，isEmpty()，indexOf()，contains()方法实现：

    @Override
     size() {
        return .size;
    }

    @Override
     isEmpty() {
        return (this.size == 0);
    }

    @Override
     indexOf(E e) {
        :::当前节点 = 列表头部哨兵
        Node<E> currentNode = if(e != null){
            :::如果不是查询null元素

            :::遍历列表
            for(int i=0; i<this.size; i++){
                :::不断切换当前节点 ==> "当前节点 = 当前节点的右节点"
                currentNode = currentNode.right;
                :::如果满足要求（注意: equals顺序不能反,否则可能会有currentNode.data为空,出现空指针异常）
                if(e.equals(currentNode.data)){
                    :::返回下标
                    return i;
                }
            }
        }else{
            :::如果是查询null元素

            :::如果是null元素
                if(currentNode.data == ){
                     i;
                }
            }
        }
        :::遍历列表未找到相等的元素,返回特殊值"-1"代表未找到
        return -1;
    }

    @Override
     contains(E e) {
        :::复用indexOf方法,如果返回-1代表不存在;反之,则代表存在
        return (indexOf(e) != -1);
    }

链表 indexOf、contains方法的时间复杂度：　　

　　indexOf方法的实现和向量类似，是通过一次循环遍历来进行查询的，从头部节点不停地跳转到下一个节点，直到发现目标节点或者到达尾部哨兵节点。

　　因此indexOf方法、contains方法的时间复杂度都是O(n)。

3.4 链表增删改查接口实现

3.4.1?下标越界检查

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

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