大纲图

链表的经典面试题目

如何设计一个LRU缓存淘汰算法

tip:单向链表

约瑟夫问题

N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

举个例子： 假设N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。
现在问你最后留下的人是谁？
比如N=6，M=5 ，留下的就是1

1 2 3 4 5 6 => 6 1 2 3 4 => 6 1 2 3 =>1 2 3 => 1 3 => 1

tips: 单向循环链表

顺序表VS 链表

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 比如下面这种

相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表的特点

• 不需要连续的内存空间
• 有指针引用

常见的链表结

三种最常见的链表结构：单向链表、双向链表 和循环链表 （单向循环链表、双向循环链表）

单向链表

单向链表是由一个个节点组成的，每个节点是一种信息集合，包含元素本身以及下一个节点的地址。

从单链表图中，可以发现，有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。

我们一般把第一个结点叫作头结点，把最后一个结点叫作尾结点。

其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。

而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。

单向链表的查找

没啥好说的，从头结点开始遍历，直到找到停止，不存在的话，就是全部遍历了，查找的时间复杂度为O(n)

code如下

 /**
     * 根据值，找到对应的节点
     * 从头节点 开始遍历
     *
     * @param data
     * @return
     *
    public ArtisanNode find(Object data) {
        // 头节点的临时变量，直接用head就把head给改变了，不可取。
        ArtisanNode currentNode = head;
        // 遍历
        while (currentNode != null) {
            if (currentNode.data == data) { // 如果匹配，终止循环
                break;
            } else {
                currentNode = currentNode.next; // 不匹配则将下个节点赋值给当前节点，继续循环
            }
        }
        System.out.println("当前节点:" + currentNode.toString());
        return currentNode;
    }

单向链表的插入

插入的话 分为三种场景，头插、尾插、中间插入

头插

头插就是插入头部节点。 流程如下

尾部插入

尾插就是插入尾部节点。 流程如下

中间插入

单向链表的删除

删除头节点

删除中间的节点

删除尾部节点

Code

/**
 * @author 小工匠
 * @version v1.0
 * @create 2020-01-01 07:36
 * @motto show me the code ,change the word
 * @blog https://artisan.blog.csdn.net/
 * @description
 **/

public class ArtisanSingleLinkedList {

    // 头节点
    private ArtisanNode head;
    // 单向链表的长度
    private int size;

    /**
     * 构造函数
     */
    public ArtisanSingleLinkedList() {
        this.size = 0; // 初始化长度为0
        this.head = null;// 初始化head为null
    }

    /**
     * 头插
     *
     * @param data
     */
    public void add2Head(Object data) {
        ArtisanNode node = new ArtisanNode(data); // 初始化一个Node
        node.next = head;// 将这个新Node的next指向head
        this.head = node;// 把这个新的node置为head
        size++;  // 更新链表容量
    }

    /**
     * 尾插
     *
     * @param data
     */
    public void add2Tail(Object data) {
        ArtisanNode node = new ArtisanNode(data);

        ArtisanNode currentNode = head;
        while (currentNode != null){ // 遍历
            if (currentNode.next == null){ // next为null，说明到了tail
                currentNode.next = node; // 将next节点指向新增节点
                break; // 跳出循环
            }else {
                currentNode = currentNode.next; // 不匹配则将下个节点赋值给当前节点，继续循环
            }
        }
        size++;
    }

    /**
     * 插入链表的中间 假设在第N个位置插入
     *
     * @param data
     */
    public ArtisanNode add2Nth(Object data, int position) {
        ArtisanNode node = new ArtisanNode(data);

        if (position == 0) { // 如果position = 0 ,头插
            add2Head(data);
        } else { // 找到对应的位置
            // 头节点的临时变量，直接用head就把head给改变了，不可取。
            ArtisanNode currentNode = head;
            for (int i = 1; i < position; i++) {
                currentNode = currentNode.next; // 一直往后遍历
            }
            node.next = currentNode.next; // 当前节点的next节点 赋值给 新节点的next
            currentNode.next = node; // 当前节点的next节点指向新节点
        }
        size++; // 更新链表容量
        return node;
    }

    /**
     * 根据值，找到对应的节点
     * 从头节点 开始遍历
     *
     * @param data
     * @return
     */
    public ArtisanNode find(Object data) {
        // 头节点的临时变量，直接用head就把head给改变了，不可取。
        ArtisanNode currentNode = head;
        // 遍历
        while (currentNode != null) {
            if (currentNode.data == data) { // 如果匹配，终止循环
                break;
            } else {
                currentNode = currentNode.next; // 不匹配则将下个节点赋值给当前节点，继续循环
            }
        }
        System.out.println("当前节点:" + currentNode.toString());
        return currentNode;
    }



    /**
     * @return 单向链表当前的容量
     */
    public int getSize() {
        System.out.println("ArtisanSingleLinkedList 当前的容量为:" + size);
        return size;
    }


    /**
     * 删除头节点
     * 时间复杂度 O(1)
     */
    public ArtisanNode deleteHead(){
        this.head = head.next ; // 将头节点的next
        size--;
        return head;// 返回头节点
    }


    /**
     * 删除指定位置的节点
     *
     * 时间复杂度 O(n)
     */
    public ArtisanNode deleteNth(int position){
        ArtisanNode currentNode = head;
        if (position == 0 ){
            deleteHead();
        }else{
            for (int i = 1; i < position; i++) {
                currentNode = currentNode.next;
            }
            currentNode.next = currentNode.next.next; //cur.next 表示的是删除的点，后一个next就是我们要指向的
        }
        size--;
        return currentNode.next; // 返回被移除的节点
    }

    /**
     * 删除尾部节点
     */
    public ArtisanNode deleteTail(){
        ArtisanNode currentNode = head;
        ArtisanNode previosNode = head;
        while (currentNode != null){
            if (currentNode.next == null){
                    previosNode.next = null;
                    break;
            }else {
                previosNode = currentNode;
                currentNode = currentNode.next;
            }
        }
        size--;
        return previosNode; // 返回尾结点
    }

    public void print(){
        ArtisanNode currentNode = head;
        while(currentNode != null){
                System.out.print(currentNode.data+" -> ");// 从头节点开始输出
                currentNode = currentNode.next;

        }
        System.out.println();
    }

    public static void main(String[] args) {

        ArtisanSingleLinkedList single = new ArtisanSingleLinkedList();
        // 头插
        single.add2Head(5);
        single.add2Head(4);
        single.add2Head(3);
        single.add2Head(2);
        single.add2Head(1);
        single.getSize();
        single.print();


        // 查找数据
        single.find(4);

        // 指定位置插入
        single.add2Nth("InsertedData", 2);
        single.getSize();
        single.print();

        // 尾插
        single.add2Tail("小工匠");
        single.print();

        single.getSize();

        // 删除中间节点
        single.deleteNth(2);
        single.print();

        // 删除尾部节点
        single.deleteTail();
        single.getSize();
        single.print();
    }
}


/**
 * Node节点
 */
class ArtisanNode {
    Object data; // 数据域
    ArtisanNode next; // 指针域，指向下一个节点

    /**
     * 构造函数
     *
     * @param data
     */
    public ArtisanNode(Object data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "ArtisanNode{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}

总结

• 1. 说到数组就要想到下标，查找使用下标去查找，因为根据下标查找的时间复杂度为O(1).
  不要试图使用根据元素的值去查找，因为这样的话，根据值去查找，时间复杂度为O(n)

• 2. 数组的话，需要考虑数组越界的问题， 合理的动态扩容/缩容 ， 减少不必要的内存浪费

• 3. CPU可以把数组缓存到CPU内部，执行效率比链表更高。 为啥可以缓存数组呢？ ---->
  数组是在内存里连续的， 索引找到了首地址，其他元素也就都找到了。 链表在内存中 是没有规律的，通过指针项链，没发被CPU缓存。

• 4. 说到链表，不需要考虑下标的问题，所以不能根据下边来查找，肯定是需要根据数据域存储的数据来查找，从头遍历，通过next执行，一直遍历下去，直到找到数据位置。所以时间复杂度为O(n)

• 5. 链表 虽然查找慢，但是插入和删除快啊，动动指针即可，不用挪元素。时间复杂度O(1)

• 6. 链表 因为本身支持动态扩容，所以一定要考虑 链表占用的内存大小。。。切记。