1.数组

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

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

数组的基本操作
操作 时间复杂度
读取元素 O(1)
更新元素 O(1)
O(n)
删除元素 O(n)
数组的优势和劣势

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

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

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

2.链表

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

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

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

链表的基本操作
操作 时间复杂度
查找元素 O(n)
更新节点 不考虑查找过程的话是O(1)
插入节点 不考虑查找过程的话是O(1)
删除元素 不考虑查找过程的话是O(1)
数组 vs 链表
结构 查找 更新 插入 删除
数组 O(1) O(1) O(n) O(n)
链表 O(n) O(1) O(1) O(1)

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

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

3.栈

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

栈的基本操作
操作 时间复杂度
入栈 O(1)
出栈 O(1)

4.队列

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

队列的基本操作
操作 时间复杂度
入队 O(1)
出队 O(1)

5.散列表

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

散列表的基本操作
操作 时间复杂度
写操作 不同实现介于O(1)~O(n)间
读操作 接近于O(1)