数据结构算法 - 数组与链表

是时候来撸一波数据结构和算法了，学完 NDK 自己打算又重新回到 Android 和 Java ， 再去抓一些有细节和深度的东西。大学选的是教育专业后来自学的编程，学编程的第一感觉就是可以找一份工作，薪资方面什么的都还好，因为农村孩子家里穷所以就学了。刚开始学习不像现在，谈不上有多喜欢，也没学过什么数据结构和算法，感觉开发中能用到的地方也不多，面试基本也不问（长沙）。前几天在微信公众号看到一篇文章 《 P2P被套了，失业了，魔都我又开始面试了，说好的不跳的》 现在企业的用人标准，似乎都比以前高了很多。来深圳面试上了 500 人以上的企业，基本都会问一些数据结构和算法的知识，好在自己在还没来深圳之前，就做了一些准备。

学了数据结构和算法后，自己的第一感觉就是思维更加敏捷和开阔了，写代码的时候严谨了很多，线上崩溃 Bug 也少了许多。如果说语言的基础语法和业务逻辑是术，那 数据结构与算法思想和设计模式就是道。后期如果想要有一个飞跃式的提高，数据结构与算法、设计模式这个时候就很重要，是一门内功心法。

首先我们需要了解几个概念，什么是数据结构？什么是算法？算法的优劣怎样来衡量？

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系，简单的理解就是元素之间的相互关系。其中逻辑结构分为四类：集合结构，线性结构，树形结构，图形结构。存储结构一般分为顺序存储和连式存储。

算法是指特定问题求解步骤的描述。算法的特性有：输入，输出，有穷性，确定性和可行性。算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，也称之为时间复杂度和空间复杂度。

时间复杂度是一个函数，它定性描述了该算法的运行时间，时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。

概念性的东西理解起来比较困难，我们来看一个简单的实例，相信就能理解什么是时间复杂度和空间复杂度了。假如我们现在需要求 1+2+3+4+5+ **** + n ，我们可能会有如下写法：

// 通过具体的 n 的步骤就可以推演出算法的复杂度
int sum1(int n){ // 时间复杂度 O(n)
    int sum = 0; // 执行 1 步
    for (int i = 1; i <= n; i++) // 执行 n 步
    {
        sum += i;
    }
    return sum;
}

int sum2(int n){// 时间复杂度 O(1)
    return (1 + n) * n / 2;// 1步
}

上面的实例，通过具体的 n 的步骤就可以推演出算法的复杂度，因此 sum1 的时间复杂度我们可以表示为 O(n) , sum2 的时间复杂度为 O(1) 。

常见的时间复杂度有： 常数阶O(1)，对数阶O(log2 n)，线性阶O(n)，线性对数阶O(n log2 n)，平方阶O(n^2)， 立方阶O(n^3)， k次方阶O(n^K)，指数阶O (2^n)。 随着n的不断增大，时间复杂度不断增大，算法花费时间越多。

理论过后就是去实践了，为了方便巩固我们 NDK 所学的内容，后面的文章分析源码主要以 Java 为主，语法主要以 c/c++ 为主。至于数组之前的文章 《C++基础 - 实现 Native 层的 ArrayList》 有讲过，这里就不再过多的啰嗦。那么本文就主要来分析链表，以 Java 的 LinkedList 源码为例。

template<typename E>
typedef
struct Node {
    E value;
    Node *next;
public:
    Node(E value, Node *next) {
        this->value = value;
        this->next = next;
    }
};

template<typename E>
E LinkedList<E>::get(int index) {
    assert(index >= 0 && index < len);
    return node(index)->value;
}

template<typename E>
int LinkedList<E>::size() {
    return len;
}

template<typename E>
void LinkedList<E>::push(E e) {
    // 创建新的节点
    Node<E> *newNode = new Node<E>(e, NULL);
    if (head) {
        // 获取最后一个节点
        Node<E> *last = node(len - 1);
        last->next = newNode;
    } else {
        head = newNode;
    }
    len++;
}

template<typename E>
Node<E> *LinkedList<E>::node(int index) {
    Node<E> *cur = head;

    for (int i = 0; i < index; ++i) {
        cur = cur->next;
    }

    return cur;
}

template<typename E>
void LinkedList<E>::insert(int index, E e) {
    assert(index >= 0 && index <= len);

    Node<E> *newNode = new Node<E>(e, NULL);

    if (index == 0) {
        newNode ->next = head;
        head = newNode;
    } else {
        // 获取当前位置的前一个节点
        Node<E> *pre = node(index - 1);
        // 保存当前位置
        Node<E> *next = pre->next;
        pre->next = newNode;
        newNode->next = next;
    }
    len++;
}

template<typename E>
E LinkedList<E>::remove(int index) {
    assert(index >= 0 && index < len);
    len--;
    if(index == 0){
        Node<E> *h = head;
        head = head->next;

        E value = h->value;
        delete h;
        return value;
    } else {
        Node<E> *pre = node(index - 1);
        Node<E> *next = pre->next;
        pre->next = pre->next->next;

        E value = next->value;
        // new 的对象，需要删除当前节点
        delete next;
        return value;
    }
}

上面的代码比较简单，主要采用单链表来实现一个集合。一个算法我们可以优先考虑时间复杂度，所以在大多数场景下，可以考虑用空间复杂度来换时间复杂度，比如我们现在插入一条数据的时间复杂度是 O(n) 级别，那么我们就需要想办法去优化。比如我们加一个 last 节点，就可以把插入数据的复杂度降为 O(1) 级别。不要小看了这些优化，当数据量大的时候就会非常有用。

对插入 50000 条数据进行测试，耗时是 8000ms ，上面插入算法时间复杂度是 O(n) 级别的，关键就在于每次插入数据的时候，都需要遍历整个链表找到最后一个节点才能插入。因此我们可以针对性的做一些优化，我们再定义一个节点用来记录链表的最后一个位置，将时间复杂度优化为 O(1) 级别。

template<typename E>
void LinkedList<E>::linkLast(E e) {
    Node<E> *l = last;
    Node<E> *new_node = new Node<E>(e, NULL);
    last = new_node;

    if (l == NULL) {
        head = new_node;
    } else {
        l->next = new_node;
    }
}

对插入 50000 条数据进行测试，耗时是 0ms 。链表和数组相比劣势就在于查找，因为数组可以根据索引查找，因此时间复杂度是 O(1) 级别，而链表的时间复杂度是 O(n)，当然我们也可以对其进行优化，比如采用双向链表或是单链表位运算等等。

template<typename E>
void LinkedList<E>::linkBefore(E e, Node<E> *cur) {
    Node<E> *prev = cur->prev;
    Node<E> *new_node = new Node<E>(e, prev, cur);
    cur->prev = new_node;

    if(prev){
        prev->next = new_node;
    } else{
        head = new_node;
    }
}

视频地址：https://pan.baidu.com/s/1s0Xb_PM3Ehp81slUY7qnGg
视频密码：kcek