数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。

如下图所示，常见的数据结构可分为「线性数据结构」与「非线性数据结构」，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。数据结构 - 图1

线性结构

链表

ListNode

  1. class ListNode {
  2.     int val;       // 节点值
  3.     ListNode next; // 后继节点引用
  4.     ListNode(int x) { val = x; }
  5. }

栈

栈是一种具有 「先入后出」 特点的抽象数据结构，可使用数组或链表实现。
Stack stack = new Stack<>();
如下图所示，通过常用操作「入栈 push()」,「出栈 pop()」，展示了栈的先入后出特性。

  1. stack.push(1); // 元素 1 入栈
  2. stack.push(2); // 元素 2 入栈
  3. stack.pop();   // 出栈 -> 元素 2
  4. stack.pop();   // 出栈 -> 元素 1

队列

队列是一种具有 「先入先出」 特点的抽象数据结构，可使用链表实现。

  1. queue.offer(1); // 元素 1 入队
  2. queue.offer(2); // 元素 2 入队
  3. queue.poll();   // 出队 -> 元素 1
  4. queue.poll();   // 出队 -> 元素 2

非线性结构：

树

树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」 。

  1. class TreeNode {
  2.     int val;        // 节点值
  3.     TreeNode left;  // 左子节点
  4.     TreeNode right; // 右子节点
  5.     TreeNode(int x) { val = x; }
  6. }

如下图所示，建立此二叉树需要实例化每个节点，并构建各节点的引用指向。

  1. // 初始化节点
  2. TreeNode n1 = new TreeNode(3); // 根节点 root
  3. TreeNode n2 = new TreeNode(4);
  4. TreeNode n3 = new TreeNode(5);
  5. TreeNode n4 = new TreeNode(1);
  6. TreeNode n5 = new TreeNode(2);
  8. // 构建引用指向
  9. n1.left = n2;
  10. n1.right = n3;
  11. n2.left = n4;
  12. n2.right = n5;

散列表：

散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。
则可通过建立姓名为 key ，学号为 value 的散列表实现此需求，代码如下：

  1. // 初始化散列表
  2. Map<String, Integer> dic = new HashMap<>();
  4. // 添加 key -> value 键值对
  5. dic.put("小力", 10001);
  6. dic.put("小特", 10002);
  7. dic.put("小扣", 10003);
  9. // 从姓名查找学号
  10. dic.get("小力"); // -> 10001
  11. dic.get("小特"); // -> 10002
  12. dic.get("小扣"); // -> 10003

数据结构 - 图2

Hash 函数设计 Demo ：

将三人的姓名存储至以下数组中，则各姓名在数组中的索引分别为 0, 1, 2 。

  1. String[] names = { "小力", "小特", "小扣" };

此时，我们构造一个简单的 Hash 函数（ \%% 为取余符号 ），公式和封装函数如下所示：

  1. int hash(int id) {
  2.     int index = (id - 1) % 10000;
  3.     return index;
  4. }

则我们构建了以学号为 key 、姓名对应的数组索引为 value 的散列表。利用此 Hash 函数，则可在 O(1)O(1) 时间复杂度下通过学号查找到对应姓名，即：

  1. names[hash(10001)] // 小力
  2. names[hash(10002)] // 小特
  3. names[hash(10003)] // 小扣

堆：

  • 堆是一种基于「完全二叉树」的数据结构，可使用数组实现。
  • 以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。
  • 堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。
  • 完全二叉树定义： 设二叉树深度为 kk ，若二叉树除第 kk 层外的其它各层（第 11 至 k-1 k−1 层）的节点达到最大个数，且处于第 kk 层的节点都连续集中在最左边，则称此二叉树为完全二叉树。
  • 如下图所示，为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆（完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式。

数据结构 - 图3
通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作，即可完成堆排序，实现代码如下：

  1. // 初始化小顶堆
  2. Queue<Integer> heap = new PriorityQueue<>();
  4. // 元素入堆
  5. heap.add(1);
  6. heap.add(4);
  7. heap.add(2);
  8. heap.add(6);
  9. heap.add(8);
  11. // 元素出堆（从小到大）
  12. heap.poll(); // -> 1
  13. heap.poll(); // -> 2
  14. heap.poll(); // -> 4
  15. heap.poll(); // -> 6
  16. heap.poll(); // -> 8