数据结构

数据结构这个词相信大家都不陌生，在很多场景下可能都听过，但你有没有考虑过“数据结构”究竟是一个什么东西呢？
数据结构即数据元素相互之间存在的一种和多种特定的关系集合。
一般你可以从两个维度来理解它，逻辑结构和存储结构。

逻辑结构

数据结构 - 图1
简单的来说逻辑结构就是数据之间的关系，逻辑结构大概统一的可以分成两种：线性结构、非线性结构。
线性结构：是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
常用的线性结构有: 栈，队列，链表，线性表。
—非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。
常见的非线性结构有 二维数组，树等。

存储结构

逻辑结构指的是数据间的关系，而存储结构是逻辑结构用计算机语言的实现。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储。
例如：数组在内存中的位置是连续的，它就属于顺序存储；链表是主动建立数据间的关联关系的，在内存中却不一定是连续的，它属于链式存储；还有顺序和逻辑上都不存在顺序关系，但是你可以通过一定的方式去放问它的哈希表，数据散列存储。

二叉树

树是用来模拟具有树状结构性质的数据集合。根据它的特性可以分为非常多的种类，对于我们来讲，掌握二叉树这种结构就足够了，它也是树最简单、应用最广泛的种类。
二叉树是一种典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。
数据结构 - 图2

二叉树遍历

重点中的重点，最好同时掌握递归和非递归版本，递归版本很容易书写，但是真正考察基本功的是非递归版本。

根据前序遍历和中序遍历的特点重建二叉树，逆向思维，很有意思的题目

  1. 若任意节点的左⼦子树不不空，则左⼦子树上所有结点的值均⼩小于它的 根结点的值;
  2. 若任意节点的右⼦子树不不空，则右⼦子树上所有结点的值均⼤大于它的 根结点的值;
  3. 任意节点的左、右⼦子树也分别为⼆二叉查找树。

链表

用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。

  • 需要遍历才能查询到元素，查询慢。
  • 插入元素只需断开连接重新赋值，插入快。

数据结构 - 图3
链表在开发中也是经常用到的数据结构，React16的 Fiber Node连接起来形成的Fiber Tree, 就是个单链表结构。

基本应用

主要是对链表基本概念和特性的应用，如果基础概念掌握牢靠，此类问题即可迎刃而解

对于单链表，因为我们只能在一个方向上遍历链表，所以第一种情景可能无法工作。然而，第二种情景，也被称为慢指针和快指针技巧，是非常有用的。

数组

数组是我们在开发中最常见到的数据结构了，用于按顺序存储元素的集合。但是元素可以随机存取，因为数组中的每个元素都可以通过数组索引来识别。插入和删除时要移动后续元素，还要考虑扩容问题，插入慢。
数组与日常的业务开发联系非常紧密，如何巧妙的用好数组是我们能否开发出高质量代码的关键。

双指针

上面链表中提到的一类题目，主要是利用两个或多个不同位置的指针，通过速度和方向的变换解决问题。注意这种技巧经常在排序数组中使用。

栈和队列

在上面的数组中，我们可以通过索引随机访问元素，但是在某些情况下，我们可能要限制数据的访问顺序，于是有了两种限制访问顺序的数据结构：栈（后进先出）、队列（先进先出）
数据结构 - 图4

哈希表

哈希的基本原理是将给定的键值转换为偏移地址来检索记录。
键转换为地址是通过一种关系（公式）来完成的，这就是哈希（散列）函数。
虽然哈希表是一种有效的搜索技术，但是它还有些缺点。两个不同的关键字，由于哈希函数值相同，因而被映射到同一表位置上。该现象称为冲突。发生冲突的两个关键字称为该哈希函数的同义词。
数据结构 - 图5
如何设计哈希函数以及如何避免冲突就是哈希表的常见问题。 好的哈希函数的选择有两条标准：

  • 1.简单并且能够快速计算
  • 2.能够在址空间中获取键的均匀人分布

例如下面的题目：

当用到哈希表时我们通常是要开辟一个额外空间来记录一些计算过的值，同时我们又要在下一次计算的过程中快速检索到它们，例如上面提到的两数之和、三数之和等都利用了这种思想。

堆

数据结构 - 图6
堆的底层实际上是一棵完全二叉树，可以用数组实现

  • 每个的节点元素值不小于其子节点 - 最大堆
  • 每个的节点元素值不大于其子节点 - 最小堆

堆在处理某些特殊场景时可以大大降低代码的时间复杂度，例如在庞大的数据中找到最大的几个数或者最小的几个数，可以借助堆来完成这个过程。

鸣谢：转载至作者：ConardLi，十分感谢！