Linux之父Linus曾说“优秀的程序员更在意数据结构和彼此间的联系。”数据结构是软件的骨架也是面试常客。本文速览十种常见数据结构。链表节点序列每个节点存数据和指向下一个节点的指针。双向链表还有前驱指针。增删快查找慢。堆栈后进先出LIFO像一叠书只能从顶部操作。主要操作为push入栈、pop出栈、peek查看栈顶。队列先进先出FIFO像排队买单。入队enqueue在队尾添加出队dequeue从队首移除。集合无序、无重复。支持并集、交集、差集和子集判断。Map字典键值对存储键唯一查找快速。支持增删改查。哈希表Map的一种用散列函数将键映射到存储位置。理想情况下查找、插入、删除均为O(1)需处理碰撞。二叉搜索树每个节点最多两子左子小于父节点右子大于父节点。查找、插入、删除平均O(log n)。前缀树字典树常用于单词存储和自动补全。每个节点存一个字母并用布尔值标记单词结尾。二叉堆完全二叉树最大堆父节点大于子节点最小堆反之。适合优先队列插入和删除O(log n)。图由节点顶点和边组成分有向和无向。用邻接表或邻接矩阵表示遍历常用广度优先BFS和深度优先DFS。大多数高级语言内置了这些结构但理解其实现方能写出高性能代码。
Linux之父Linus曾说“优秀的程序员更在意数据结构和彼此间的联系。”数据结构是软件的骨架也是面试常客。本文速览十种常见数据结构。链表节点序列每个节点存数据和指向下一个节点的指针。双向链表还有前驱指针。增删快查找慢。堆栈后进先出LIFO像一叠书只能从顶部操作。主要操作为push入栈、pop出栈、peek查看栈顶。队列先进先出FIFO像排队买单。入队enqueue在队尾添加出队dequeue从队首移除。集合无序、无重复。支持并集、交集、差集和子集判断。Map字典键值对存储键唯一查找快速。支持增删改查。哈希表Map的一种用散列函数将键映射到存储位置。理想情况下查找、插入、删除均为O(1)需处理碰撞。二叉搜索树每个节点最多两子左子小于父节点右子大于父节点。查找、插入、删除平均O(log n)。前缀树字典树常用于单词存储和自动补全。每个节点存一个字母并用布尔值标记单词结尾。二叉堆完全二叉树最大堆父节点大于子节点最小堆反之。适合优先队列插入和删除O(log n)。图由节点顶点和边组成分有向和无向。用邻接表或邻接矩阵表示遍历常用广度优先BFS和深度优先DFS。大多数高级语言内置了这些结构但理解其实现方能写出高性能代码。
