数据结构选对了,代码效率能提升十倍不止。我见过太多项目因为用了错误的数据结构,性能上不去只能硬着头皮优化。
下面这10个数据结构是我日常开发中最常用的,每个都有实际应用场景。
List - 列表
List是最常用的数据结构,有序集合可以重复支持按索引访问。保存Twitter动态、文章评论、购物车商品都很合适。
const tweets = [
{ id: 1, content: "今天天气不错" },
{ id: 2, content: "刚写完一篇文章" }
]
tweets.push({ id: 3, content: "周末要去爬山" })
const firstTweet = tweets[0]
Stack - 栈
栈是后进先出(LIFO)的数据结构,就像一摞盘子只能从最上面拿。文字编辑器的撤销重做、浏览器历史记录、函数调用栈都在用。
class TextEditor {
constructor() {
this.content = ""
this.history = [] // 用数组模拟栈
}
write(text) {
this.history.push(this.content)
this.content += text
}
undo() {
if (this.history.length > 0) {
this.content = this.history.pop()
}
}
}
3. Queue - 队列
场景: 打印任务队列、消息队列、游戏中的用户操作
队列是先进先出(FIFO)的数据结构,就像排队买票,先来的先服务。
// 打印任务队列
class PrintQueue {
constructor() {
this.queue = []
}
addJob(job) {
this.queue.push(job) // 从队尾添加
console.log(`任务 ${job.id} 加入队列`)
}
process() {
if (this.queue.length > 0) {
const job = this.queue.shift() // 从队头取出
console.log(`正在打印: ${job.document}`)
}
}
}
// 使用
const printer = new PrintQueue()
printer.addJob({ id: 1, document: "报告.pdf" })
printer.addJob({ id: 2, document: "简历.docx" })
printer.process() // 打印报告.pdf
printer.process() // 打印简历.docx
适用场景: 任务调度、消息传递、缓冲区。
4. Hash Table - 哈希表
场景: 缓存系统、用户信息存储、去重
哈希表通过键值对存储数据,查找速度接近O(1),是最常用的数据结构之一。
// 缓存系统
class Cache {
constructor() {
this.data = {}
}
set(key, value) {
this.data[key] = value
}
get(key) {
return this.data[key]
}
has(key) {
return key in this.data
}
}
// 使用
const cache = new Cache()
cache.set("user:123", { name: "张三", age: 25 })
const user = cache.get("user:123")
适用场景: 快速查找、去重、缓存、计数。
5. Array - 数组
场景: 数学运算、矩阵操作、图像处理
数组是连续内存存储的数据结构,支持随机访问,适合数值计算。
// 图像像素处理
function adjustBrightness(imageData, factor) {
const pixels = imageData.data // 数组存储像素值
for (let i = 0; i < pixels.length; i += 4) {
pixels[i] *= factor // R
pixels[i + 1] *= factor // G
pixels[i + 2] *= factor // B
// A通道不变
}
return imageData
}
// 数学运算
const matrix1 = [[1, 2], [3, 4]]
const matrix2 = [[5, 6], [7, 8]]
// 矩阵乘法...
适用场景: 数值计算、矩阵运算、图像处理。
6. Heap - 堆
场景: 任务调度、Top K问题、优先队列
堆是一种特殊的树形结构,堆顶元素总是最大或最小。
// 任务优先级调度(最小堆)
class TaskScheduler {
constructor() {
this.tasks = []
}
addTask(task) {
this.tasks.push(task)
this.tasks.sort((a, b) => a.priority - b.priority)
}
getNextTask() {
return this.tasks.shift() // 取出优先级最高的
}
}
// 使用
const scheduler = new TaskScheduler()
scheduler.addTask({ name: "发送邮件", priority: 3 })
scheduler.addTask({ name: "备份数据", priority: 1 }) // 优先级最高
scheduler.addTask({ name: "清理缓存", priority: 2 })
const task = scheduler.getNextTask()
console.log(task.name) // 输出: 备份数据
适用场景: 优先队列、Top K问题、任务调度。
7. Tree - 树
场景: HTML文档结构、文件系统、AI决策树
树是分层的数据结构,每个节点有多个子节点。
// HTML DOM树
const htmlTree = {
tag: "div",
children: [
{
tag: "h1",
children: [{ text: "标题" }]
},
{
tag: "p",
children: [{ text: "段落内容" }]
}
]
}
// 文件系统
const fileSystem = {
name: "root",
type: "folder",
children: [
{ name: "src", type: "folder", children: [...] },
{ name: "package.json", type: "file" }
]
}
适用场景: 分层数据、DOM树、文件系统、决策树。
8. Suffix Tree - 后缀树
场景: 文档搜索、DNA序列匹配、字符串匹配
后缀树用于高效的字符串搜索,能在O(m)时间内找到模式串。
// 简化示例:在文档中搜索单词
class DocumentSearcher {
constructor(text) {
this.text = text
this.buildIndex()
}
buildIndex() {
// 构建后缀树索引
const words = this.text.split(/\s+/)
this.index = new Map()
words.forEach((word, pos) => {
if (!this.index.has(word)) {
this.index.set(word, [])
}
this.index.get(word).push(pos)
})
}
search(word) {
return this.index.get(word) || []
}
}
// 使用
const doc = "数据结构是编程的基石 数据结构很重要"
const searcher = new DocumentSearcher(doc)
console.log(searcher.search("数据结构")) // [0, 10]
适用场景: 全文搜索、字符串匹配、生物信息学。
9. Graph - 图
场景: 社交网络关系、地图导航、依赖关系
图由节点和边组成,用于表示事物之间的关系。
// 社交网络好友关系
const socialGraph = {
"张三": ["李四", "王五"],
"李四": ["张三", "赵六"],
"王五": ["张三"],
"赵六": ["李四"]
}
// 查找两人的共同好友
function findCommonFriends(person1, person2) {
const friends1 = new Set(socialGraph[person1])
const friends2 = socialGraph[person2]
return friends2.filter(f => friends1.has(f))
}
console.log(findCommonFriends("张三", "李四")) // ["王五"]
适用场景: 社交网络、路径规划、依赖分析、推荐系统。
10. R-Tree - R树
场景: 地理位置搜索、地图应用、最近邻查找
R树是空间索引结构,用于高效查询空间数据。
// 简化示例:查找附近的餐厅
class RestaurantFinder {
constructor(restaurants) {
this.restaurants = restaurants
}
findNearby(location, radius) {
return this.restaurants.filter(r => {
const distance = this.calculateDistance(location, r.location)
return distance <= radius
})
}
calculateDistance(loc1, loc2) {
// 简化的距离计算
return Math.sqrt(
Math.pow(loc1.lat - loc2.lat, 2) +
Math.pow(loc1.lng - loc2.lng, 2)
)
}
}
// 使用
const restaurants = [
{ name: "麦当劳", location: { lat: 39.9, lng: 116.4 } },
{ name: "肯德基", location: { lat: 39.91, lng: 116.41 } }
]
const finder = new RestaurantFinder(restaurants)
const nearby = finder.findNearby({ lat: 39.9, lng: 116.4 }, 0.1)
适用场景: 地理位置查询、地图服务、空间数据库。
Bonus: Vertex Buffer - 顶点缓冲区
场景: 游戏开发、3D渲染、图形应用
顶点缓冲区是GPU渲染的专用数据结构,存储顶点数据发送给GPU。
// WebGL示例
const vertices = new Float32Array([
// x, y, z坐标
0.0, 0.5, 0.0,
-0.5, -0.5, 0.0,
0.5, -0.5, 0.0
])
// 创建顶点缓冲区
const buffer = gl.createBuffer()
gl.bindBuffer(gl.ARRAY_BUFFER, buffer)
gl.bufferData(gl.ARRAY_BUFFER, vertices, gl.STATIC_DRAW)
适用场景: 游戏开发、3D渲染、图形应用。
最后想说的
这10个数据结构覆盖了大部分开发场景:List有序数据,Stack撤销操作,Queue任务调度,Hash Table快速查找,Array数值计算,Heap优先队列,Tree分层数据,Suffix Tree字符串搜索,Graph关系网络,R-Tree空间查询,Vertex Buffer GPU渲染。
没有最好的数据结构,只有最适合场景的数据结构。理解它们的特性,能帮你写出更好的代码。
有帮到你的话,点个赞或者收藏吧。有问题评论区见。
