一维数据结构

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

数组

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

因为有了这些限定条件,就可以推导出数组的内存地址公式 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) 的访问时间复杂度。

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

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

坚持原创技术分享,您的支持将鼓励我继续创作!