手撕数据结构与算法

前言

底层基础决定上层发展。

点个赞在看，让我知道你在关注技术。

本系列文章Github 后端进阶指南 已收录，此项目正在完善中，欢迎star。

本系列内容预览：

1. 什么是链表？

链表也是线性表中的一种，数组是线性表中的顺序结构，而这次说的链表是线性表的链式存储结构，它在内存中是非连续、非顺序性的数据结构，由若干个节点组成。它每个节点中都会存储数据和下一个节点的地址，存储数据的叫做数据域，存储地址的叫做指针域。指针分为前驱指针、后继指针，分别用来记录前一个节点和后一个节点的位置。

指针：将某个变量赋值给指针，实际上就是将变量的地址值赋值给指针，可以看做Java当中的引用。

1.1 单向链表

单向链表，顾名思义就是只有一个方向的链表，从上图中来看，一个单向链表由若干个节点组成，每个节点又分为两个部分，一部分存放数据，一部分存放下一个节点的位置。用图来说话就是橘色的方块叫做数据域，里面用来存放数据data。而黄色的方块叫做指针域，用来存放下一个节点的位置next（注意是下一个节点的位置，不是下一个指针的位置），这个next又被称为后继指针。

大家观察上面的图，有两个地方比较特殊，那就是第一个节点和最后一个节点。我们还可以称作头结点、尾结点。这两个节点有什么特别之处呢？那就是头结点可以不存数据，作为链表的开始，而尾结点的后继指针指向null，代表这是链表的最后一个节点。

头节点：链表中第一个节点，头节点中可以不存储数据。

头指针：链表中第一个节点的指针，用来存储链表的基地址，是整个链表的开始。

尾节点：链表中最后一个节点，指向一个空null，代表这是链表的最后一个节点。

1.2 单向循环链表

单向循环链表是从单向链表衍生出来的，它和单向链表的唯一区别就是单向链表的尾结点的后继指针指向了null，而单向循环链表的尾结点后继指针指向了头节点。这种首尾相连的单链表称单向循环链表。循环链表的优点就是从链尾到链头比较方便，处理环形结构问题时比较适用，比如著名的约瑟夫问题。

1.3 双向链表

双向链表稍微复杂一些，它和单向链表相比除了后继指针以外还多了个前驱指针。如果存储同样多的数据，双向链表比单向链表占用更多的空间，虽然双向链表中的两个指针很浪费空间，但可以支持双向遍历，也给链表本身带来了更多的灵活性。

1.4 双向循环链表

了解了循环链表和双向链表之后，把这两个组合在一起就是双向循环链表，大家看图就知道了，头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。这里就不做过多介绍了，大家知道链表都有哪几种就可以了。

2. 链表VS数组

说了半天链表，不知道大家了解了没有，我自己都感觉很枯燥。可是基础就是这样，只有学好了基础才能更好的向上爬。现在我们来看下链表和我们之前讲的数组有什么区别。首先它们两个的存储结构就不一样，数组是顺序存储结构，也就是说它在内存中是一块连续的存储空间，而链表是链式存储结构，也就是非连续的。我们来看下它们在内存中表现：

通过图片，相信大家已经看出来区别了，由于数组是连续的存储结构，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。由于数据结构的不同，导致数组和链表的插入、删除、随机访问等操作的时间复杂度正好相反。

链表天然的支持动态扩容，因为它不是预先生成内存空间，只有真正使用的时候才会去开辟一块内存空间。而数组就不行，数组的缺点就是大小固定，申请多了浪费，申请少了还得频繁的扩容、搬移数组，如果数据量大了很耗时。所以大家在使用List的时候也是，如果能够事先预估数据量的大小，那么在初始化的时候最好指定下大小，避免扩容时搬移数据带来影响。

3. 链表的基本操作

3.1 链表的增加

链表的增加操作，一共有三种情况：

• 增加到头部

  

  增加到头部一共分为两步，第一步将新节点的后继指针指向原头节点，第二步是将新节点变为头节点。这样就完成了头部添加。

• 增加到中间

  

  中间插入也分为两步，第一步将插入位置的前边节点的后继指针指向新节点，第二步是将新节点后继指针指向插入位置的原节点。

• 增加到尾部

  

  链表的尾部插入最简单，只需要将最后一个节点的后继指针指向新节点就可以了。

我们来看下代码，如果大家时间充沛，建议自己手动敲一遍，这样会理解的更深刻。

/**
 * @author: lixiaoshuang
 * @create: 2019-12-08 23:11
 **/
public class LinkedListAddDemo {

    //头节点
    private static Node headNode = null;
    //尾节点
    private static Node lastNode = null;
    //链表的长度
    private static int size;

    public static void main(String[] args) {
        //初始化一个链表
        addByIndex(1, 0);
        addByIndex(2, 1);
        addByIndex(3, 2);
        addByIndex(4, 3);

        //头部插入
        addByIndex(5, 0);
        printNode();   //输出 5、1、2、3、4
        //中间插入
        addByIndex(5, 2);
        printNode();   //输出 1、2、5、3、4
        //尾部插入
        addByIndex(5, 4);
        printNode();   //输出 1、2、3、4、5
    }

    private static void addByIndex(int data, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node node = new Node(data);
        if (index == 0) {
            //插入到头部
            node.setNext(headNode);
            headNode = node;
            if (size == 0) {
                lastNode = node;
            }
        } else if (index == size) {
            //插入到尾部
            lastNode.setNext(node);
            lastNode = node;
        } else {
            //插入到中间
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.getNext();
            prevNode.setNext(node);
            node.setNext(nextNode);
        }
        size++;
    }

    /**
     * 通过位置查找链表节点
     *
     * @param index
     * @return
     */
    private static Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node temp = headNode;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 打印节点
     */
    private static void printNode() {
        while (headNode != null) {
            System.out.println(headNode.getDate());
            headNode = headNode.getNext();
        }
    }

}

/**
 * 定义一个节点
 *
 * @param <T>
 */
class Node<T> {
    /**
     * 节点中的数据
     */
    private T date;
    /**
     * 下一个节点的指针
     */
    private Node next;

    public Node(T date) {
        this.date = date;
    }

    public Node getNext() {
        return next;
    }

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

    public T getDate() {
        return date;
    }

    public void setDate(T date) {
        this.date = date;
    }
}

3.2 链表的删除

链表删除和增加一样，也有三种情况：

• 删除头部

  

  删除头部操作只需要将头部节点设置为当前头部节点的下一个节点就可以了。

• 删除中间

  

  删除中间操作只需要将被删除节点的前一个节点的后继指针指向被删除节点的下一个节点就可以了。

• 删除尾部

  

  尾部删除只需要将倒数第二个节点的后继指针指向null就可以。

/**
 * @author: lixiaoshuang
 * @create: 2019-12-08 23:11
 **/
public class LinkedListAddDemo {

    //头节点
    private static Node headNode = null;
    //尾节点
    private static Node lastNode = null;
    //链表的长度
    private static int size;

    public static void main(String[] args) {
        //初始化一个链表
        addByIndex(1, 0);
        addByIndex(2, 1);
        addByIndex(3, 2);
        addByIndex(4, 3);

        //头部删除
        delete(0);
        printNode();   //输出 2、3、4
        //尾部删除
        delete(3);
        printNode();   //输出 1、2、3
        //中间删除
        delete(2);
        printNode();   //输出 1、2、4
    }

    /**
     * 链表删除操作
     *
     * @param index
     */
    private static void delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        if (index == 0) {
            //删除头部
            headNode = headNode.getNext();
        } else if (index == size - 1) {
            //删除尾部
            Node prevNode = get(index - 1);
            prevNode.setNext(null);
            lastNode = prevNode;
        } else {
            //删除中间
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.getNext().getNext();
            prevNode.setNext(nextNode);
        }
        size--;
    }

    /**
     * 通过位置查找链表节点
     *
     * @param index
     * @return
     */
    private static Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node temp = headNode;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 打印节点
     */
    private static void printNode() {
        while (headNode != null) {
            System.out.println(headNode.getDate());
            headNode = headNode.getNext();
        }
    }

}

3.3 链表的修改

修改链表节点就直接将要修改的节点替换为新节点，第一步先将被修改的节点的前一个节点的后继指针指向新节点，然后将新节点的后继指针指向被修改节点的下一个节点，这里讲的是如何修改一个节点，逻辑和上边的增加删除差不多，这里就举一个中间修改的图例吧。如果想不替换节点修改节点中的数据，这个比较简单，大家可以自己实现下。

/**
 * @author: lixiaoshuang
 * @create: 2019-12-08 23:11
 **/
public class LinkedListOperationDemo {

    //头节点
    private static Node headNode = null;
    //尾节点
    private static Node lastNode = null;
    //链表的长度
    private static int size;

    public static void main(String[] args) {
        //初始化一个链表
        addByIndex(1, 0);
        addByIndex(2, 1);
        addByIndex(3, 2);
        addByIndex(4, 3);

        //修改头部
        update(5, 0);
        printNode();   //输出 5、2、3、4
        //修改尾部
        update(5, 3);
        printNode();   //输出 1、2、3、5
        //修改中间
        update(5, 1);
        printNode();   //输出 1、5、3、4
    }

    /**
     * 链表的修改
     *
     * @param data
     * @param index
     */
    private static void update(int data, int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node newNode = new Node(data);
        if (index == 0) {
            //修改头部
            Node next = headNode.getNext();
            newNode.setNext(next);
            headNode = newNode;
        } else if (index == size) {
            //修改尾部
            Node prevNode = get(index - 1);
            prevNode.setNext(newNode);
            lastNode = newNode;
        } else {
            //修改中间
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.getNext().getNext();
            prevNode.setNext(newNode);
            newNode.setNext(nextNode);
        }
    }

    /**
     * 通过位置查找链表节点
     *
     * @param index
     * @return
     */
    private static Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node temp = headNode;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 打印节点
     */
    private static void printNode() {
        while (headNode != null) {
            System.out.println(headNode.getDate());
            headNode = headNode.getNext();
        }
    }

}

3.4 链表的查询

说道查询，不知道大家发现没有，上边的代码中已经有过实现了