什么是数据结构
链表
数组
栈
队列
哈希表

什么是数据结构

数据结构决定数据的顺序和位置关系
我们把内存看成一个一个的小格子，数据存储在这些小格子中。
数据存储于内存时，决定了数据的顺序和位置关系的就是“数据结构”。
选择合适的数据结构以提高内存的利用率
将数据存储于内存时，根据使用目的的选择合适的数据结构，可以提高内存的利用率。
我们可以大概将数据结构分成 ‘线性排列’ 和 ‘非线性排列’ 。

链表

链表是线性排列的数据结构之一。在链表中，数据的添加和删除比较方便，就是访问比较耗费时间。
链表有多个节点链接而成。以单链表为例，当前节点除了存储自身数据以外，还存储了下一个节点的地址。
链表的数据一般都是分散存储于内存中，无需存储在连续空间内。如果要访问数据的话，只能从第一个数据开始，顺着指针的指向一一向下访问（顺序访问）。但是，如果要添加数据的话，只需要改变添加位置前后指针的指向就可以了。数据的删除也一样简单，改变前面节点的指针指向到删除节点的下级节点就可以了。
用时间复杂度来描述的话，链表的数据量为n，增加的时间复杂度为O(1)，删除的为O(1), 查询的为O(n)。

当然，还有首位节点相连的环形链表，
节点中两个指针指向上下级节点的双向链表。
不同的应用场景选择使用不同的数据结构。

数组

数组也是线性排列的数据结构之一。在数组中，访问数据十分简单，而添加和删除数据比较耗费时间。
数组内的数据按顺序排列在内存的连续空间内，一般用数组的首位元素的地址来代表数组的地址。由于数据是存储在连续空间内，所以每个数据的内存地址都可以通过数组下表计算出，所以能直接访问目标数据（随机访问）。但是要增加数据的时候，首先要开辟一点空间，保证元素可以正常插入，然后将插入位置之后的元素逐步向后移动，再在空出来的位置上写入新数据。删除则是，先删除目标数据，然后将后边的元素逐步向前移动，随后再删除掉多余的空间。
用时间复杂度来说，数组的数据量为n，查询的时间复杂度为O(1), 增加的为O(n), 删除的为O(n)。

在链表和数组中，数据都是线性的排成一列，
在链表中增删比较简单，在数组中查询比较简单，
我们可以根据哪种操作比较频繁来决定使用哪种数据结构。

栈

栈也是一种数据呈线性排列的数据结构，但是在这种数据结构中，我们只能访问最新添加的数据。
像栈这种最后添加的数据最先被取出，即后进先出的数据结构，我们称为Last In First Out, 简称LIFO。
在栈中，添加和删除数据只能在一端进行，访问数据也只能访问最顶端的数据，想要访问中间的数据的时候，就必须通过出栈操作将目标数据移动到栈顶才行。
看起来操作十分不便，但是在仅仅访问最新数据的时候，它就非常方便了。

队列

队列也是一种数据呈线性排列的数据结构，虽然与栈看起来有些相似，但是队列中添加和删除数据的操作分别在队列的两端。在队列中，处理总是从第一名开始往后进行，而新来的数据只能排在队尾。
像队列这种最先进去的数据最先被取出，即先进先出的数据结构，我们称为First In First Out，简称FIFO。
与栈类似，队列中可以操作数据的位置也有一定的限制，队列中数据的添加和删除在两端进行，也不能访问处于中间的数据，必须通过出队操作将目标数据变成首位才能访问。

哈希表

一般来说有哈希列表和哈希映射两种形式，实际上都是哈希表。我们先新建一个长度为n的数组，用来存储数据，存的时候 将元素或者键值对的键 执行哈希函数，然后拿得到的哈希值，对n取模，然后存入数组中相应的位置。如果需要存入的两条数据的哈希值对n取模相同的话，这种情况称为哈希冲突，遇到这种情况，则使用链表在已经存入的数据后边存入新数据。
查询的时候，取哈希值，取对n的模，然后查找链表。所以查询的效率比单纯的数组要高很多。
从这种存储方式来看，要看n定义的大小，如果n太小，那么很容易发生哈希冲突，查询效率会差很多，想反，如果n太大的话，则造成空间浪费。

    使用链表处理哈希冲突这种方法，叫做链地址法。
    除了这种方法，使用比较广泛的是开放地址法。
    是指，在冲突发生的时候，立刻计算一个候补地址，将数据存进去，
    如果仍然有冲突，变继续寻找下一个候补地址，直到有空的地址为止。
    可以多次使用哈希函数，或者线性探测法等方法来查询候补地址。

Tips：因为哈希表有哈希冲突的情况，所以不能很简单的将其放入线性数据结构中。只是大多数情况都以线性排列的数据呈现，所以在线性排列的数据结构中将其录入。