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) |