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

发布时间：2021-04-01 14:24:59 所属栏目：安全来源：网络整理

导读：副标题#e# 1.链表介绍前面我们已经介绍了向量，向量是基于数组进行数据存储的线性表。今天，要介绍的是线性表的另一种实现方式---链表。链表和向量都是线性表，从使用者的角度上依然被视为一个线性的列表结构。但是，链表内部存储数据的方式却和向量大不

　　从概率的角度上来看，下标访问是随机的，因此find方法的时间复杂度被认为是O(n)。

3.4.2 链表的插入方法实现

 add(E e) {
        :::将新的数据 插入到列表末尾 ==> 作为last节点的前一个节点插入
        this.last.linkAsLeft((e));
        :::size自增
        this.size++;

        true:::插入时,下标越界检查
        rangeCheckForAdd(index);

        :::查询出下标对应的 目标节点
        Node<E> targetNode = find(index);

        :::将新的数据节点 作为目标节点的前一个节点插入
        targetNode.linkAsLeft((e));

        ;
    }

插入方法的时间复杂度:

尾部插入：

　　尾部插入方法中，由于我们维护了一个last哨兵节点，通过直接将新节点插入last哨兵的左边，完成尾部数据的插入。

　　因此，尾部插入方法的时间复杂度为O(1)。

下标插入：

　　下标插入方法中，依赖find方法查询出下标对应的节点，然后将新节点进行插入。

　　因此，下标插入方法的时间复杂度为O(n)；对于头部，尾部节点的插入，时间复杂度为O(1)。

3.4.3 删除方法的实现

 remove(E e) {
        .first;
:::如果不是查询空元素
            :::匹配成功,将当前节点从链表中删除
                    currentNode.unlinkSelf();
                    :::删除成功,返回true
                    ;
                }
            }
        }:::如果是查询null元素
            :::如果满足要求
                ;
                }
            }
        }
        
        falsepublic E remove( index) {
        :::下标越界检查
        rangeCheck(index);

        :::获得下标对应的 Node
        Node<E> targetNode =:::将目标节点从链表中移除
        targetNode.unlinkSelf();
        :::size自减
        this.size--:::返回被移除的节点data值
         targetNode.data;
    }

删除方法的时间复杂度:

特定元素删除：

　　链表特定元素的删除和find方法类似，通过一次遍历获得目标节点，然后进行删除。

　　因此，特定元素的删除方法时间复杂度为O(n)。

下标删除：

　　下标删除方法中，依赖find方法查询出下标对应的节点，然后将目标节点进行删除。

　　因此，下标删除方法的时间复杂度为O(n)；对于头部，尾部节点的删除，时间复杂度为O(1)。

3.4.4?修改/查询方法实现

public E set(:::先暂存要被替换的"data"
        E oldValue = targetNode.data;
        :::将当前下标对应的"data"替换为"e"
        targetNode.data = e;

        :::返回被替换的data
         oldValue;
    }

    @Override
    public E get( targetNode.data;
    }

修改/查询方法的时间复杂度：

　　可以看到，链表基于下标的修改和查询都依赖于find方法。

　　因此，修改/查询方法的时间复杂度为O(n)；对于头部，尾部节点的修改和查询，时间复杂度为O(1)。

3.5 链表其它接口

3.5.1 clear方法

　　clear方法用于清空链表内的元素，初始化链表。

 clear() {
        :::当头部哨兵节点不和尾部哨兵节点直接相连时
        while(this.first.right != .last){
            :::删除掉头部哨兵节点后的节点
            remove(0);
        }

        :::执行完毕后,代表链表被初始化,重置size
        ;
    }

3.5.2 toString方法

 String toString() {
        Iterator<E> iterator = .iterator();

        :::空列表
        if(!iterator.hasNext()){
            return "[]";
        }

        :::列表起始使用"["
        StringBuilder s = new StringBuilder("[");

        :::反复迭代
        :::获得迭代的当前元素
            E data = iterator.next();

            :::判断当前元素是否是最后一个元素
            iterator.hasNext()){
                :::是最后一个元素，用"]"收尾
                s.append(data).append("]");
                :::执行完毕 返回拼接完成的字符串
                 s.toString();
            }{
                :::不是最后一个元素
                :::使用","分割，拼接到后面
                s.append(data).append(",");
            }
        }
    }

　　链表的toString方法在之前"向量篇"的基础上进行了优化。基于列表List的Iterator接口进行遍历，实现了同样的功能。事实上，改进之后的toString方法也同样可以适用于向量。

　　在jdk的Collection框架中，框架设计者要求所有的单值数据结构容器都必须实现Iterator接口，因而将toString方法在AbstractCollection这一顶层抽象类中进行了实现，达到统一单值数据结构容器toString方法默认行为的目的，增强了代码的可重用性。

4.链表的Iterator(迭代器)

   
     * 链表迭代器实现
     * class Itr implements Iterator<E>
         * 当前迭代器光标位置
         * 初始化指向 头部哨兵节点
         * private Node<E> currentNode = LinkedList..first;
        
         * 最近一次迭代返回的数据
         *  lastReturned;

        @Override
         hasNext() {
            :::判断当前节点的下一个节点 是否是 尾部哨兵节点
            this.currentNode.right != LinkedList..last);
        }

        @Override
         E next() {
            :::指向当前节点的下一个节点
            this.currentNode = .currentNode.right;

            :::设置最近一次返回的节点
            this.lastReturned = currentNode;

            :::返回当前节点的data
            .currentNode.data;
        }

        @Override
         remove() {
            if(this.lastReturned == new IteratorStateErrorException("迭代器状态异常: 可能在一次迭代中进行了多次remove操作");
            }

            :::当前光标指向的节点要被删除,先暂存引用
            Node<E> nodeWillRemove = .currentNode;

            :::由于当前节点需要被删除,因此光标前移,指向当前节点的上一个节点
            .currentNode.left;

            :::移除操作需要将最近一次返回设置为null，防止多次remove
            this.lastReturned = :::将节点从链表中移除
            nodeWillRemove.unlinkSelf();
        }
    }

　　迭代器在实现时需要满足接口的行为定义，remove方法在一次next迭代中不能被重复调用，否则会产生古怪的异常。