很多初学者觉得数据结构与算法是面试造火箭工作拧螺丝的东西。实际上日常写代码的过程中你时时刻刻都在和数据结构和算法打交道只是没有意识到而已。这篇文章不讲红黑树、B树这些复杂结构就说说工作中最常用的4种数据结构。1. 数组——最基础也最高效数组是连续内存空间支持O(1)的随机访问。Java里的ArrayList、Python里的list、C里的vector底层都是数组。什么时候用数组需要频繁按下标访问元素的时候。比如存储一批用户ID、一周七天的温度数据。缺点是插入删除成本高要移动元素扩容有性能开销。一个小技巧如果你知道数据规模的上限初始化时指定容量可以避免多次扩容带来的性能损耗。java// Java - 指定初始容量 ListString list new ArrayList(1000);python# Python - 列表预留空间虽然不直接支持但可以用乘法初始化 data [None] * 10002. 哈希表——O(1)的查找神器哈希表是工作中用得最多的数据结构没有之一。Java的HashMap、Python的dict、C的unordered_map底层都是哈希表。java// Java - 用HashMap做缓存 MapString, User userCache new HashMap(); User user userCache.getOrDefault(userId, loadFromDB(userId));python# Python - 用dict统计词频 word_count {} for word in words: word_count[word] word_count.get(word, 0) 1cpp// C - unordered_map的使用 #include unordered_map std::unordered_mapstd::string, int scores; scores[Alice] 100; auto it scores.find(Bob); if (it ! scores.end()) { std::cout it-second; }O(1)的查找、插入、删除让哈希表成为解决快速查找问题的不二之选。代价是内存消耗较大且元素无序Java的LinkedHashMap、Python 3.7的dict可以保持插入顺序。实际应用场景缓存数据用户信息、配置项去重用Set底层也是哈希表计数统计词频、PV/UV快速查找根据ID查对象3. 链表——灵活的动态结构链表的优势在于插入删除是O(1)不需要连续内存。Java的LinkedList、Python的deque都基于链表或类似的链式结构。python# Python - 用deque实现高效的头尾操作 from collections import deque d deque([1, 2, 3]) d.appendleft(0) # 左侧插入 O(1) d.append(4) # 右侧插入 O(1) first d.popleft() # 左侧弹出 O(1)实际工作中链表很少独立使用但它是LRU缓存、消息队列等更高级结构的基础。算法题里常见的反转链表、合并两个有序链表考察的其实是对指针/引用操作的熟练度。java// Java - 手写一个简单链表的节点 class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } } // 反转链表 ListNode reverse(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; }4. 栈和队列——规则简单的工具栈是后进先出LIFO队列是先进先出FIFO。这两个结构规则简单但应用极广。栈的应用函数调用栈递归就是靠栈括号匹配编译器检查语法表达式求值中缀转后缀浏览器的前进后退队列的应用消息队列RabbitMQ、Kafka的底层思想BFS广度优先搜索线程池的任务队列缓冲区的数据排队python# Python - deque可以当栈也可以当队列 from collections import deque # 当作栈使用 stack deque() stack.append(1) # 入栈 stack.append(2) top stack.pop() # 出栈 → 2 # 当作队列使用 queue deque() queue.append(1) # 入队 queue.append(2) first queue.popleft() # 出队 → 1java// Java - 栈和队列 StackInteger stack new Stack(); stack.push(1); int top stack.pop(); QueueInteger queue new LinkedList(); queue.offer(1); int first queue.poll();5. 额外补充树结构简单提一下虽然文章标题说4种但二叉树在开发中也很常见值得简单一提。二叉搜索树BST可以让查找、插入、删除都达到O(log n)的时间复杂度。但普通BST可能退化成链表所以实际生产中用的是平衡二叉树如Java的TreeMap、C的std::map底层是红黑树。java// Java - TreeMap基于红黑树有序 MapString, Integer sortedMap new TreeMap(); sortedMap.put(banana, 1); sortedMap.put(apple, 2); sortedMap.put(cherry, 3); // 遍历会按key的自然顺序输出apple, banana, cherry学会选择合适的数据结构写代码的时候多问自己一句这里用什么数据结构最合适场景推荐数据结构需要快速按位置取元素数组ArrayList需要快速查找某个键对应的值哈希表HashMap/dict需要频繁在两端插入删除双端队列deque需要按顺序取出元素并移除队列Queue需要后进先出的场景栈Stack需要有序存储且频繁查找平衡树TreeMap需要去重哈希集合HashSet/set
很多初学者觉得数据结构与算法是面试造火箭工作拧螺丝的东西。实际上日常写代码的过程中你时时刻刻都在和数据结构和算法打交道只是没有意识到而已。这篇文章不讲红黑树、B树这些复杂结构就说说工作中最常用的4种数据结构。1. 数组——最基础也最高效数组是连续内存空间支持O(1)的随机访问。Java里的ArrayList、Python里的list、C里的vector底层都是数组。什么时候用数组需要频繁按下标访问元素的时候。比如存储一批用户ID、一周七天的温度数据。缺点是插入删除成本高要移动元素扩容有性能开销。一个小技巧如果你知道数据规模的上限初始化时指定容量可以避免多次扩容带来的性能损耗。java// Java - 指定初始容量 ListString list new ArrayList(1000);python# Python - 列表预留空间虽然不直接支持但可以用乘法初始化 data [None] * 10002. 哈希表——O(1)的查找神器哈希表是工作中用得最多的数据结构没有之一。Java的HashMap、Python的dict、C的unordered_map底层都是哈希表。java// Java - 用HashMap做缓存 MapString, User userCache new HashMap(); User user userCache.getOrDefault(userId, loadFromDB(userId));python# Python - 用dict统计词频 word_count {} for word in words: word_count[word] word_count.get(word, 0) 1cpp// C - unordered_map的使用 #include unordered_map std::unordered_mapstd::string, int scores; scores[Alice] 100; auto it scores.find(Bob); if (it ! scores.end()) { std::cout it-second; }O(1)的查找、插入、删除让哈希表成为解决快速查找问题的不二之选。代价是内存消耗较大且元素无序Java的LinkedHashMap、Python 3.7的dict可以保持插入顺序。实际应用场景缓存数据用户信息、配置项去重用Set底层也是哈希表计数统计词频、PV/UV快速查找根据ID查对象3. 链表——灵活的动态结构链表的优势在于插入删除是O(1)不需要连续内存。Java的LinkedList、Python的deque都基于链表或类似的链式结构。python# Python - 用deque实现高效的头尾操作 from collections import deque d deque([1, 2, 3]) d.appendleft(0) # 左侧插入 O(1) d.append(4) # 右侧插入 O(1) first d.popleft() # 左侧弹出 O(1)实际工作中链表很少独立使用但它是LRU缓存、消息队列等更高级结构的基础。算法题里常见的反转链表、合并两个有序链表考察的其实是对指针/引用操作的熟练度。java// Java - 手写一个简单链表的节点 class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } } // 反转链表 ListNode reverse(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; }4. 栈和队列——规则简单的工具栈是后进先出LIFO队列是先进先出FIFO。这两个结构规则简单但应用极广。栈的应用函数调用栈递归就是靠栈括号匹配编译器检查语法表达式求值中缀转后缀浏览器的前进后退队列的应用消息队列RabbitMQ、Kafka的底层思想BFS广度优先搜索线程池的任务队列缓冲区的数据排队python# Python - deque可以当栈也可以当队列 from collections import deque # 当作栈使用 stack deque() stack.append(1) # 入栈 stack.append(2) top stack.pop() # 出栈 → 2 # 当作队列使用 queue deque() queue.append(1) # 入队 queue.append(2) first queue.popleft() # 出队 → 1java// Java - 栈和队列 StackInteger stack new Stack(); stack.push(1); int top stack.pop(); QueueInteger queue new LinkedList(); queue.offer(1); int first queue.poll();5. 额外补充树结构简单提一下虽然文章标题说4种但二叉树在开发中也很常见值得简单一提。二叉搜索树BST可以让查找、插入、删除都达到O(log n)的时间复杂度。但普通BST可能退化成链表所以实际生产中用的是平衡二叉树如Java的TreeMap、C的std::map底层是红黑树。java// Java - TreeMap基于红黑树有序 MapString, Integer sortedMap new TreeMap(); sortedMap.put(banana, 1); sortedMap.put(apple, 2); sortedMap.put(cherry, 3); // 遍历会按key的自然顺序输出apple, banana, cherry学会选择合适的数据结构写代码的时候多问自己一句这里用什么数据结构最合适场景推荐数据结构需要快速按位置取元素数组ArrayList需要快速查找某个键对应的值哈希表HashMap/dict需要频繁在两端插入删除双端队列deque需要按顺序取出元素并移除队列Queue需要后进先出的场景栈Stack需要有序存储且频繁查找平衡树TreeMap需要去重哈希集合HashSet/set
