什么是数组

(资料图片)

数组(Array): 有限个相同类型的变量所组成的有序集合，数组中的每一个变量称为元素。

数组在内存中顺序存储。

Python中使用列表(list)和元组(tuple)这两种集合，本质上是对数组的封装；

列表是一个动态可扩展的数组，支持任意的增、删、改；

元组是一个不可变集合，一旦创建就不再支持修改

数组的优势与劣势：

数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。运用该优势的算法：二分查找

插入、删除元素都会导致大量元素被迫移动，影响效率

数组适合的是读操作多、写操作少的场景

什么是链表

链表(linked list)是一种物理上非连续、非顺序的数据结构，由若干节点(node)所组成。

单向链表中每个节点包含两部分，一是存放数据变量的data，另一个部分是指向下一个节点的指针next。

双向链表：每个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

数组的存储方式：顺序存储

链表的存储方式：随机存储

数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些；

链表的优势在于能够灵活地进行插入和删除操作，如果需要频繁插入、删除元素，用链表更合适一些

栈和队列

栈(stack)是一种线性数据结构，栈中的元素只能先入后出(First In Last Out, FILO)；

最早进入元素存放的位置叫做栈底(bottom)，最后进入的元素存放的位置叫做栈顶(top)；

栈可用数组或者链表来实现

栈的基本操作包括 入栈(push)和出栈(pop)

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。

Python语言中，列表实现了栈的功能，append(element)相当于入栈，pop(element)相当于出栈

队列(queue)是一种线性数据结构，队列中的元素只能先入先出(First In First Out,FIFO)；

队列的入口端叫做队尾，队列的出口端叫做队头;

队列可以用数组或者链表来实现

队列的基本操作：入队(enqueue)和出队(dequeue)

入队: 在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾

出队: 只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头

循环队列：假设一个队列经过反复的入队和出队操作，还剩下2个元素，在“物理”上分布于数组的末尾位置。这时又有一个新元素将要入队。在数组不做扩容的前提下，我们可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。这样一来，整个队列的元素就“循环”起来了。

在Python中，表示队列的工具由collections.deque、queue.Queue等

栈的应用: 

实现递归的逻辑

面包屑导航

队列的应用: 

在多线程中，争夺公平锁的等待队列

网络爬虫实现网站抓取

双端队列：

双端队列可以从队头一端可以入队或出队，也可以从队尾一端也可以入队或出队。

优先队列: 

谁的优先级最高，谁先出队，优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。

神奇的哈希表

哈希表(hash table)：散列表，提供键(Key)-值(Value)的映射关系，给出key，就可以高效地找到所匹配的Value

哈希表在本质上也是一个数组，数组根据下标，像a[0]、a[1]、a[2]、a[3]、a[4]这样来访

问，而哈希表则以字符串类型的Key为下标进行访问

Python中，哈希表对应的集合为字典(dict)

在Python及大多数面向对象的语言中，每一个对象都有属于自己的hash值，这个hash值是区分不同对象的重要标识。无论对象自身的类型是什么，它们的hash值都是一个整型变量

Python中的哈希函数利用了位运算的方式来优化性能

通过哈希函数，可以把字符串或其他类型的Key，转化成数组的下标index

哈希表的写操作(put)：

写操作就是在哈希表中插入新的键值对(Entry)

哈希冲突: 由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的

解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法

开放寻址法: 当一个Key通过哈希函数获得对应的数组下标已被占用时，我们可以寻找下一个空当位置

链表法: 哈希表数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入对应的链表中即可。

哈希表读操作(get)：通过给定的Key，在哈希表中查找对应的Value。

在众多编程语言中，有些语言的哈希表采用了链表法，最具代表性的就是

Java中的HashMap；

有些编程语言采用的是开放寻址法，比如Python中的dict。

有兴趣的读者可以看一下Python官方解释器（CPython）中，关于PyDictObject的C语言源码实现。

哈希表可以说是数组和链表的结合，它在算法中的应用很普遍，是一种非常重要的数据结构。

小结

什么是数组？

数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是O(1)，中间插入、删除数组元素的时间复杂度是O(n）

什么是链表？

链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是O(n)， 中间插入、删除节点的时间复杂度是O(1)

什么是栈？

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现；

栈包含入栈和出栈操作，遵循先入后出的原则(FILO)

什么是队列？

队列是一种线性逻辑结构，可以用数组实现，也可以用链表实现；

队列包含入队和出队的操作，遵循先入先出的原则(FIFO)

什么是哈希表？哈希表也叫做散列表，是存储Key-Value映射的集合；

对于某一个Key，哈希表可以在接近O(1)的时间内进行读写操作；

哈希表通过哈希函数实现Key和数组下表的转换，通过开放寻址法和链表法来解决哈希冲突