算法和数据结构：第二章 数据结构基础

1.数组

​ 数组是有限个相同类型发变量所组成的有序集合，数组中的每一个变量被称为元素，数组是最简单、最常用的数据结构。

​ 数组的另一个特点是在内存中顺序存储，因此可以很好地思想逻辑上的顺序表。

数组的基本操作

数组的优势和劣势

优势：数据具有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应的元素，二分查找就是利用了数组的这个优势。

劣势：体现在插入和删除元素方面，由于数据元素连续紧密地存储在内存中，插入、删除元素会导致大量元素被迫移动，影响效率。

总体来说，数据适合读操作多，写操作少的场景。

2.链表

​ 链表是一种在物理存储上非连续非顺序的数据结构，有若干节点所组成。

​ 单向链表的每一个节点包含两部分，一部分是存放数据的变量，一部分是厨房指向下一个节点的指针。

​ 双向链表比单向链表稍微复杂一些，它的每个节点除了拥有数据和下一个节点的指针为，还拥有指向前一个节点的指针。

链表的基本操作

数组 vs 链表

数组的优势在于能快速定位元素，对于读操作多、写操作少的场景，用数据更适合。

链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适（？存疑，在尾部插入/删除元素使用数组应该更适合）

3.栈

​ 栈是一种线性数据结构，栈中的元素只能先进后出（FILO），最早进入的元素存放的位置叫栈低，最后进入的元素存放的位置叫栈顶。

栈的基本操作

4.队列

​ 队列是一种线性数据结构，队列中的元素只能先进先出（FIFO），队列的出口端叫对头，队列的入口端叫队尾。

队列的基本操作

5.散列表

​ 散列表也叫哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效找到它所匹配的Value，时间复杂度接近于O(1)。

散列表的基本操作