常见的数据结构及算法

1、数据结构

1.1、数组

数组是比较常见的数据结构。创建数据必须是内存中的一段连续的空间，另外，数组中也必须存放相同类型的数据。数组通过下标读取数组元素，随机读写速度快是数组的一大特性。内存结构如下图：

数组的特点：随机读写快，插入较慢。

1.2、链表



链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表中的每个数据元素都必须存储指向下一个元素地址的指针。如果要在链表中查找一个元素，必须从第一个元素开始找。链表的结构如下图：

链表的特点：查询较慢，插入较快。

1.3、Hash表

hash表是根据Key而直接进行访问的数据结构。它通过把key值映射到表中一个位置来访问记录，以加快查找的速度。本质上是数组与链表的一种结合，内存结构如下图：

上图中，左侧是数组，数组元素存放的是key的hashcode，不同的key计算出的hashcode有可能相同，这时就是“hash冲突”。当hash冲突时，在采用链表顺序存储。hash表的特点：既能快速访问数据，也能快速增删数据。

1.4、栈

栈也叫堆栈，是一种操作受限的线性表（数组、链表都是线性表）。结构如下图：

特点：后进先出，即后面加进来的数据，必须首先比删除。