Review

1. 2019-08-14
2. 2024-09-08 08:22

[!Summary] 常见数据结构

1. 栈
2. 队列
3. 数组
4. 链表
5. 树
6. 图
7. 堆
8. 散列表

一、Introduction #

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

数组 #

数组是有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。 高效地查询数据 查找：O(1) 插入删除：O(n)

链表 #

链表是一种链式数据结构，有若干节点组成，每个节点包含指向下一节点的指针。 链表的物理存储方式是随机存储，访问方式是顺序访问。 能够灵活地进行查如何删除操作。 查找：O(n) 插入删除：O(1) 单向链表 双向链表

栈 #

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。入栈（push）、出栈（pop）。先入后出（FILO）

应用：

• 对“历史”的回溯
• 面包屑导航

1. 常规栈
2. 最小栈：提供 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

队列 #

队列是一种线性逻辑结构，可以用数组实现，也可以用链表实现。入队（enqueue）、出队（dequeue）。先入先出（FIFO）

应用：

• 对“历史”的回放
• 网络爬虫

双端队列 #

把栈和队列的特点结合起来

优先队列 #

谁的优先级高，谁先出队。

散列表 #

散列表也叫哈希表（hash table），是存储key-value映射的集合。对于一个key，读写O(1)。可以说是数据和链表的结合。 散列表通过哈希函数实现key和数据下表的转换。 通过开放寻址法和链表法解决哈希冲突。

Reference #