基础数据结构

简介

数据结构是用来描述数据在计算机内存中组织方式的形式。

Bit/Byte

• bit 是内存中最小的数据单位，为一个数据位；

• 8 个 bit 组成一个 byte。

字符串(string)

• 字符串匹配
• 字符串转换
• 公共前缀

数组/向量(array)

• 查找
• 排序

双端队列(deque)

链表(list)

• 单向链表
• 双向链
• 跳表(SkipList)
• 舞蹈链(Dancing Link)
  • 排序
  • 有序链表合并
  • 反转
  • 交叉点
  • 循环点

树(tree)

• 二叉树(BST)
• 完全平衡二叉树(AVL)
• 红黑树(RB Tree)
• B 树
• B+树
• 线段树
• 字典树(Trie Tree)

堆(heap)

栈(stack)

队列(queue)

• BlockQueue
• 优先队列

哈希表(hashmap)

• 拉链法
• 重定位法
• 二次哈希

集合(set)

图(graphic)

缓存(Cache)

• LRU(Latest Recent Used): 最近使用时间

• LFU(Latest Frequently Used)：最少使用次数