前端算法系列之数据结构基础

数组

1. 数组底层实现

如下图，数组底层硬件实现有一个叫做内存管理器的东西，每当申请数组的时候，计算机实际上是在内存中开辟了一段连续的地址，每一个地址就可以通过内存管理器进行访问，它可以随机的访问任何一个元素，访问每一个元素的时间复杂度都是一样的，也就是时间常数称为O(1)

Java数组实现源码分析：developer.classpath.org/doc/java/ut…

2. 数组优缺点分析

如下所示，当插入或删除一个元素时，它之后的所有元素都要进行下移操作(删除操作相反)，时间复杂度是O(n)

3. 数组各操作时间复杂度

• prepend O(1)
• append O(1)
• lookup O(1)
• insert O(n)
• delete O(n)

抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是一些操作的集合，抽象数据类型是数学的抽象，在 ADT 的定义中根本没涉及如何实现操作的集合，这可以看作是模块化设计的扩充。
例如表、集合、图和它们的操作。

大致可分为如下三类。

• 栈、队列、链表
• 集合、字典
• 树、堆、图

对表的所有操作都可以通过使用数组来实现。虽然数组是动态指定的，但是还是需要对表的大小的最大值进行估计。通常需要估计得大一些，从而会浪费大量的空间。这是严重的局限，特别是在存在许多未知大小的表的情况下。

数组实现使得 PrintList 和 Find 正如所预期的那样以线性时间执行，而 FindKth 则花费常数时间。然而，插人和删除的花费是昂贵的。例如，在位置 0 的插入（这实际上是做一个新的第一元素）首先需要将整个数组后移一个位置以空出空间来，而删除第一个元索则需要将表中的所有元素前移一个位置，因此这两种操作的最坏情况为 O（N）。平均来看，这两种运算都需要移动表的一半的元素，因此仍然需要线性时间。只通过 N 次相继插人来建立一个表将需要二次时间。

因为插入和删除的运行时间是如此的慢以及表的大小还必须事先已知，所以简单数组一般不用来实现表这种结构。

维度分类

一维

基础：数组array(string)，链表linked list
高级：栈stack，队列queue，双端队列deque，集合set，映射map (hash or map)，etc

二维

基础：树tree，图graph
高级:二叉搜索树binary search tree(red-black tree, AVL)，堆heap，并查集disjoint set，字典树Trie，etc

特殊

位运算Bitwise，布隆过滤器BloomFilter

数据结构脑图：naotu.baidu.com/file/b832f0…