数据结构笔记
这学期感觉 Terry 的 Data Structures for Application Developers 对我帮助巨大。毕竟非科班出身,很多概念都是一知半解。第一天上课的时候,Terry 掏出了一把小锤子,尝试用它干各种事情。大家哈哈大笑的时候,Terry 说,
This is exactly what you are doing. You have lots of tools, but you always use ArrayList.
这门课学下来,Terry 深入浅出地讲解了各种基础算法和数据结构、它们背后的实现、以及如何去选择,上完课的时候真的让我有些醍醐灌顶的感觉。最后一节课下课前,Terry 又说,
Now you know your tools. Use them wisely.
这里就来梳理一下我们手中的 tools。
Array, ArrayList, LinkedList
Array 与 Linear Search
Java 中的数组(没记错的话 C 也是)长度是固定的,即数组一旦创建无法改变大小,所以数组的 length
是 immutable field。如果需要改变,只能创建一个新的更大的数组然后调用 System.arraycopy()
复制。在内存中,假设我们有数组 int array[]
,其中 array[0]
的地址是 0x200,那么 array[2]
的地址就是 0x200 + 2 * 4(Java 中 int 是 4 bytes)= 0x208,因此通过下标获取数组中的某个元素可以在常数时间内完成(直接计算地址)。如果用 C 表示的话,那就是 array[2]
和 *(array + 2)
是完全一样的。
假设我们需要在 Array 中找到一个值并删除,一种简单的思路当然是遍历数组总会找到的,这就是 linear search 或 sequential search,一种最简单的搜索算法。同时,在 worst-case 下,它的运行时间也是 O(n) 的,因为可能需要遍历所有 n 个元素。
ArrayList 与 Binary Search
Java 中的 ArrayList 提供了诸如 add()
,set()
一类的操作,看起来像是能够改变数组的长度。实际上,ArrayList 底层有一个 Array 数据结构,在每次执行 add()
方法前,会先执行 ensureCapacity()
方法去确保当前持有的 Array 能够有足够的空间。 如果没有的话,ArrayList 会创建一个新的更大的数组,然后把旧数组的所有内容复制过来。
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
注意在计算 newCapacity
时的 + 1,这是为了保证在 oldCapacity == 0
的时候也能够按照我们预期的执行。
因此,ArrayList 频繁执行 add()
会造成时间复杂度显著的增加,原因在于一般情况下 add()
可以在常数时间完成,然而一旦触发数组复制,需要消耗和原数组长度线性相关的时间去执行复制。因此,不断调用 ArrayList 的 add()
,消耗的时间曲线类似于这样:
这就是 ArrayList 的 latency issue。还要注意,在调用 remove()
的时候,由于 Array 不允许内部出现空,因此 ArrayList 需要把内部数组里待删除元素之后的元素全部左移,而且不像 add()
仅会在特定次数时触发数组复制,每次 remove()
都会导致元素移动,因此是非常效率低下的。
对于一个排好序的数组,除了 linear search,一个更好的选择是 binary search。它的思路是每次比较数组正中间的值,如果大于中间值,则对右半边数 组继续搜索,否则在左半边搜索。Binary search 大大减少了搜索所需要的时间复杂度,可以达到 O(log n)。
func binarySearch(data: [Int], key: Int) -> Int {
guard !data.isEmpty else {
return NSNotFound
}
var lowerBound = 0
var upperBound = data.count - 1
var mid = 0
while true {
if lowerBound > upperBound {
return NSNotFound
}
// 注意:直接使用 (lowerBound + upperBound) / 2 可能导致超出 Int 范围溢出
mid = lowerBound + (upperBound - lowerBound) / 2
if data[mid] == key {
return mid
} else if data[mid] < key {
lowerBound = mid + 1
} else {
upperBound = mid - 1
}
}
}
LinkedList
为了在常数时间内执行 add()
和 remove()
,我们提出了 LinkedList 的数据结构。LinkedList 的思想是:一条链表由若干节点构成,每个节点的 next
属性指向它的下一个节点,链表的 head
指向第一个节点,这就是 singly linked list。如果节点还具有 prev
属性指向它的上一个节点,链表还具有 tail
属性指向最后一个节点,这就是一个 doubly linked list。
实现 LinkedList 的数据结构。首先我们需要定义节点的类,把它实现为一个 inner class。
class LinkedList<T: Equatable> {
private(set) var head: Node<T>?
init() {
self.head = nil
}
class Node<T> {
var data: T
var next: Node<T>?
init(data: T, next: Node<T>? = nil) {
self.data = data
self.next = next
}
}
}
然后实现 SinglyLinkedList 的各个方法。这里如果我们需要插入一个元素,只要找到上一个元素,然后更改对应的引用就可以了;删除同理。因此,链表的插入和删除可以较快完成。同样的,链表并不是连续的数据结构,一个链表的相邻节点可以在内存中相隔很远。
// 添加到链表开头
func addFirst(_ item: T) {
let newHead = Node(data: item, next: head)
head = newHead
}
// 添加到链表结尾
func addLast(_ item: T) {
guard let head else {
addFirst(item)
return
}
var tmp = head
while let next = tmp.next {
tmp = next
}
tmp.next = Node(data: item)
}
// 在后面插♂入
func insert(after key: T, item: T) {
var tmp = head
while tmp != nil, tmp?.data != key {
tmp = tmp?.next
}
tmp?.next = Node(data: item, next: tmp?.next)
}
// 在前面插入
func insert(before key: T, item: T) {
guard let head else {
return
}
if head.data == key {
addFirst(item)
return
}
var prev: Node<T>?
var curr: Node<T>? = head
while curr != nil, curr?.data != key {
prev = curr
curr = curr?.next
}
if let curr {
prev?.next = Node(data: item, next: curr)
}
}
// 删除
func remove(_ item: T) {
guard let head else {
return
}
if head.data == item {
self.head = head.next
return
}
var prev: Node<T>?
var curr: Node<T>? = head
while curr != nil, curr?.data != item {
prev = curr
curr = curr?.next
}
if let curr {
prev?.next = curr.next
}
}
总结
- Array 或 ArrayList
- 随机访问的数据结构:每一项可以在常数时间内获取
- 插入和删除时需要消耗大量资源(移位,复制),连续的数据结构
- LinkedList
- 顺序访问的数据结构:元素只能按照一定顺序访问(next, prev)
- 链表元素持有数据和对下一个(上一个)元素的引用
- 插入和删除元素时无需移动元素,只需要更改引用,不连续的数据结构
Stack, Queue
Stack
栈是一种按照后入先出(last-in-first-out, aka LIFO)顺序插入/移除元素的数据结构。栈的使用非常普遍,例如浏览器的历史记录,例如 iOS 中 UINavigationController
就是维护了一个栈。栈最关键的是有两种操作(peek 不关键):
- Push:把一个元素压到栈顶
- Pop:把栈顶的元素弹出
- Peek:返回栈顶元素,无需弹出
栈是建立在其它数据结构的基础上的,它的内部可以是数组也可以是链表。比如,我们可以用一个 LinkedList 去实现栈,这样 push 操作可以用 addLast()
,pop 操作可以用 removeLast()
。栈的 push 和 pop 操作都应该在常数时间内完成。
基于 Swift Array,栈可以非常简单地实现。
class Stack<T> {
private var array: [T]
init() {
self.array = []
}
var isEmpty: Bool {
array.isEmpty
}
func push(_ item: T) {
array.append(item)
}
@discardableResult
func pop() -> T? {
return array.popLast()
}
func peek() -> T? {
return array.last
}
}
Queue
队列是一种按照先入先出(first-in-first-out, aka FIFO)顺序插入/移除元素的数据结构。队列也非常常见,比如打印机的队列、在星巴克门店的排队。队列主要也有两种操作:
- Enqueue:把一个元素插入到队列的尾部
- Dequeue:把队首元素移除
队列也可以建立在其他数据结构基础上,最简单的当然还是 LinkedList,入队即是 addLast()
,出队即 removeFirst()
。同样的,入队和出队操作也应该在常数时间内完成。
这里给一个基于 Swift Array 的非常简单的队列实现。
class Queue<T> {
private var array: [T]
init() {
self.array = []
}
var isEmpty: Bool {
array.isEmpty
}
func enqueue(_ item: T) {
array.append(item)
}
@discardableResult
func dequeue() -> T? {
if isEmpty {
return nil
}
let first = array.first
array.remove(at: 0)
return first
}
func peekFront() -> T? {
return array.first
}
}