这学期感觉 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 个元素。