Contents
  1. 1. 基本数据结构
    1. 1.1. List
      1. 1.1.1. List 的抽象数据类型
      2. 1.1.2. List 的实现
    2. 1.2. Stack
      1. 1.2.1. Stack 的抽象数据类型
      2. 1.2.2. Stack 的实现
    3. 1.3. Queue
      1. 1.3.1. Queue 的抽象数据类型
      2. 1.3.2. Queue 的实现
    4. 1.4. Binary Tree
      1. 1.4.1. Binary Tree 的抽象数据类型
      2. 1.4.2. Binary Tree 的实现
    5. 1.5. Graph
      1. 1.5.1. Graph 的抽象数据类型
      2. 1.5.2. Graph 的实现
  2. 2. 其它数据结构
    1. 2.1. Dictionary
      1. 2.1.1. Dictionary 的抽象数据类型
    2. 2.2. Hash Table
      1. 2.2.1. Hash Table 的抽象数据类型
      2. 2.2.2. Hash Table 的实现
  3. 3. 数据结构的选择
    1. 3.1. 插入删除/扩展性
    2. 3.2. 搜索
    3. 3.3. 综合考虑
  4. 4. 数据结构的总结
  5. 5. References

基本数据结构

List


List 的抽象数据类型

列表(List)包含一组按顺序排列的相同类型的元素,它的操作如下:

  • get() - 返回给定位置的一个元素。
  • insert() - 插入一个元素在指定位置。
  • remove() - 删除第一个元素。
  • removeAt() - 删除一个特定位置的元素。
  • size() - 返回列表元素的数量。
  • isEmpty() - 返回列表是否为空。
  • isFull() - 返回列表是否已满。
  • clear() - 清空列表的内容。

List 的实现

Array List

数组是列表的一种实现,它在内存中是连续的空间。

优点

  • 它可以快速的随机访问。

缺点

  • 插入和删除性能不太好,需要大量的元素位置移动。

应用场景

  • 简单的存储一组数据。

Linked List

链表是一个线性结构,它是列表的另一种实现,它在内存中是非连续的空间。每个元素称为节点,相邻的两个节点由指针进行连接。

优点

  • 它具有很好的扩展性,快速的插入和删除。

缺点

  • 随机访问(按位置访问)性能不好。节点的访问必须从前往后依次遍历。
  • 比数组消耗更多的内存。在使用的指针上。
  • 需要更多的读取时间。在内存中是不连续的,CPU 一次只能获取一个元素,

应用场景

  • 迭代器。

Array List vs Linked List

数组 链表
随机存取 T(n) = O(1) T(n) = O(n)
插入和删除 T(n) = O(n) T(n) = O(1)

Stack


Stack 的抽象数据类型

栈(Stack)是一个线性的数据结构。它遵循一个特殊的操作顺序。后进先出(Last In First Out, LIFO),它的操作如下:

  • push()
  • pop()
  • peek()
  • size()
  • claer()

Stack 的实现

可以基于数据实现,也可以基于链表实现。

优点

  • 方便的按照某种循序访问数据。

缺点

  • 只用于特定场合。

应用场景

  • 逆序输出。
    • 进制转换。
  • 递归嵌套。
    • 括号匹配
    • 栈混洗(Stack Permutation)。通过一个中间栈,重新排序原始栈的数据顺序。。
  • 延迟缓冲。
    • 中缀表达式。操作符以中缀形式处于操作数中间的算术表达式。
    • 逆波兰表达式。不需要括号的后缀表达式。
  • 栈式计算。

Queue


Queue 的抽象数据类型

队列(Queue)是一个线性结构。它和栈类似有特殊的操作顺序。先进先出(First In First Out, FIFO)。它的操作如下:

  • enquque()
  • dequeue()
  • peek()
  • size()
  • claer()

Queue 的实现

队列可以基于数组实现,也可以基于链表实现。

优点

  • 方便的按照某种循序访问数据。

缺点

  • 只使用在特定的场合。

应用场景

  • 系统任务调度。

Binary Tree


Binary Tree 的抽象数据类型

二叉树(Binary Tree)是一个树结构,每个节点最多有两个子节点,分别表示为左子树和右子树。它的操作:

  • getRoot()
  • isEmpty()
  • size()
  • contains()
  • find()
  • toString()
  • iteratorInOrder()
  • iteratorPreOrder()
  • iteratorPostOrder()
  • iteratorLevelOrder()

Binary Tree 的实现

二叉树通过指针关联节点实现。

优点

  • 可以表示树结构的数据关系。

缺点

  • 大量的指针消耗。

应用场景

  • 用于搜索。通过 binary search tree 可以支持快速的搜索、插入和删除,复杂度都是 O(log n)。
  • 用于压缩。使用在 Huffman Coding。
  • 用于数据库的索引的实现。

Graph


Graph 的抽象数据类型

图(Graph)由一组有限个顶点(Vertex)和有限的边(Edge)组成。它的操作如下:

  • addVertex(vert)
  • addEdge(fromVert, toVert)
  • addEdge(fromVert, toVert, weight)
  • getVertex(vertKey)

Graph 的实现

可以通过邻接表(adjacency List),也可以邻接矩阵(adjacency Matrix)实现。

邻接矩阵 邻接表
内存 O(n^2) less than adjacency Matrix
查询一条边 O(1) O(k)
遍历所有边 slow fast
添加/删除一个节点 O(n^2) O(n)
添加一条边 O(1) O(1)

应用场景:

  • 用于计算机网络的路由,找到最小花费路径。

  • 社交媒体应用,用户之间的关联。

  • 地图应用。如,找到最优的行驶路线。

  • 电商网站。推荐商品。

其它数据结构

Dictionary


Dictionary 的抽象数据类型

字典(Dictionary)高效地组织数据,支持快速地存储和查找。每个元素由一个 key 和一个复合类型(对象)组成<key, E>。通过 key 来唯一标识一个对象,可以通过 key 来查找对象。它的操作如下:

  • insert(key, object)
  • remove(key)
  • find(key)
  • size()
  • clear()

Hash Table


Hash Table 的抽象数据类型

哈希表(Hash Table)是一个由链表组成的数组结构。它使用哈希函数计算一个元素值在数组中的索引。它的操作:

  • put(key, value)
  • get(key)
  • containsKey(key)
  • contains(value)
  • remove(key)

Hash Table 的实现

哈希表由链表数组实现。

优点

  • 快速的查找。
  • 快速的插入和删除。

缺点

  • 不保证元素的顺序。不能随机访问。

数据结构的选择

插入删除/扩展性

数据的容量需要很好的扩展性,或者频繁的插入和删除,选择动态的数据结构(指针关联)比较合适。如链表,二叉树等等。不足之处是指针结构对随机存取效率没有静态结构(连续空间)好。

搜索

简单的搜索即从第一个元素一直比较直到最后一个元素。如数组,它的复杂度是 O(n)。

更高效率搜索的数据结构,哈希表的复杂度为 O(1),有序数组复杂度为 O(log n),搜索二叉树的复杂度为 O(log n)

综合考虑

兼顾搜索和插入:可以考虑哈希表和搜索二叉树。有序数组虽然搜索复杂度和搜索二叉树一样,但是有序数组的插入性能不好。

兼顾搜索和随机存取:可以考虑有序数组。

数据结构的总结

组成形式:连续空间,不连续(指针)空间。

结构关系类型:线性,树状,图

本质:存储一组元素,表示元素之间的关系,提供操作元素的方法。

数据结构的总结:

  • 数据结构是用来表示数据和操作数据的。

  • 有些数据结构只适用于特殊的场景。

  • 一个好的数据结构可以大幅度提高算法的效率。

  • 不存在一种数据结构在所有方面都优于另一个数据结构,每个数据结构都有自己的优缺点。数据结构的选择是一个权衡利弊和妥协的过程。

References

[1] Data Structures and Algorithm Analysis in C++ (3rd) by Clifford A. Shaffer

[2] Abstract Data Types - GeeksforGeeks

[3] The BinaryTree ADT

[4] The Graph Abstract Data Type

[5] Linked List - Wikipedia

[6] What are the applications of binary trees? - Stack Overflow

[7] What are real life applications of graphs? - Quora

Contents
  1. 1. 基本数据结构
    1. 1.1. List
      1. 1.1.1. List 的抽象数据类型
      2. 1.1.2. List 的实现
    2. 1.2. Stack
      1. 1.2.1. Stack 的抽象数据类型
      2. 1.2.2. Stack 的实现
    3. 1.3. Queue
      1. 1.3.1. Queue 的抽象数据类型
      2. 1.3.2. Queue 的实现
    4. 1.4. Binary Tree
      1. 1.4.1. Binary Tree 的抽象数据类型
      2. 1.4.2. Binary Tree 的实现
    5. 1.5. Graph
      1. 1.5.1. Graph 的抽象数据类型
      2. 1.5.2. Graph 的实现
  2. 2. 其它数据结构
    1. 2.1. Dictionary
      1. 2.1.1. Dictionary 的抽象数据类型
    2. 2.2. Hash Table
      1. 2.2.1. Hash Table 的抽象数据类型
      2. 2.2.2. Hash Table 的实现
  3. 3. 数据结构的选择
    1. 3.1. 插入删除/扩展性
    2. 3.2. 搜索
    3. 3.3. 综合考虑
  4. 4. 数据结构的总结
  5. 5. References