常见数据结构

如有笔误，欢迎留言指正或讨论！

数据结构是计算机存储、组织数据的方式。不同场景选择的数据结构可以提高高效的运行或存储效率！常见数据结构：数组-array、链表-linkedList、队列-queue、栈-stack，树-tree、散列表-hash、堆-heap、图-graph 。

数组是一种线性结构，而且在物理内存中占据着一块连续的内存。

优点：访问数据简单。数据储存在连续的空间上，每个数据的内存地址都是通过数组下标就可以直接访问数据(也叫：随机访问如array[2]) 。

缺点：添加、删除比较耗费时间。新增或删除数据，首先保证足够的空间，然后把已有的数据一个个移动。

链表在物理存储单位上是非连续的、非顺序的存储结构。数据元素是通过链表的指针地址实现，每个元素包含两个节点：存储元素的数据域(内存空间)、指向下一个节点地址的指针域。

优点：数据添加和删除方便。只需要更改指定的指向就可以了。

缺点：访问比较耗费时间。因为数据都是分散存储的，所以访问数据只能从第一个数据开始，顺着指针的指向逐一往下访问。

vs	访问	添加	删除
链表	慢	快	快
数组	快	慢	慢

栈也是一种数据呈线性排列数据结构。

添加称之为入栈(push),删除称之为出栈(pop) 。

特点是先进后出(Last In First Out 简称LIFO)。类似于一个桶，数据依次放入，先进数据的在桶内的最下边，后进的数据在桶内的上边。

队列中的添加和删除数据的操作都是在两端进行的，一端添加元素另一端取出元素(先进先出 First In First Out，简称FIFO ) 。

散列表(也称哈希表)通过key和value来映射到集合中的一个位置，方便快速找到集合中的对应元素。

堆是一种图的树形结构，用于实现 "优先队列(priority queues)"。优先队列是一种数据结构，可以自由添加数据，但去除数据时要从最小值开始按顺序取出。

堆在树形结构中，在各个顶点被称为 "结点(node)" 数据就存储这些节点中。

它是由n(n >= 1)个有限节点组成一个具有层次关系的集合。

图是由结点的有穷集合V和边的集合E组成。为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。按照顶点指向的方向可分为无向图和有向图。