第三章链表

作者: 古剑诛仙 | 来源:发表于2019-10-10 22:35 被阅读0次

数据结构与算法相关续
第三章链表
第三章链表
第三章链表
链表基础
双向链表&双向循环链表
算法与数据结构:链表
链表
五、双向链表
链表

基本概念

链表的含义：

链表是一种用于存储数据集合的数据结构，具有以下属性

相邻元素之间通过指针相连
最后一个元素的后继指针为NULL
在程序执行过程中，链表的长度可以增加或减小
链表的空间能够按需分配（直到系统内存耗尽）
没有内存空间的浪费（但链表中的指针需要一些额外的内存开销）

image.png

链表的操作：

插入：插入一个元素到链表中
删除：移除并返回链表中指定位置的元素
删除链表：清空链表中的全部元素
计数：返回链表中元素的个数
查找：寻找从链表表头开始的第n个节点（node）

链表与数组的比较：

链表和数组都可用于存储数据集合，但两者的用法还是有些许不同，下面对两种的异同进行比对

image.png

数组的优点：

实现简单，使用方便
访问元素快（常数时间）

数组的缺点：

大小固定：数组的大小是静态的（需要在使用前声明其大小）
分配一个连续的空间块：数组初始分配空间时，有时内存不足以给出一个连续的空间以存放数组（当数组过大或者内存碎片过多时）
基于位置的插入操作实现复杂：如果要在数组的指定位置插入元素，可能需要移动存储在数组中的其他元素。指定的位置越靠前，移动操作的开销也就越大。

数组的改进：

image.png

链表的主要优点：

链表的扩展和收缩都是常数时间。当创建数组时，必须分配能存储一定数量元素的内存。如果向数组中添加更多元素，必须创建一个新的数组，然后把原数组中的元素复制到新数组中，这将产生很大的开销。
当然可以为数组预先分配一个很大的空间来预防上述情况的发生，但很可能因为分配超过用户需要的空间而造成内存浪费。动态数组的实现也是基于上文所述的原理。而对于链表，初始时仅需要分配一个元素的存储空间，而且添加新的元素也很容易，不需要做任何内存复制和重新分配的操作。

链表的缺点：

链表最主要的缺点就是访问单个元素的时间开销问题。数组是随机存取的，即存取数组中任一元素的时间开销为 $O(1)$ 。而链表在最差情况下访问一个元素的时间开销是 $O(n)$ 。同时数组在存取时间的另一个优点是内存的空间局部性。因为数组定义为连续的内存块，所以任何数组元素与其邻居是物理相邻的。这一点归功于现代的CPU缓存模式。
尽管链表在动态分配存储空间上有很大优势，但在存储和检索数据的开销却有很大问题。尤其是对链表的操作很麻烦。比如要删除链表最后一个元素，倒数第二个结点必须更改后继结点为NULL，而这需要从头遍历链表，直到找到倒数第二个结点。相当于为了删除一个元素，需要遍历两遍链表。（后续程序中为避免这一点，用一个临时结点存储当前结点的前一个结点）
链表中的额外指针引用需要消耗内存

image.png

单向链表

最常用的链表就是单向链表，它包含多个结点，每个节点有一个指向后继元素的next指针，最后一个结点的next指针为NULL，表示链表的结束

image.png

下面我们看一下单向链表的三种基本操作：遍历链表，在链表中插入一个元素，在链表中删除一个元素

单向链表的遍历

image.png

单向链表的插入
单向链表的插入可分为以下三种情况：

在链表的表头前插入一个新的结点（相当于在原表头前插入一个新表头）
在链表的表尾后插入一个新的结点（相当于在原尾结点后添加一个新尾结点）
在链表的中间插入一个新的结点（第一二种情况外的任意位置）
这里我们说在位置p插入一个结点，是说新的结点位置是p

image.png

单向链表的删除
与插入类似，删除也分为三种情况：

删除链表的表头结点
删除链表的表尾结点
删除链表中间的节点

image.png

image.png
注意这里应该是 count<position-1
单向链表的清空释放

image.png

这里值得注意的是其中的clear方法仅仅是将head置为空，如有size则置为0，在LinkedList源码中，其实现如下

 /**
     * Removes all of the elements from this list.
     * The list will be empty after this call returns.
     */
    public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

关键在于源码中的两行注释

当遗弃的结点在不止一代中（新生代和老年代）存在，可以帮助分代收集器GC
即便有一个关于linkedlist的可达的迭代器存在，也可以保证链表中的结点的内存被回收（不然会造成虽然头尾结点都是Null，但如果一个迭代器作为GC root，其中lastReturned指向一个结点，这个结点还有前驱和后继结点，最终导致所有结点都得不到释放，即便此时头尾结点已经无法遍历至其他结点了）

// LinkedList中迭代器部分源码
private class ListItr implements ListIterator<E> {  
    private Entry<E> lastReturned = header;  
    private Entry<E> next;  
    private int nextIndex;  
    private int expectedModCount = modCount;  
  
    ListItr(int index) {  
        if (index < 0 || index > size)  
        throw new IndexOutOfBoundsException("Index: "+index+  
                            ", Size: "+size);  
        if (index < (size >> 1)) {  
        next = header.next;  
        for (nextIndex=0; nextIndex<index; nextIndex++)  
            next = next.next;  
        } else {  
        next = header;  
        for (nextIndex=size; nextIndex>index; nextIndex--)  
            next = next.previous;  
        }  
    }  
  
    public boolean hasNext() {  
        return nextIndex != size;  
    }  
  
    public E next() {  
        checkForComodification();  
        if (nextIndex == size)  
        throw new NoSuchElementException();  
  
        lastReturned = next;  
        next = next.next;  
        nextIndex++;  
        return lastReturned.element;  
    }  
......  
}

综上所述，因此源码实现才会在将基础的头尾结点置空，size置0之前，将每个结点的值，前驱和后继结点都置为空，当然我们这里实现的最基础的链表功能是不需要考虑这么多的。

双向链表

双向链表的特点是：对于链表中一个给定的结点，可以从两个方向来操作。在单向链表中，只有获得结点的前驱结点，才能删除该结点。然而在双向链表中，即使没有获得一个给定结点的前驱结点，也可以删除该结点（这是因为双向链表的每个结点都有next指针同时还有previous指针指向前驱结点）
然而与单向链表相比：

每个结点需要添加一个额外的指针，因此需要更多空间开销
结点的插入和删除更加费时（需要更多的指针操作）

下面是一个双向链表的类型声明

image.png
双向链表的插入
与单向链表类似，双向链表的插入也分为三种情况

image.png

双向链表的删除

image.png

循环链表

单向链表和双向链表中都用NULL表示链表的结束，然而循环链表没有结束标志（没有next为NULL的情况）。因此遍历循环链表需要格外小心，因为每一个结点都有一个后继结点，会导致遍历无限循环下去。

循环链表在某些情况下是很有用的，例如多个进程都想使用CPU资源，并且它们使用该资源的时间也相同，为了防止某个进程总是排在其他进程前面，通过循环链表实现的轮询算法可以保证公平。

image.png

题外话：链表中的哨兵

注意到我们对于链表的操作牵扯到插入和删除时，无论是单链表，双向链表还是循环链表，都要根据头部操作，尾部操作和中间操作的不同分为多种情况，下面我们引入哨兵这个概念：

哨兵，顾名思义，是用来解决国家之间边界问题的，不直接参与生产活动。
同样，计算机科学中提到的哨兵，也用来解决边界问题。
在许多算法中，存在“邻居依赖问题”，在处理当前元素时，要涉及到它旁边那个元素。那如果当前元素是边界元素时，它没有旁边那个元素，此时不作处理，程序就可能出错；但对它特别对待，就会增加代码复杂性，还会降低程序效率。应用哨兵，也就是申请若干个多余的元素作为边界元素的邻居，可以完美得解决这个问题。

比如在n*m的矩形区域中，例如扫雷，一个点击方块时，要扫描周围8个方块的雷数，而边界方块的周围不足8个方块，一种解决方法就是在有效矩形区域的周围，添加一圈的方块，

但这个方法申请的哨兵数量有点多，数量是2n+2m-4,在实践中应该酌情考虑。

在数组中，参考以下一个例子：如果要在含n个数的数组array中找value值的索引

 1.普通写法：
        for (int i = 0; i < n; ++i) {
            if (value == array[i])
                return i;
        }


    2.使用哨兵：
        array[n] = value;
        for (int i = 0;; i++) {
            if (value == array[i]) {
                if (i != n)
                    return i;
            }
        }

可以看使用哨兵比普通写法节省了每次 i<n 的耗时，而这个消耗会随着n的增大而增大

而在链表中，单链表在插入和删除时，需要修改前驱结点的后继指针，这就形成了“邻居依赖”，链表中第一个元素没有前驱结点，如果没有特殊处理，在插入和删除第一个结点时，就会出错。

所以我们可以申请一个头结点，作为原本的第一个结点的前驱结点，问题也就解决了。但是在这种方式中，我们要插入或者删除一个结点时，如果此时要知道它的前驱结点地址，这往往是麻烦的。

image.png

如上图所示，在单链表中第一个结点是哨兵结点，它的item域是没有确切意义的，而之后的item为5的结点才是链表中第一个元素，通过设置哨兵结点可以极大的简化对链表操作的逻辑，使得代码显得简洁，下一节是一个基于哨兵结点的单链表，其中具备了一些单链表常见操作，同时实现了一些对链表的特殊操作（常见于面试题中）

另一个方式，也是我更喜欢的方式，是申请一个尾结点，作为原本最后一个结点的后继结点。

要删除某个元素时，我们不删除当前这个结点，而是用后继结点的数据覆盖当前结点的数据，再删除后继结点。这种方式，不需要访问前驱结点，也就解决了获取前驱结点的困难。插入元素分为两种情况：如果我们要在当前节点后插入，那么直接创建新结点，然后更改当前节点的后继与新结点的后继结点就可以了；如果我们要在当前节点前插入，由于需要修改当前节点的前驱结点的后继指针是比较麻烦的，可以新建一个值是当前节点值的结点，然后把新结点的后继指针指向当前节点的后继结点，修改当前节点的后继指针，同时修改当前节点的值为新结点的原值。
（注意：因为涉及到数据的拷贝，如果结点的数据类型不是基本类型，而是引用数据类型，需要注意深浅拷贝的问题）

对于双向链表，我们知道为了能够在更快的在头部和尾部分别进行插入删除操作（可以实现双端队列）而不需要遍历链表，需要引入指向尾部的指针，观察下图中的情况

image.png

从上图可以看出一个问题，last结点有时指向哨兵结点，有时指向实际结点。这会导致特殊情况的出现，比如在进行addFirst操作时，last指向哨兵结点时插入后需要将last往后移动一个，而第二张图指向实际结点时在头部插入结点后并不需要改变last指针。这时需要在尾部后也引入一个哨兵结点，以使其一致。相应示意图如下：

image.png

但这样一来一个双向链表中，就需要2个哨兵结点，我们做一下改进，用一个哨兵结点实现
我们将双向链表升级为循环双向链表，让哨兵结点指向头结点，item中不存内容，当为空链表时，使哨兵结点的前驱和后继指针都指向自身

image.png

当不为空链表时，哨兵结点与第一个元素（实际为第二个结点）和最后一个结点链接在一起，最后结点的后继指针与哨兵结点的前驱指针相互指向对方

image.png

一个基于哨兵结点的单链表实现

public class MyLinkedList<E extends Comparable> {
    // 结点类
    static class Node<E> {
        
        private E item;
        private Node<E> next;
        Node(){}
        Node(E element) {
            this.item = element;
        }

        public void setItem(E item) {
            this.item = item;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }

        public E getItem() {
            return item;
        }

        public Node<E> getNext() {
            return next;
        }
    }
    // 链表的第一个结点,作为哨兵结点，不存放实际内容，
    // 如果不使用哨兵结点，应在各种链表操作中对其正常初始化和赋值
    private Node<E> sentry=new Node<>();

    public MyLinkedList() {
        
    }

    /**
     * 1. 判断链表是否为空
     */
    public boolean isEmpty() {
        return sentry.next == null;
    }

    /**
     * 2. 返回链表长度
     * @return 链表长度
     */
    public int size() {
        return size(sentry);
    }

    /**
     * 3. 返回当前节点后的结点数
     * @param head 当前节点
     * @return head 结点之后的结点数
     */
    public static <E> int size(Node<E> head) {
        Node<E> temp = head.next;
        int size = 0;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    /**
     * 4. 正向遍历链表
     */
    public void printList() {
        Node<E> temp = sentry.next;
        while (temp != null) {
            System.out.println(temp.item);
            temp = temp.next;
        }
    }

    /**
     * 5. 反向遍历链表
     * 因为要反向遍历链表，考虑使用递归，因为递归调用栈既是一个天然的先入后出的队列
     */
    public void printListReverse() {
        Node<E> temp = sentry.next;
        printListReverse(temp);
    }

    /**
     * 反向输出当前节点及之后的结点值
     * @param e
     */
    private void printListReverse(Node<E> e) {
        if (e != null) {
            printListReverse(e.next);
            System.out.println(e.item);
        }
    }

    /**
     * 6. 链表头部添加节点
     * 如果头结点为空，新加结点就是头结点
     * 如果头结点不为空，则新加结点的next就是头结点，并且将头结点设置为新加结点
     * 这里使用哨兵结点简化边界条件
     * @param e <E> 要插入的结点值
     */
    public void addFirst(E e) {
        // 这里我们使用哨兵后，不需要对空链表进行特殊处理
        Node<E> newNode = new Node<E>(e);
        newNode.next=sentry.next;
        sentry.next=newNode;
        
//     第一个结点不是哨兵结点时，代码如下：
//       Node<E> temp = sentry;
//       Node<E> newNode = new Node<E>(e, null);
//
//       if (temp == null) {
//           sentry = newNode;
//       }
//       else {
//           newNode.next = temp;
//           sentry = newNode;
//       }
    }

    /**
     * 7. 链表尾部添加节点
     * 直接找到最后一个节点，添加到最后一个节点的next
     * 特殊情况：如果链表长度为0，直接令first为新插入节点
     * 引入哨兵节点处理特殊情况，简化边界条件
     * @param e <E> 要插入的结点值
     */
    public void addLast(E e) {
        Node<E> newNode = new Node<E>(e);
        Node<E> current=sentry;
        while (current.next!=null) {
            current=current.next;
        }
        current.next=newNode;
//       第一个结点不是哨兵结点时，代码如下：
//       Node<E> temp = sentry;
//       Node<E> newNode = new Node<E>(e, null);
//       if (temp == null) {
//            sentry = newNode;
//       }
//       else {
//            while (temp.next != null) {
//                temp = temp.next;
//            }
//            temp.next = newNode;
//       }
    }

    /**
     * 8. 链表按索引位置插入新结点
     * @param index 需要插入的结点位置，当链表长度为n时，合法范围为1~n+1
     * @param insertValue 需要插入的结点值
     */
    public boolean addNodeByIndex(int index, E insertValue) {
        if(insertValue==null){
            throw new IllegalArgumentException("空结点值！");
        }
        if (index < 1 || index > size() + 1) {
            System.out.println("插入的位置不合法。");
            return false;
        }
        int count=1;
        Node<E> newNode = new Node<>(insertValue);
        Node<E> previous= sentry;
        while (count<index) {
            
            previous = previous.next;
            count++;
        }
        Node<E> current=previous.next;
        newNode.next=current;
        previous.next=newNode;
        return true;
        
        

    }

    /**
     * 9. 指定值的后面添加节点
     * 如果链表中已经有了重复的值，以排在最前面的为准.
     * 如果插入成功，则返回true
     * 如果插入失败，则返回false
     * 特殊情况：
     * 1. 如果链表是空的，直接返回false
     * 2. 如果两个参数有NULL值，直接返回false
     * 以下几个类似方法采用相同规则
     * @param aimValue <E>目标结点值
     * @param insertValue <E>新插入的结点值
     * @return 返回插入是否成功
     */
    public boolean addAfter(E aimValue, E insertValue) {
        if(aimValue==null||insertValue==null)
            return false;
        Node<E> temp = sentry.next;
        while (temp != null) {
            if (temp.item.equals(aimValue)) {
                Node<E> newNode = new Node<E>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                return true;
            }
            else {
                temp = temp.next;
            }
        }
        return false;
       
    }

    /**
     * 10. 所有指定值后面添加节点
     * @param aimValue <E>目标结点值
     * @param insertValue <E>新插入的结点值
     * @return 返回插入的结点数
     */
    public int addAftereAll(E aimValue, E insertValue) {
        if(aimValue==null||insertValue==null)
            return 0;
        // 插入值的个数
        int count = 0;
        Node<E> temp = sentry.next;
        while (temp != null) {
            if (temp.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                count++;
                // 由于是在temp后面加了一个指定值，所以要令temp = temp.next.next;
                temp = temp.next.next;
            }
            else {
                temp = temp.next;
            }
        }
        return count;
        
    }

    /**
     * 11. 指定值前面添加节点
     * @param aimValue <E>目标结点值
     * @param insertValue <E>新插入的结点值
     * @return 返回插入是否成功
     */
    public boolean addBefore(E aimValue, E insertValue) {
        if(aimValue==null||insertValue==null)
            return false;
        // 假设我们要在A前插入B，通过检测X.next是否为A来获取A的前驱结点，显然这是一种可行方案
        // 但如果我们传入的不是E，而是装载E的Node，这种方案就不可以接受了
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                return true;
            }
            else {
                temp = temp.next;
            }
        }
//      这里选择通过修改当前节点值的方式插入,如果传入的是一个在链表中的结点，
//      连从头结点遍历至所需结点都省了(当然这里并不是)
//        Node temp1=sentry.next;
//        while (temp1 != null) {
//            if (temp1.item.equals(aimValue)) {
//                Node<E> newNode = new Node<>(temp1.item);
//                newNode.next = temp1.next;
//                temp1.next = newNode;
//                temp1.item=insertValue;
//                return true;
//            }
//            else {
//                temp = temp.next;
//            }
//        }
        return false;
    }

    /**
     * 12. 所有指定值前面添加节点
     * 返回添加的次数
     * @param aimValue <E>目标结点值
     * @param insertValue <E>新插入的结点值
     * @return 返回插入结点的个数
     */
    public int addBeforeAll(E aimValue, E insertValue) {
        // 如果头结点为空，表示一定没有插入的位置，直接返回0。
        if(aimValue==null||insertValue==null)
            return 0;
        // 插入值的个数
        int count = 0;
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue);
                newNode.next = temp.next;
                temp.next = newNode;
                count++;
                // 由于是在temp后面加了一个指定值，所以需要把原来temp.next结点设为新的temp，这样逻辑才正确
                temp = newNode.next;
            }
            else {
                temp = temp.next;
            }
        }
        return count;
    }

    /**
     * 13. 返回链表的头结点
     * @return 头结点
     */
    public Node<E> head() {
        return sentry.next;
    }

    /**
     * 14. 返回链表的尾结点,注意不要返回哨兵结点
     * @return 尾结点
     */
    public Node<E> tail() {
        Node<E> temp = sentry;
        while (temp.next != null) {
            temp = temp.next;
        }
        if(temp==sentry)
            return null;
        return temp;
        
    }

    

    /**
     * 15. 删除指定值一个节点
     * 特殊情况：
     * 如果链表长度为0,或者aimValue为null，直接返回false，
     * @return 成功返回true,失败返回false
     */
    public boolean removeOneNode(E aimValue) {
        if (sentry.next == null || aimValue == null) {
            return false;
        }
        
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                temp.next = temp.next.next;
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    /**
     * 16. 删除指定值所有节点,返回删除的个数
     * @return 返回删除的结点个数
     */
    public int removeAllNode(E aimValue) {
        if (sentry.next == null || aimValue == null) {
            return 0;
        }
        int count = 0;
        Node<E> temp = sentry;
        while (temp.next != null) {
            if (temp.next.item.equals(aimValue)) {
                temp.next = temp.next.next;
                count++;
            }
            else {
                temp = temp.next;
            }
        }
        return count;
    }

    /**
     * 17. 链表按索引位置删除结点
     * @param index 位置索引，合法范围为1~n
     * @return 返回删除是否成功
     */
    public boolean removeNodeByIndex(int index){
        if(sentry.next==null){
            throw new IllegalArgumentException("空链表！");
        }
        if (index < 1 || index > size()) {
            System.out.println("删除的位置不合法。");
            return false;
        }
        int count=1;
        Node<E> previous= sentry;
        while (count<index) {

            previous = previous.next;
            count++;
        }
        Node<E> current=previous.next.next;
        previous.next=current;
        return true;
    }
}

高效的双向链表

image.png

NULL用0表示

考虑链表第一个元素x.ptrdiff =NULL ^ x.next = x.next，即表头存的指针值和普通双向链表表头的next指针相同

中间所有元素x.ptrdiff= x.prev ^ x.next

考虑链表最后一个元素x.ptrdiff = x.prev ^ NULL = x.prev，即链表最后一个元素存的指针和普通双向链表表尾的prev指针相同

我们知道第一个元素的next指针，中间元素的next指针可以通过前一个元素的ptrdiff和当前元素的ptrdiff异或计算获得，这就为前序遍历创造了可能

我们知道最后一个元素的prev指针，中间元素的prev指针可以通过当前元素的ptrdiff和后一个元素的ptrdiff异或计算获得，这就为后续遍历创造了可能

总之，ptrdiff = prev ^ next, NULL = 0致使链表头元素和尾元素ptrdiff值具有了特殊性，这正是此种表示的精妙之处，节省了O(n)的空间开销，但增加了运算开销（位运算），计算机执行位运算具有速度优势。

此种情况下，如果想要翻转链表就变得异常容易，只需要将链表的头尾指针交换即可。

由于java中没有指针运算，我们无法通过指针方便的获取结点地址从而获取结点信息，所以这里了解一下就好了

松散链表

与数组相比，链表给定一个位置的结点情况下，插入和删除只需要 $O(1)$ 的时间开销，但如果只给定位置(或者所需结点的要求)，不给定结点，那么链表就需要从表头遍历至所需结点，时间开销为 $O(n)$ ，下面介绍一种单向链表的简单变形——松散链表。

松散链表的每个结点存储多个元素（简称为块），每一块中所有结点由循环链表连在一起。可以理解为松散链表是由多个块用单向链表方式组成的，而每个块内部是循环链表

image.png

image.png
但是在实际应用中，如
https://stackoverflow.com/questions/38414710/unrolled-linked-list-arrays-vs-nodes/38415481#38415481
https://stackoverflow.com/questions/2956928/data-structure-name-combination-array-linked-list
所讨论的

在块的实现上，我们不采用循环链表，而选择使用数组，因为数组的内存连续性，如果合理安排数组大小，使每个数组（也就是块）的大小不超过一个缓存行（最好是一个缓存行），就可以满足在时间上的优势（原因如下，其实也是显而易见的）

image.png
如以下所论述的：
When constructing unrolled linked lists, apparently implementations will try to generally leave space in the nodes; when you try to insert in a full node, you move half the elements out. Thus, at most one node will be less than half full. And according to what I can find (I haven't done any analysis myself), if you insert things randomly, nodes tend to actually be about three-quarters full, or even fuller if operations tend to be at the end of the list.
简单翻译一下：
在构造松散链表的实现时，通常会对每个块留有足够的空间。当你试图添加一个元素到一个满块中，会将这个块一半的元素移出到别的块。因此，最多只有在开始阶段时一个块元素少于一半容量。并且在随机插入的情况下，每个块大概会有四分之一是空的。

经查阅资料，实际上，在scala中就有一个基于松散链表的基本原理的实现 UnrolledBuffer
https://www.scala-lang.org/api/2.11.7/index.html#scala.collection.mutable.UnrolledBuffer
我们完全可以通过使用一个item为Object数组的单链表，采用和Arraylist类似的实现

class UnrollLinkList<T> {
    class UnrollNode {
        UnrollNode next; // 下一个块
        int num_elements; // 块中的实际元素个数
        Object array[]; // 存储元素的数组

        // Constructor 
        public UnrollNode(int n)
        {
            next = null;
            num_elements = 0;
            array = new Object[n];
        }
    }
    private UnrollNode start_pos; // 第一个块   
    private UnrollNode end_pos; // 最后一个块
    int size_node;  // 每个块可容纳的元素个数
    int nNode;  // 元素总个数

    // Parameterized Constructor 
    UnrollLinkList(int capacity)
    {
        start_pos = null;
        end_pos = null;
        nNode = 0;
        size_node = capacity ;
    }

    /**
     * 插入的逻辑如下（尾插法）：
     * 1. 检查第一个块是否为空，为空则在第一个块中分配相应数组，并为数组第一个元素赋值同时让最后一个块指向第一个快
     * 2. 检查最后一个块是否还能容纳新元素，如果可以则在最后一个块的数组中第一个空闲位置插入
     * 3. 如果不能容纳新元素，则新建一个块，把原最后一个块后一半元素拷贝入新块中，同时更改原最后一个块有效值的索引
     *    将新元素置入新块，再把新块置为最后一个块
     * @param num
     */
    
     
    void Insert(T num)
    {
        nNode++;

        // 1.
        if (start_pos == null) {
            start_pos = new UnrollNode(size_node);
            start_pos.array[0] = num;
            start_pos.num_elements++;
            end_pos = start_pos;
            return;
        }

        // 2.
        if (end_pos.num_elements  < size_node) {
            end_pos.array[end_pos.num_elements] = num;
            end_pos.num_elements++;
        }

        // 3.
        else {
            UnrollNode node_pointer = new UnrollNode(size_node);
            int j = 0;
            for (int i = end_pos.num_elements / 2 + 1;
                 i < end_pos.num_elements; i++)
                node_pointer.array[j++] = end_pos.array[i];

            node_pointer.array[j++] = num;
            node_pointer.num_elements = j;
            end_pos.num_elements = end_pos.num_elements / 2 + 1;
            end_pos.next = node_pointer;
            end_pos = node_pointer;
        }
    }

    // Display the Linked List 
    void display()
    {
        System.out.print("\nUnrolled Linked List = ");
        System.out.println();
        UnrollNode pointer = start_pos;
        while (pointer != null) {
            for (int i = 0; i < pointer.num_elements; i++)
                System.out.print(pointer.array[i] + " ");
            System.out.println();
            pointer = pointer.next;
        }
        System.out.println();
    }
}

显然想要在存储空间均匀分配与空间的利用率上获得好的效果，会有更复杂的增删逻辑，这里只做了解，下一种是更值得我们耗费精力学习的链表结构

跳跃链表

跳跃链表是一种可以替代平衡二叉树的结构，与平衡二叉树相比，这种链表可以迅速执行搜索，插入和删除操作。它的平衡是数学概率的平衡而非平衡二叉树那样严格的平衡。其实这种链表本质上只是普通的单链表上，加入了一些指针使其能够跳过链表中某些元素。它采用随机数生成器来制定某些决策。
对于有序链表而言，其搜索，插入和删除都需要耗费 $O(n)$ 级别的时间，因为需要把所有结点依次扫描才能找到相应结点，如果能以较大的步伐来迈进，那么就可以显著减少扫描的开销，这正是跳跃链表的意义所在。需要注意的是，AVL的实现一般都比较复杂，插入/删除元素可能涉及对整个树结构的修改，特别是并发环境下，通常需要全局锁来保证AVL的线程安全，而跳跃链表在这方面性能要优秀很多。

image.png

用数学方法分析，如果在L1基础上，还有一层L2，设L1长度为n，L2长度为m，则复杂度可表示为 $m+\frac{n}{m}$ （也就是L2的长度加上L1被分割的一节的长度），显然当 $m=\sqrt n$ 时，取到最小值为 $2\sqrt n$ （此时相当于最普通的松散链表）
同理，如果加上一层L3，复杂度为 $3\sqrt[3]{n}$ ，到第k层，复杂度为 $k\sqrt[k]{n}$ ，我们取 $k=\log n$ 时获得最小值， $\log n \cdot\sqrt[\log n]{n}=\log n\cdot n^{\frac{1}{\log n}}=\log n\cdot 2^{\frac{\log n}{\log n}}=2\log n$

在叙述插入操作前，我们应该知道，跳跃表具有以下几个必备的性质：

最底层是一个包含所有节点的有序链表
每一层都是一个有序的链表，由高向低结点数递减
每层的每个节点都有两个指针，一个指向右侧节点（没有则为空），一个指向下层节点（没有则为空）
每层链表的头结点相同，通过它可以遍历整个链表（多数情况下使用哨兵结点）
如果一个结点在上面某一层出现，则它一定也出现在下面所有层中

image.png

注意红线表示查找的过程

算法导论中，对插入策略的叙述如下：
对每个新添加的结点，采用类似抛硬币的方法，各有二分之一的概率选择使其升层，比如当其从L1提升至L2时，继续做随机的检测，直至检测失败为止，此时，这个结点出现在level=k及以下所有层中，如果k大于最高层，则新建一层，之后我们从高向低，依次将结点插入入每层链表中
这种方式在数学上能保证其层数小于等于 $\log n$ 的概率在 $1-\frac{1}{n^\alpha},\alpha\in(0,1)$ 间

而删除操作也很简单，需要从左上方开始查找直至找到相应元素，让后把这个结点以及其所有向下指向的结点全部删除

在代码实现上

image.png

想要真正理解跳跃表，参见ConcurrentSkipListMap的源码解析

习题解答

image.png

上图中，设环外有k步，快慢指针相遇在环中蓝色delta位置处，环的入口为红色位置，环的长度为R

必然相遇的证明
1、如果链表没有环，那么快指针比慢指针先到达尾部（null)。
2、如果链表有环的话，因为快指针走的比慢指针快，所以在环中相遇的过程可以看作是快指针从环后边追赶慢指针的过程。
用递归法证明，快慢指针一定会相遇：
（1)快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
（2)快指针与慢指针之间差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。
（3)快指针与慢指针之间差x步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(x+1-2)即x-1步。重复这个过程，直到快指针和慢指针相遇。
因此，此题得证。所以快指针必然与慢指针相遇。

同时显然快指针先进环，慢指针后进。
假设慢指针进环那一刻快指针差m步能追上（0<= m < R），根据上边结论，两个指针走m次就会相遇了。因为m < R，所以快指针在慢指针进环那一刻最多比慢指针多绕一个圈。
也就是说慢指针被追上时，在环中没有走完一圈。有等式
$2(k+\delta)=k+m+xR$ ，等号左边是满指针的两倍距离，等号右边是快指针的距离（x表示绕了多少正整数圈）
即 $k+\delta=xR$ ，显然如果环不存在，则等式不成立，R至少为1才能使等号成立（为1时相当于尾结点指向自身）

image.png

正如上文分析的那样，从 $\delta$ 处走 $k$ 步，正好等于在环的入口处走 $xR$ 步回到环的入口，而 $\delta$ 通过快慢指针相遇可以求出来，未知的k正好可以通过重新设定位置和速度再次相遇而求出，此时两者相遇位置正好是环的入口处

image.png

原地的链表迭代逆置参考如下图

image.png

方法2：头插法逆置
分为两种情况：①链表为空或者链表中仅有一个节点，直接返回pHead ②链表中有多个节点时：将pHead后面的节点依次插入到头结点的后面，这样显然需要一个新的链表结构存储，时间复杂度O(n)，空间复杂度O(n)
方法3：递归逆置

 Node reverse3(Node head) {
        //递归出口
        //注意这里加入对head.next==null的判断，防止下文中的head.next.next出现空指针异常
        if (head == null || head.next == null)
            return head;
        //递归子情况
        Node pre = reverse3(head.next);
        head.next.next = head;  // 这一步会造成环
        head.next = null;  // 这一步是为了断开环
        return pre;
    }