梦回前端系列02数据结构篇

关于梦回前端

每天一个重要的知识点，以问答的形式进行反推，利用碎片时间来完成自我提升

Day02 数据结构篇

说在前面

最近有很多朋友问我，前端有没有必要学习数据结构及算法？

先说下我的结论
有必要，很有必要，非学不可

原因

• 程序员基本功离不开数据结构与算法(如果你想一直做切图仔可以忽视)
• 精益求精离不开数据结构与算法(如果你只想完成需求当我没说)
• 高级进阶离不开数据结构与算法(如果你说再干两月就回家继承几个亿家产了直接忽视)

看过一部电影《嫌疑人 X 的替身》剧中的男二是名数学鬼才，男一有句台词是这么讲的 ” 只要他想干的事，就没有干不成的 ”, 映射出这些基础的思想贯穿我们整个日常

什么是数据结构？为什么我们要使用数据结构？

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合, 精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关

晦涩？没关系，大白话来翻译一下, 咱们家的大别墅中橱柜，衣柜，鞋柜都有吧，鞋柜放大门口，衣柜放在卧室，这些就是结构，一个合理的结构能帮助我们以最少的成本达到最优解

常见的数据结构有哪些?

1. 数组(Array)

一种 聚合 数据类型，它是将具有相同类型的若干变量 有序地 组织在一起的集合

1. 栈(Stack)

一种特殊的 线性表 ，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照 后进先出 的原则来存储数据

1. 队列(Queue)

一种特殊的 线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作

1. 链表(Linked List)

一种数据元素按照 链式存储结构 进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。

1. 树(Tree)

典型的 非线性 结构，它是包括， 2 个结点 的有穷集合 K。在树结构中，有且仅有 一个根结点

1. 图(Graph)

一种 非线性 数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对

1. 堆(Heap)

一种 特殊的树形 数据结构，一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构

1. 散列表(Hash)

散列表源自于散列函数 (Hash function)，其思想是如果在结构中存在 关键字和 T 相等 的记录，那么必定在 F(T) 的存储位置可以找到该记录

数组跟链表的特点？分别适应于什么场景？

以下由梦回前端成员 @panda 整理

数组

因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高，但在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间

应用场景: 数据比较少；经常做的运算是按序号访问数据元素；数组更容易实现，任何高级语言都支持；构建的线性表较稳定

链表

链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活

应用场景：对线性表的长度或者规模难以估计；频繁做插入删除操作；构建动态性比较强的线性表

队列跟栈的特点？分别是适应于什么场景？

以下由梦回前端成员 @panda 整理

栈

特点：栈是一种只能从表的一端存取数据且遵循 “ 先进后出 ” 原则的线性存储结构

应用场景：算符优先算法求表达式的值、表达式的括号匹配问题、迷宫求解、浏览器的 ” 回退 ”、进制转换等问题都具有先进后出的特点，需使用栈结构

生活中的先进先出-乒乓球盒，先放进的球要等后面的全部拿出

队列

特点：队列中数据的进出要遵循 “ 先进先出 ” 的原则

应用场景：舞伴问题、操作系统的进程、作业管理中的先进先出服务、字符序列是否回文等由于具有先进先出的特点，需要使用队列结构

生活中的先进先出-停车场，后来的车要等前面的车全部开走

请简述一下你理解的树与图

• 树 (无向图) 是图，图不一定是树
• 树一对多，图多对多
• 树有根节点，图没有
• 树有层次划，图没有
• 树可以递归，图不一定
• 树非根节点必有父节点，图不一定

散列表（Hash Table）的特点？适应场景有哪些？

以下由梦回前端成员 @panda 整理

特点

• 长变短：Hash 算法可以将任意长度的数据 Hash 成固定长度的数据。
• 速度快：Hash 算法基本上是异或和位移操作，速度很快。
• 不可逆：由 hash 结果找到 hash 前的字符串是困难的。
• 低碰撞：存在这样的情况，Hash 前输入不同，Hash 后输出相同，但绝大多数情况是输入不同，输出不同。

应用场景

• HashTable 肯定会应用到数据库的实现中，数据库是典型的字典模型。另外 HashTable 在 Linux 内核中也有应用，很多场景均使用了 hash table（hlist），如 tasklet、页表维护等

最后

如果你想系统学习前端并且能够坚持，欢迎加入我们共同成长，扫码回复 1 即可，在这里，你不是一个人在战斗

点击加入