链表真的那么难吗? 基础＋练习带你领略链表的奇妙之处

引言：

        链表是java语言开发中常见的一种数据结构，应用也很广泛。比如linked系列的Collection子类集合，以及Map下的HashMap和ConcurrentHashMap等等，都或多或少的用到了链表结构，来优化其元素的增删效率。

      之所以写这篇博文，是因为CSDN每日一练中有些题涉及到了链表，特别是链表反转，颇为让人头疼，经过几天的琢磨，今天想着分享一下自己对链表的理解与心得，也希望码友们有一天碰到类似问题，可引以为参考。

一、链表介绍

     1）链表是一种物理存储单元上非连续、非顺序的存储结构，区别于数组，数组在内存中固定分配一块连续的内存，来存储其元素。什么是连续, 就是这些元素放在一起方便快速寻找，他们每个都会被数字来标记，这些数字就是下标也即索引，他们必须是0、1、2、3、4这样具有连续性，就像是军训时的队列，只有顺序编号没有名字一样。

而非连续意味着，他们散落在堆中的某些地方，各自有自己名字，如果你记得我，肯定是记得我的名字而不是我的编号，这样你找我时需要打电话确认我在哪里，然后走很远找到我，也因此链表查询效率较低，但是如果你与我绝交，你只需要忘记我即可，这里指删除。反观数组，如果队列里某个调皮的学生请假了，队列编号需要重新调整，并且位置也要调整。

     2）链表由一系列节点（Node）组成，且节点与节点之间单向或双向相连，即 N.next 指向 N+1或N.previous指向N-1，或两者结合。next和previous其实就是指向其它元素的引用。

    3）链表的单个节点组成部门由当前节点的描述信息与下一个或前一个节点的指针域或两者并存的指针域组成。

   4）链表插入的时间复杂度为O(1)，查找和访问特定节点则需要O(n)的时间。

二、链表的应用

1）linkedList

     linkedList是有序且增删效率较高的线性双向链表之一。双向链表其实也没那么高深莫测，就是比普通链表多了一个指向前置节点的引用。下面是linkedList的节点类，大家可以看看

private static class Node {
    // 当前节点描述信息
    E item;
    // 指向 N + 1 节点的指针域
    Node next;
    // 指向 N - 1 节点的指针域
    Node prev;
    
    // 带参构造 Parameterized constructor
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

  

  2） HashMap

        HashMap，底层其实是数组+链表+红黑树这样一个组合式数据结构，目的是为了更好的改善随着数据量增加而面临的增删改查效率问题。既然到到这儿了，也顺表讲一下为何HashMap会用到链表。大家都知道，HashMap使用hash值来索引元素，尽管hash算法可以让hash值唯一，但不是绝对的，因此在数据量特别庞大时，就会出现hash值碰撞，即两个元素计算出来的hash值一样，如果一样两个元素放到数组中不就被其中一个覆盖了吗？当hash值碰撞，就将新元素的引用赋值给数组中同样hash值的另一个元素的next指针域，接下来重复这样的操作就可以了。红黑树是什么呢？红黑树和AVL树很相似，只是前者多了红黑节点标识的特征。但他们的出现都是为了解决搜索性能相关问题的，这么说你就明白红黑树的意义了。链表的问题是当数据里大时，搜索性能会大打折扣，这时红黑树的作用不言自明。

放个图理解更好：这个是我从百度找的，大家看一下，画的非常好，红黑树都包括了。

嗯，感觉有些跑题了，但是这些知识本来就是互相关联的，举一反三。 

 下面是HashMap的链表节点类，这是一个普通链表：

static class Node implements Map.Entry {
    // 节点描述信息
    final int hash;
    final K key;
    V value;
    // 指向下一个节点的指针域
    Node next;

    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

        //  Methods follow

       ......

} 

   单向链表图解： 

 其它linked系列的，除此之外还有ConcurrentHashMap都使用了链表结构，我这里就不一一列举了，码友们可以自己去阅读源码，一探究竟。

三、链表的操作

        1）增删改查

此处，就不细讲了，本博文侧重点是反转。

        2）遍历和搜索。这个要着重说一下，因为linkedList中用到了简单的二分搜索，相比于线性搜素，效率更高。

Node node(int index) {
    // assert isElementIndex(index);
    
    // size是链表长度，右移1位,相当于 size / 2. 为了更快命中目标，
    // 需要利用linkedList中的first和last节点。当index < (size >> 1)，
    // 意味着该节点处于链表的左侧部分，我们就需要从左向右遍历
    // 反之从右向左遍历
    if (index < (size >> 1)) {
        // 左向右
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 右向左
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

四、练习       1） 反转链表。给你一个单向链表，你能不能把它反转过来？大家可以先不看代码，自己写一遍，再来看，会有很大收获！

什么是反转链表？比如某个链表是这样的，为了方便理解，我使用有序字符，A => B => C => D，反转后就是 D => C => B => A。它不像数组反转，使用任何一个排序算法即可解决。下面是代码，大家看一遍，后面我详细分析反转流程以及总结

    private static ListNode nodeReverse(ListNode head){
        ListNode pre = null, tmp;
        while (head != null){
            tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }

pre变量是反转后我们需要交代的数据，temp，当交换数据时，用来临时存储数据。

while循环出口：当遍历到最后节点时，while循环结束，因为尾部节点的next指向的是null！

第一圈时：tmp= 'B'；head.next = pre = null; pre = head = 'A'; head = tmp = 'B';

第二圈时：tmp = 'C'; head.next = pre = 'A'; pre = head = 'B'; head = tmp = 'C';

第三圈时：tmp = 'D'; head.next = pre = 'B'; pre = head = 'C'； head = tmp = 'D'; 

第四圈时：next = null; cur.next = pre = 'C'; pre = head = 'D'； head = tmp = 'null';

此时，循环结束，链表反转成功。

这里的pre相当于一个新的容器, 用来存储反转后的节点。

 我们假设一个场景：

        tmp是head的辅助。他们要从出发点A走到D，head负责记住自己走过的路，tmp负责记录下一步要走的路。pre则在终点等着它们，当head每走到一个地方，都需要向pre报告，pre则为head记录每次走过的路线，因此pre为head做的记录是倒着的，最后由辅助tmp告诉head下一个要怎么走。

第一次，head自己看了地图，发现自己的下一步是B，就把地图给了tmp，说我们下一步要走到B，此后，地图交给你，我不在负责下一步的分析，但是我需要记住上一步走的地方，tmp鞠了躬，说："当然，在下之荣幸。"  走完A，head打电话告诉pre，我们走完A了，你帮我记录一下。

....

第四圈，head与tmp两人走完了全程，根据每个人的职责，

pre记录的是：

①  A；② B => A；③ C => B => A；④ D => C => B => A；

head的记录是(.next的值)：

null(出发)；① A；② B；③ C；④ D；

tmp的记录是：

①：B => C => D；② C => D；③ D; ④ null(行程结束)；

链表全反转，就讲到这里，下面我们一起讨论反转链表的某一个段落；

2）根据提供的区间，来反转该链表区间内的所有节点。有链表 A => B => C => D => E, m = 2, n = 4, 请将该区间内的链表进行反转。

1、先创建一个空节点或者说是虚拟节点，作为存储反转链表的容器；

2、找到区间头节点的上一个节点；

    // 虚拟节点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    // pre为dummy的副本， tmp为临时存储容器
    ListNode pre = dummy, tmp;
    // 遍历到m - 1的位置，也就是区间头节点的上一个节点
    for(int i = 1; i < m; i++) {
       pre = pre.next;
    }

2.1 这里解释一下为何是dummy.next = head 而不是 dummy = head; 当遍历的区间开始节点是全链表的头节点时，也就是pre=head，pre.next是无法指向头节点的，因此我们需要为pre前置一个虚拟节点，来指向head即头节点。            

3、取出区间头节点

4、开始遍历并发转

   // 取出区间的头节点
   head = pre.next;
   for(int i = m; i < n; i++){
      // tmp临时存储遍历的剩余部分节点
      tmp = head.next;
      // 准备下一个要遍历的节点
      head.next = tmp.next;
      // 开始反转
      tmp.next = pre.next;
      pre.next = tmp;
 
   }

下面我通过两个步骤，画了一张反转m to n之间的过程

 五、总结

1、反转链表需要注意两大点

     1）在反转的过程中要确保链表的遍历能够正常完成

     2）为了避免原链表与反转后的链表互相干扰或藕断丝连，应尽量重新定义一个节点，来链接反转后的顺序节点。当然练习第一题的代码并不是按照这个原则来做的，但是tmp作为保证遍历的顺序进行的关键，始终没有被篡改，因此在head原链表被修改之后，tmp又将本属于head的值赋给了它，以保证遍历的顺序执行。

以上是我对链表的理解，以及对链表如何反转的一些见解和经验，原创不易，希望您高抬贵手一键三连。最后再给大家留一个题，就是如何反转双向链表？有思路的同学可以在评论区留言，共同讨论