关于小密圈，有很多朋友在知乎上给我发私信，问相关的情况。是这样，小密圈只是象征性的收取一点费用。孔子也说：“自行束修以上，吾未尝无诲焉”，再加上我确实也没那么多精力，所以就没有免费，以达到控制人数的目的。

还有朋友问，有没有QQ群，以前尝试过组建了一个C++学习的群，但是后来群里一开始都乱发各种通过搜索就能解决的简单题，后来慢慢地就没人发言，成了死群了，所以我也不想再建一个这样的群了。收取一点费用，也是为了激励大家好好学习，认真地做一下课后习题。所以，那些问我有没有免费的群的，我集中回答一下，现在还没有，临时也没有计划创建。

还有知乎私信问我怎么学习的，真的很不好意思，这个问题比较大，也比较难回答，各人情况也不一样，而且我的精力也有限。所以很多私信我没办法一一回复，还希望大家多包涵。

还有小密圈的人数上限的问题。这个圈友不用担心，我已经请好了嘉宾，其中有前阿里巴巴的数据工程师，前腾讯前端工程师，以及一个清华博士，这些人都是我的朋友，会帮我一起review作业，所以review的质量还是可以保证的。只是这里要提醒一下已经加圈的朋友，作业你们得做啊。我收到的作业目前只有五份。

好了，下面正式开始今天的内容。

数组

我们从数组开始讲起，创建一个数组，在第 n 位存数据，取数据，这些基本的操作我就不再赘述了。这些都是比较简单的操作。我们再想一种情况，假如，我要在第3个位置上插入一个数据，例如，现在的数组是这样定义的：

        int[] array = new int[10];
        for (int i = ; i < array.length - 1; i++)
            array[i] = i + 1;

然后我希望在第3位插入10，这样遍历这个数组的时候，得到的是1, 2, 3, 10, 4, 5, 6, 7, 8。那么我就得这么做：

        for (int i = array.length - 1; i >= 3; i--) {
            array[i] = array[i - 1];
        }
        array[3] = 10;

        for (int i : array) {
            System.out.println(i);
        }

通过这个例子，我们看到了数组的特点：随机存取都很快，但顺序存储会比较慢。

大O记号

上一节，我用快慢来描述存取算法，这种感性的描述是不好的。我们希望有一种方法可以量化一种操作的耗时情况。注意到，解决问题的时间往往和问题的规模有关系，我们借用了数学分析中的大O记号来描述这种关系。

解决一个规模为 n 的问题所花费的步骤如果是 n 的常数倍，我们就记这个方法的复杂度为O(n)。例如，给一个数组，求这个数组中的最大值，需要遍历这个数组，如果数组长度为n，那么遍历数组的步骤就是 n。所以，这是一种O(n)的操作。

同样，解决一个规模为 n 的问题所花费的步骤如果是 n^2 的常数倍，我们就记这个方法的复杂度为O(n^2)。比如冒泡排序。

而解决问题的步骤如果与问题规模无关，这个时间复杂度就是O(1)的。比如，数组的随机存取。

上一节里说讲的数组的顺序存储就是O(n)的。

链表

我们接下来看链表，先看一个类的定义：

class LinkNode {
    public int data;
    public LinkNode next;

    public LinkNode(int data) {
        this.data = data;
        this.next = null;
    }
}

我们定义了一个LinkNode类，这个类里有两个成员变量，一个是整型data，还有一个是指向LinkNode 类型的引用。

通过这个引用，我就可以把多个LinkNode串起来，比如，这样的代码：

        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);

我就在内存里创建了两个LinkNode对象，它们之间的关系就像这样：

链表增加一项

如果我想在head之后，增加一个链表项，让这个链表变成下图中的样子，该怎么做呢？

大家可以先想一下，看看能不能写出来。

        LinkNode newNode = new LinkNode(3);
        newNode.next = head.next;
        head.next = newNode;

思路就是先把新的结点的next设为head的next，然后再使得head.next指向新的结点即可。

反过来，想要把head后面的那个结点删掉，也很简单，只需要让head的next再往后指一项，把原来head后面的那一项跳过去就可以了：

        head.next = head.next.next;

可以看到，在链表中，指定的结点后面添加一个项是常数时间的，也就是O(1)，删除一个项也是一样的。但与数组不同的，如果我要完成“查询链表中的第n项是什么”这个操作，就会变成O(n)的，因为我们每次查找都必须从头开始，依次向后查找。

    public static int queryData(LinkNode head, int index) {
        LinkNode cur = head;
        for (int i = ; i < index; i++) {
            cur = cur.next;
        }

        return cur.data;
    }

再看一个问题，假如我知道了一个LinkNode，不妨记为temp, 位于一个链表中，如果想知道这个结点的上一个结点是什么，应该怎么办？对于我们前边定义的链表结构，只能从头开始找，去判断是否有某个结点，它的 next 与 temp 相等。如果相等就说明，这个结点就是 temp 的前序结点。代码如下：

    public static LinkNode findPrevious(LinkNode head, LinkNode temp) {
        LinkNode cur = head;
        while (cur != null) {
            if (cur.next == temp)
                return cur;

            cur = cur.next;
        }

        return null;
    }

双向链表

实际上，在工程实践中，使用链表的时候，经常会有“查询某个结点的前一结点”这样的需求，为了加速这一过程，我们其实可以修改一下LinkNode的定义，结它加上一个指向前序结点的成员变量：

class DoubleLinkNode {
    public int data;
    public LinkNode next;
    public LinkNode prev;

    public LinkNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

这样的话，链表就成了这个样子了：

好了。今天的课程就到这里了。

作业：

1. 实现一个完整的双向链表类：

class DoubleLinkList {
  public DoubleLinkNode head;
  public DoubleLinkNode tail;
  public DoubleLinkNode queryNode(int index); // 查询第 index 项的内容
  public void deleteNode(DoubleLinkNode toBeDelete); // 将 toBeDelete 从链表中删除
  public void insertNode(DoubleLinkNode pos, DoubleLinkNode toBeInsert); // 将toBeInsert插入到pos结点后面
}

2. 一个单向链表，删除指定的结点。注意，我们使用单向链表的时候，如果指定一个结点，删除它的后序结点是比较容易的，文章里的例子也是这样的。题目的要求是删除指定结点。

3. 有一个复杂链表，结点包含next指针和sibling指针，其中next指针指向下一个结点，而sibling指针指向链内的某一个不确定位置的结点。复制这个链表。图2.1中实线箭头代 表next指针，虚线箭头代表sibling指针。

上一节课：位操作

下一节课：队列

目录：课程目录

=========== 广告时间 ====================

课程内容都会发在知乎专栏里，不加小密圈也可以看。而且我再次保证，理论的讲解绝不会藏私，一定是公共地发出来。小密圈的作用，除了发布作业的答案，还有作业的讲解。我会为圈子里的朋友们，针对这些习题，专门进行review。

小密圈是付费的，但是收费刚好是一顿必胜客套餐。持继一年的课程，只需要请我吃一顿饭，怎么看也是划算的:)

https://wx.xiaomiquan.com/mweb/views/joingroup/join_group.html?group_id=2214254521&secret=3v8pextw4kz53tpbns53ewxg1846d6hf&extra=222990c1366583bf0f1db69e06ad15575f6e6010196e1abb057aec1164fe7d49 (二维码自动识别)