数据结构----链表

标签：Node ---- head cur next 链表数据结构节点

接下来我打算更新数据结构相关方面的知识，使用的语言是Java，但是其中的逻辑和思路并不影响。如果感兴趣可以关注合集。

希望大家看完之后可以自己去手敲实现一遍，同时在最后我也列出一些基本和经典的题目，可以尝试做一下。大家也可以自己去力扣或者洛谷牛客这些网站自己去练习，数据结构光看不练是学不好的，加油，祝你早日学会数据结构这门课程。

有梦别怕苦，想赢别喊累。

链表的概述

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。这与我们所认识的数组有相同之处，二者都是线性集合，但是数组在元素存储上是连续的。

链表的分类

1.单向链表：每个元素只知道其下一个元素是谁，最后一个元素（tail尾节点）的下一个元素指向是null。

2.双向链表：每个元素知道其上一个元素和下一个元素，最后一个元素（tail尾节点）的下一个元素指向是null，第一个元素（head节点）的上一个元素指向是null。

3.循环链表：通常的链表尾节点tail指向的都是null，而循环链表的tail指向的是头节点head。

特殊：哨兵节点：链表内还有一种特俗的节点称为哨兵节点，它不负责存储数据，通常用作头尾，用来简化边界判断，如虚拟头节点dummyhead等。

链表的性能

访问操作

因为链表在存储上并不连续，所以并不支持像数组一样的直接寻址访问（通过索引），因此链表的每次访问操作都要从头节点开始一个一个往下找，所以访问操作的时间复杂度是O(n)。

插入和删除操作

对于插入和删除操作，如果我们已经知道待操作节点的位置，那么单是操作都是常数级别的时间复杂度O(1)。但是如果不知道待操作节点的位置，那么我们就要先访问到当前节点再进行操作，也就是O(n)+O(1)。

单链表的实现

结构

链表是由许多节点组成的，所以我们研究链表的结构就是要搞清楚节点的结构。单向链表的节点是由两部分组成的，一个是待存储的值value，一个是指向下一个节点的next指针（在Java中指针就是引用，所以就是Node类型）。

/*
*  节点类
*/
private  static class Node{
    int value; //值
    Node next; // 指向下一个节点指针

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

同时对于一条链表，我们还需要一个头节点，来作为我们链表的起点，最后我们链表的整体结构就搭建完了。

//单向链表
public class singlyLinkedList { //整体
    /*
     *  节点类
     */
    private static class Node{
        int value; //值
        Node next; // 下一个节点指针

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node head;
}

添加节点

在链表头部添加节点（addInHead)

在链表头部添加节点就是创建一个新节点，让该节点作为新的头节点。

如果链表为空，那么新节点的next指针指向null。如果链表非空那么新节点的next指针指向head。并把新节点赋值给head。我们会发现无论链表是否为空，我们都可以直接将新节点的next指针指向head。

//在头部添加节点
public void addInHead(int value) {
        // 1. 链表为空
//        head = new Node(value, null);
        //2.链表非空
        head = new Node(value, head);
    }

下面我拆解一下这一行吧，好像对于刚开始学习的人来说这一行理解起来有点复杂。

我们要在链表头部添加一个节点所以我们首先1.需要new一个新节点cur，然后我们要将当前节点与之前的链表相关起来，也就是2.把cur的next指针指向head，这样该节点也就添加到了链表的头部，又因为该节点现在是链表的头节点，3.所以我们要把该节点赋值给head来维护头节点。

        // 1.new 新的待添加的节点
        Node cur = new Node(value, null);
        // 2.将新节点添加到链表头部
        cur.next = head;
        //  3.维护head变量，因为head永远表示头节点
        head = cur;

自绘图，太丑勿喷。按着步骤对着上面代码一起看更好理解。

在学习在链表尾部插入节点之前，我们先需要学习一下链表的遍历，因为不会链表的遍历，我们怎么到达链表的尾部呢，到不了链表的尾部谈何在链表尾部添加呢。

链表的遍历

迭代遍历（forEach)

对于一条链表我们只能知道它的头节点，而对于链表中每个节点我们都能通过next指针找到他的下一个节点，而链表的尾节点的next指针一定指向null。基于这个特性，我们可以一直通过next指针找下去，直到next指针为null时代表我们当前来到了链表的尾节点。

//遍历
public void forEach() {
        Node cur = head;
        while (cur != null) {
            System.out.println(cur.value);
            cur = cur.next;
        }
    }

注意！！！

这里我们是用了一个cur变量代替head不断去找下一个节点，这里不能直接用head，因为head始终要指向链表的头节点，是我们要维护的，简单来说就是，如果我们用head去找，那么我们下次使用head他就不代表链表头节点了，同时我们也找不到链表头节点了。

遍历链表这里我把它写死了，都是把他每个节点的值都打印出来。同样这里也可以不打印，去实现外部调用者来自己决定遍历时需要进行的处理，用一个Consumer变量去接收参数再调用accept方法，当然这不是重点。

头部插入节点我们之前已经实现了，现在我们又把遍历实现了，接下来我们就可以测试一下这两个方法。

    @Test
    public void test01(){
        singlyLinkedList list = new singlyLinkedList();
        list.addInHead(1);
        list.addInHead(2);
        list.addInHead(3);
        list.addInHead(4);

        list.forEach();
    }

测试显示通过，同时打印4321，没有任何问题。

递归遍历

链表也可以进行递归遍历，这里也是很好实现，递归终止的条件就是当前节点来到了链表尾部就停止递归，否则就打印当前节点，然后调用下一层递归。这里可以试试把递归函数的调用和打印语句调换位置你会发现链表的打印是逆序的，相信这里你只要仔细思考一下递归的执行过程也不难想到其中的原理。

    //递归遍历
    public void recursion(Node cur) {
        if (cur == null) {
            return;
        }
        System.out.println(cur.value);
        recursion(cur.next);
    }

对于其它遍历的方法，例如什么重写迭代器，这里就不做过多概述，大多数情况上面那两种已经能够满足所有需求了

在链表尾部添加节点（addInTail）

如果我们想在链表尾部添加节点，那么通过我们上面所学的我们就可以遍历链表找到链表的最后一个节点，任何让它的next指针指向我们想添加的节点就好了。对于链表的最后一个节点有一个特性就是它的next指针指向null，所以我们不难写出下面的代码。

    //寻找最后一个节点
    private Node findLast() {
        if (head == null) return head; //空链表

        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }

不要忘了链表为空时，特殊处理一下。

接着我们既然得到了链表的最后一个节点，那么在这个节点后面添加一个节点，想必对你来说都是易如反掌，不要忘了空链表时特殊处理。

    //在尾部添加节点
    public void addInTail(int value) {
        Node tail = findLast();
        if (tail == null) {
     //链表为空时也就是在头部添加一个节点，直接调用之前写好的方法
            addInHead(value);
            return;
        }
        
        tail.next = new Node(value, null);
    }

写完一个方法可以去测试一下，当然也是没有问题的。

根据索引获取节点的值（get）

既然数组支持我们通过索引进行直接寻址访问，那么我们也可以让链表也实现通过索引获取节点，我们来看一下该怎么实现。

既然是通过索引实现，那我们在调用该方法的时候一定要给它传一个参数代表索引index，

接着我们在遍历的时候用一个变量去记录当前遍历到的节点的索引，如果等于index我们就返回当前节点。这样我们就实现了根据索引获取节点。

    //根据索引获取节点的值
    public int get(int index) {
        int currentIndex = 0;
        Node cur = head;
        while (cur != null) {
            if (currentIndex == index) {
                return cur.value;
            }
            cur = cur.next;
            currentIndex++;
        }
        throw new IllegalArgumentException("索引越界");
    }

对于索引小于0和超出索引范围的我们可以抛出异常也可以返回特定值。

又写完了一个方法再去测试一下，当然也是没有问题的。

插入节点（insert）

前面我们学会了往链表头部和尾部插入节点，现在我们来实现一下向链表任意地方插入节点，也可以理解为通过索引插入节点。

我们可以仔细思考一下如果我们想实现在索引index处插入一个新节点cur，那么我们应该怎么做呢？不难想出我们只要让索引为（index-1）的节点pre的next指向新节点，并让cur的next指向索引为pre的next原来指向的节点。看图更好理解。

这里有必要解释一下为什么右边是第一步呢，因为如果我们把左边变成第一步，那么pre的next也就指向了cur，那这时我们再进行第二步就等同于把cur的next指向cur自己，也就让cur形成了自环，所以这里要留心一下顺序。

对于索引越界的情况我们只需要特殊处理一下就行了，另外还有一种特殊的情况就是索引为0时也就是在链表头部插入一个节点我们可以直接调用前面写好的方法。对于这一种情况我们后面可以用虚拟头节点来实现统一处理。

    //向索引位置插入
    public void insert(int index, int value) {
        //在头部插入节点
        if (index == 0) {
            addInHead(value);
            return;
        }

        //找到待插入索引的上一个节点
        int currentIndex = 0;
        Node pre = head;
        while (pre != null) {
            // 上一个节点所以是index-1
            if (currentIndex == index - 1) {
                break;
            }
            pre = pre.next;
            currentIndex++;
        }

        //没有找到
        if (pre == null) {
            throw new IllegalArgumentException("索引越界");
        }

        Node cur = new Node(value, null);
        //第一步
        cur.next = pre.next;
        //第二步
        pre.next = cur;

        //上面三行可以简化成下面这一行
//        pre.next = new Node(value, pre.next);
    }

又写完了一个方法再去测试一下，当然也是没有问题的。

删除节点

删除头节点（removeFirst）

如果我们想删除链表中的第一个节点，非常简单。我们只需要把head变成head指向的next就行了。不要忘了空链表特殊处理。

    //删除第一个节点
    public void removeFirst() {
        if (head == null) { //链表为空
            return;
        }
        head = head.next;
    }

根据索引删除节点（remove）

如果我们想根据索引index删除一个节点cur，那我们只要把cur上一个节点pre的next指向断开，然后重新指向cur的next指向的节点。这样我们就实现了删除cur节点，另外使用c,c++语言的不要忘记手动释放内存。

这里存在三种特殊情况，前面两种都是常见的，第一种是pre节点不存在，第二种就是index等于0直接删除头节点，第三种特殊情况就是pre节点存在但是cur节点不存在。

    //根据索引删除节点
    public void remove(int index) {
        //1.删除头节点
        if (index == 0) {
            removeFirst();
            return;
        }

        //找到待删除节点的上一个节点pre
        int currentIndex = 0;
        Node pre = head;
        while (pre != null) {
            if (currentIndex == index - 1) {
                break;
            }
            pre = pre.next;
            currentIndex++;
        }

        //2.没有找到pre节点
        if (pre == null) {
            throw new IllegalArgumentException("索引越界");
        }

        //3.待删除节点cur不存在
        Node cur = pre.next;
        if (cur == null) {
            throw new IllegalArgumentException("索引越界");
        }

        pre.next = cur.next;
        //上面两行也可以写作一行
//        pre.next = pre.next.next;
    }

虽然看着代码有点长，但是里面的逻辑都是我们之前实现过的，仔细看一下也是不难的。

带哨兵的单向链表

在上面我们实现的单向链表的功能中，对于很多地方我们都是if特殊处理的，相对来说就是我们的代码还不够强大。接下来我们就认识一下哨兵节点来健壮一下我们的代码。

哨兵节点，它不负责存储数据，通常用作头尾，用来简化边界判断，如虚拟头节点dummyhead等。

在之前我们head头节点一开始就是null，当链表不为空时head就代表代表第一个节点。现在我们可以让head一开始就设置成一个节点，然后将head节点就作为我们的哨兵节点，一开始它的next指向null。由于哨兵节点不负责存储数据，所以值可以随便设，我这里就设置成了一个整型最大值。

private Node head = new Node(Integer.MAX_VALUE, null);

设置完哨兵节点之后我们会发现，链表一开始就不会是空链表了，它一开始最少也有一个哨兵节点。所以在我们之前写的在链表尾部添加节点时的特殊处理就可以删掉。注释掉的地方就是做的改动。

    //寻找最后一个节点
    private Node findLast() {
 //       if (head == null) return head; //空链表
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }
    //在尾部添加节点
    public void addInTail(int value) {
        Node tail = findLast();
   //     if (tail == null) {
     //链表为空时也就是在头部添加一个节点，直接调用之前写好的方法
 //           addInHead(value);
 //           return;
  //      }
        tail.next = new Node(value, null);
    }

接着就是我们来看一下我们的链表遍历，由于哨兵节点存储的值没什么实际意义，所以我们遍历时的起点应该是head的next指向的节点，head的next指向的节点就是我们这条链表真正的头节点。

    //遍历
    public void forEach(Consumer<Integer> consumer) {
        Node cur = head.next;
        while (cur != null) {
            consumer.accept(cur.value);
            cur = cur.next;
        }
    }

还记得我们在根据索引删除和插入节点时候，对于索引为0时的特殊处理吧。这里既然我们链表的起点是head的next，那索引为0的节点也就是head的next，那head哨兵节点的索引就是-1。那我们在找待插入节点的上一个节点时我们还是从head开始，同时变量记录也应该从-1开始，这时我们会发现普通的情况没问题，当索引为0时的情况也不需要特殊处理了，这就是哨兵节点的好处。这里只贴了insert方法的代码，remove方法同理。

     //向索引位置插入
    public void insert(int index, int value) {
        //找到待插入索引的上一个节点
        int currentIndex = -1;
        Node pre = head;
        while (pre != null) {
            if (currentIndex == index - 1) {
                break;
            }
            pre = pre.next;
            currentIndex++;
        }

        //没有找到
        if (pre == null) {
            throw new IllegalArgumentException("索引越界");
        }

        Node cur = new Node(value, null);
        //第一步
        cur.next = pre.next;
        //第二步
        pre.next = cur;

        //上面三行可以简化成下面这一行
//        pre.next = new Node(value, pre.next);
    }

接着我们来看一下最后要改的地方，在链表头部添加元素，如果按照我们之前的做法那哨兵节点head就会被覆盖，head节点又变回了链表的第一个节点，我们只需要调用inset方法在链表头部插入元素就行了。removerFirst()方法同理，调用remove(0)就可以了。

    //在头部添加节点
    public void addInHead(int value) {
        insert(0,value);
    }

双向链表的实现（带哨兵）

接下来我们来学习一下双向链表，这里我们直接来学习带哨兵节点的双向链表，一方面是好用，另一方面就是有了带哨兵单向链表的基础再学习这个也是趁热打铁，事半功倍。

结构

同单向链表一样双向链表也是由许多节点组成的，只是节点的结构有所不同。双向链表的节点是由三部分组成的，，一个是指向上一个节点的prev指针，一个是待存储的值value，一个是指向下一个节点的next指针。

    /*
     *  节点类
     */
    private static class Node {
        Node prev; // 上一个节点指针
        int value; // 值
        Node next; // 下一个节点指针

        public Node(int value, Node next, Node prev) {
            this.value = value;
            this.next = next;
            this.prev = prev;
        }
    }

一开始一条双向链表是没有节点的，但是我们这是带哨兵节点的双向链表，所以要有两个哨兵节点，一个是哨兵头节点head，一个是哨兵尾节点tail。那么这两个哨兵节点是随着双向链表的创建而创建的，所以可以直接把两个哨兵节点的初始化写在双链表的构造函数中，并让哨兵头节点head的next指针指向哨兵尾节点tail，哨兵尾节点tail的prev指针指向head节点，这样双向链表的结构就构建完了。

//双向链表
public class bothwayLinkedList {
    /*
     *  节点类
     */
    private static class Node {
        Node prev; // 上一个节点指针
        int value; // 值
        Node next; // 下一个节点指针

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node head;
    private Node tail;

    public bothwayLinkedList() {
        this.head = new Node(null, Integer.MAX_VALUE, null);
        this.tail = new Node(null, Integer.MIN_VALUE, null);
        head.next = tail;
        tail.prev = head;
    }
}

根据索引查找节点

我们先来实现一个工具方法----根据索引查找节点，因为我们在根据索引插入和删除节点的时候都需要这一步，所以为了避免代码冗余，我们可以将这一步抽取成一个方法。

由于我们存在了哨兵头节点，那么我们开始的索引可以从-1开始，这样我们就可以找到索引为0的节点（双链表实际的第一个节点）的前一个节点，从而实现对索引为0的节点进行插入和删除。接着我们在遍历时因为链表最后一个节点时哨兵尾节点，所以遍历时的结束条件就可以设置为走到tail节点就停。最后如果没有找到我们就返回null。

    //根据索引查找节点
    private Node findNode(int index) {
        int currentIndex = -1;
        Node cur = head;
        while (cur != tail) {
            if (currentIndex == index) {
                return cur;
            }
            cur = cur.next;
            currentIndex++;
        }
        return null;
    }

根据索引插入节点

对于双向链表的根据索引插入节点，我们还是只要找到待插入索引节点cur的前一个节点pre就行了吗？当然不够，我们还需要找到待插入索引节点的后一个节点after才行，因为要让后一个节点after的prev指针指向待插入索引节点cur，这样才建好连接。

先把待插入节点的指针给设置好，也就是一二步（可以直接在创建节点的时候就给上构造参数），然后再分别设置三四步。对着图和代码一起看。

    //根据索引插入节点
    private void insert(int index, int value) {
        //找到索引为index节点的上一个节点
        Node pre = findNode(index - 1);
        //如果没找到就特殊处理
        if (pre == null) {
            throw new IllegalArgumentException("索引越界");
        }
        //找到索引为index节点的下一个节点
        Node after = pre.next;
        //创建一个新的节点,并设置好一二步
        Node cur = new Node(pre, value, after);
        //第三步
        pre.next = cur;
        //第四步
        after.prev = cur;
    }

这样我们就实现好了根据索引插入节点，对于当索引等于0，在头部插入节点这种特殊情况，我们可以找到索引为0节点的前一个节点，所以这种特殊情况也是可以解决的。

    //在头部插入节点
    public void addInHead(int value) {
        insert(0, value);
    }

根据索引删除节点

同理，也是找到待删除节点cur的上一个节点pre和待删除节点cur的下一个节点after，然后改变pre的next指向直接指向after，同时让after的prev指针指向pre节点就好了。

这里存在两种特殊情况，第一种就是没有找到待删除节点的前一个节点，第二种就是待删除节点刚好是哨兵尾节点，是不可以删除的。

    //根据索引删除节点
    public void remove(int index) {
        Node pre = findNode(index - 1);
        if (pre == null) {
            throw new IllegalArgumentException("索引越界");
        }
        Node cur = pre.next;
        if (cur == tail) {
            throw new IllegalArgumentException("索引越界");
        }
        Node after = cur.next;
        pre.next = after;
        after.prev = pre;
    }

    //删除第一个节点
    public void removeFirst() {
        remove(0);
    }

在链表尾部添加节点

双链表的优势在于我们设置了哨兵尾节点，同时每个节点我们又存在prev指针指向上一个节点，所以我们就可以不用像单链表那样从头遍历到尾再进行插入，现在我们可以用O(1）的时间复杂度实现，逻辑和插入节点是一样的。

    //在链表尾部添加节点
    public void addInTail(int value) {
        Node pre = tail.prev;
        //创建一个新的节点,并设置好一二步
        Node cur = new Node(pre, value, tail);
        //第三步
        pre.next = cur;
        //第四步
        tail.prev = cur;
    }

在链表尾部删除节点

同理，我们只需要通过尾哨兵节点的prev指针拿到待删除节点cur，再通过cur的prev指针拿到上一个节点pre，然后把pre节点的next指针指向tail节点，把tail节点的prev指针指向pre节点，注意如果此时cur节点为哨兵头节点我们不可以删除要特殊处理一下。

    //删除链表尾部节点
    public void removeLast() {
        Node cur = tail.prev;
        if (cur == head) {
            throw new RuntimeException("链表为空,无法删除");
        }
        Node pre = cur.prev;
        pre.next = tail;
        tail.prev = pre;
    }

遍历链表

遍历双向链表可以从头往尾遍历也可以从尾往头遍历。这里我就从头到尾遍历。遍历时的终止条件就是当前节点来到tail节点。

    //遍历
    public void forEach(Consumer<Integer> consumer) {
        Node cur = head.next;
        while (cur != tail) {
            consumer.accept(cur.value);
            cur = cur.next;
        }
    }

最后我们完成了我们带哨兵的双向链表，我们可以来测试一下，当然我建议写完一个方法就可以测试一下，不要像这样全部完成再测试。

    @Test
    public void test01(){
        bothwayLinkedList list = new bothwayLinkedList();
        list.addInHead(1);
        list.addInTail(3);
        list.insert(1,2);
        list.forEach((value)-> System.out.print(value+" "));
        System.out.println();
        list.removeFirst();
        list.removeLast();
        list.forEach((value)-> System.out.print(value+" "));
        System.out.println();
    }

测试通过，打印的结果也是没有问题。

有了单向链表和双向链表的基础，最后一个环形链表，尝试一下看自己能不能实现出来吧。