一维数据结构

Posted on Edited on In Disqus: Symbols count in article: 3.1k Reading time ≈ 3 mins.

本周主要学习了一维数据结构，这里总结一下每种数据结构它的特性。

数组

数组将固定数量的、数据结构相同的数据存储在一段连续的内存空间上。为什么会有这些限定条件呢？

因为有了这些限定条件，就可以推导出数组的内存地址公式 a[k]_address = base_address + k * type_size ， 这样我们就可以根据数组下标随机访问数组的任意元素了。

那么想想看下面的 Java 代码数组是如何寻址的呢？

1
2
3
4
Object[] items = new Object[10];
items[0] = Arrays.asList("1", "2");
items[1] = "123";
items[2] = 123;

另外数组的随机访问和数据查找是两回事。数组随机访问的时间复杂度 O(1)，但查找并不是 ，比如遍历数组查找时间复杂度就是 O(n)，对排列好的数组用二分查找就是 O(logn) 。数组这个随机访问的特性非常重要，比如后面我们要学习的 Hash 表，就充分利用了这种特性。

链表

链表在数组的基础上解放了申请连续的内存空间的限制。单链表定义，数据 + 下个 Node 的地址构成一个 Node 的方式，使得数据逻辑上连续，形成链式结构。

以单链表举例，这样带来的弊端是，我们必须知道上个节点的，才能访问到下个节点，也就是说丧失了随机访问的能力，我们必须从头遍历链表，访问数据的时间复杂度为 O(n) 。好处是添加、删除数据没有数据搬移的操作，时间复杂的都 O(1)。 但是我们一般操作数据都是先查找数据，再进行操作，这个就 O(n) 的时间复杂度了。而且单链表操作根复杂，如果我们已知要删除某个节点，为了保证链表的连续性，必须还要知道链表的前驱节点，所以要遍历一次链表才知道。为了解决这样的问题，我们定义双向链表的节点是， 上个 Node 的地址 + 数据 + 下个 Node 的地址，这样我们的节点天然知道前驱、后继的节点，在已知操作节点的时候，插入新节点、删除该节点时间的复杂度就为 O(1) 了。 JDK 中 LinkedList 就是用双向链表实现的，我想也是利用空间换时间的思想，实现操作的高效吧。

跳表

跳表其实就是在链表的基础上加 N 阶索引，目的是为了降低链表查找数据的时间复杂度，由 O(n) 降级到 O(logn) 。其实跳表就是为了解决链表因为没有数组的随机访问特性，无法支持二分查找，使用空间换时间的思想，为链表添加 N 阶索引，使得链表支持二分查找。

跳表因为它原理简单、实现比红黑树更容易，插入、删除、搜索时间复杂度都是 O(logn) 。所以 Redis、LevelDB 都是用了跳表作为数据结构。

栈

栈是一个操作受限的一维数据结构，可以用数组实现、也可以用链表实现，只要保证只能在数据的一端操作，保证 LIFO 特性就可以了。入栈、出栈时间复杂度都是 O(1)。

这主要说说应用，他们都符合后进先出的场景：

  • 函数调用
  • 括号匹配
  • 浏览器前进后退功能

队列

是一个操作受限的一维数据结构，可以用数组实现、也可以用链表实现，保证只能在数据的一端插入数据，另一段读取并删除数据，保证 FIFO 特性。

用数组实现队列的时候，要维护 head 和 tail 在数据中的索引位置，当多次入队、出队之后，head 和 tail 都会持续往后移动，当 tail 移动到最后，即使数组有空间，也无法添加数据了。为了解决这样的问题，我们在入队的时候要检查队列是否是真的满了，如果未满则要进行数据搬移。

在 JDK 源码中 ArrayDeque 处理队列满的实现，也进行了数据的搬移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

JDK PriorityQueue 源码分析

根据 PriorityQueue 类注释可以发现，优先队列是用堆，也就是完全二叉树（基于数组存储）实现的，在入队和出队（删除）都要维护小顶堆的性质，保证队列是有序的。

其实源码中最难理解的就是如何维护小顶堆的部分。我这里以从出队 poll 数据为例：

1
2
3
4
5
6
7
8
9
10
11
12
public E poll() {
    if (size == 0)
        return null;
    int s = --size; // 占用空间-1
    modCount++; // 修改次数 +1，防止并发操作
    E result = (E) queue[0]; // 取出堆顶数据，这就是 poll 出的数据，因为添加、删除数据时遵守了小顶堆原则
    E x = (E) queue[s]; // 获取堆最后的数据
    queue[s] = null; // 堆底数据置为null, 因为 queue[s] 先要放到堆顶，然后根据比较器自顶向下 siftDown 交换来保证小顶堆原则
    if (s != 0)
        siftDown(0, x);
    return result;
}

siftDown 来维护小顶堆原则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void siftDownUsingComparator(int k, E x) { // k 传的是0, 也就是堆顶
    int half = size >>> 1;
    while (k < half) { // k 就是父节点
        int child = (k << 1) + 1;  // 获取左孩子节点，等价 child = k * 2 + 1
        // 假设左孩子是最小的
        Object c = queue[child];
        int right = child + 1;
        // 比较左右孩子的值，将最小的赋值给 c
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        // c 和交换的数据 x 对比，直到 c >= x 的值
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c; // 原来的父节点作为孩子节点 
        k = child;  //  孩子节点作为父节点（和上面一行一起看，也就是孩子节点和父节点交换）
    }
    queue[k] = x;
}

总结

没有完美的数据结构，每种数据结构优势和缺点并存，就像 CAP 理论不可能三角一样。

数据结构本身也可以通过升维、空间换时间、限制操作的思想进化为另一种数据结构：

  • 通过对数组或链表的限制操作实现栈、队列；
  • 跳表利用空间换时间的思想实现链表的二分查找；
  • 数组通过升维的思想实现完全二叉树；
  • Hash 表通过数组的特性实现 O(1) 的访问时间复杂度。

我们在解决问题的时候要充分利用这些思想、数据结构的特性去解决特定问题。

感觉本周的学习压力还是很大的，基础知识的整理学习，手动实现链表、队列（基于数组、链表）的基本操作，刷题耗费的时间最多，先是自己思考用暴力法解题，又学习不同思路，学习最优解。虽然端午节有不少整块的时间可以学习，但是时间还是不够用的，后面的课程压力很大。