本文南京万和Java培训汇总了技术面试时需要了解的算法和数据结构知识。

　　数据结构部分

　　链表

　　链表是一种由节点（Node）组成的线性数据集合，每个节点通过指针指向下一个节点。它是一种由节点组成，并能用于表示序列的数据结构。

　　单链表：每个节点仅指向下一个节点，最后一个节点指向空（null）。

　　双链表：每个节点有两个指针p，n。p指向前一个节点，n指向下一个节点；最后一个节点指向空。

　　循环链表：每个节点指向下一个节点，最后一个节点指向第一个节点。

　　时间复杂度：

　　索引：O(n)

　　查找：O(n)

　　插入：O(1)

　　删除：O(1)

　　栈

　　栈是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。

　　后进先出的数据结构（Last In First Out, LIFO）

　　时间复杂度

　　索引：O(n)

　　查找：O(n)

　　插入：O(1)

　　删除：O(1)

　　队列

　　队列是一个元素集合，支持两种基本操作：enqueue 用于添加一个元素到队列，dequeue 用于删除队列中的一个元素。

　　先进先出的数据结构（First In First Out, FIFO）。

　　时间复杂度

　　索引：O(n)

　　查找：O(n)

　　插入：O(1)

　　删除：O(1)

　　树

　　树是无向、联通的无环图。

　　二叉树

　　二叉树是一个树形数据结构，每个节点最多可以有两个子节点，称为左子节点和右子节点。

　　满二叉树（Full Tree）：二叉树中的每个节点有 0 或者 2 个子节点。

　　完美二叉树（Perfect Binary）：二叉树中的每个节点有两个子节点，并且所有的叶子节点的深度是一样的。

　　完全二叉树：二叉树中除最后一层外其他各层的节点数均达到最大值，最后一层的节点都连续集中在最左边。

　　二叉查找树

　　二叉查找树（BST）是一种二叉树。其任何节点的值都大于等于左子树中的值，小于等于右子树中的值。

　　时间复杂度

　　索引：O(log(n))

　　查找：O(log(n))

　　插入：O(log(n))

　　删除：O(log(n))

　　字典树

　　字典树，又称为基数树或前缀树，是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值，而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀，根节点则是空字符串。

　　树状数组

　　树状数组，又称为二进制索引树（Binary Indexed Tree，BIT），其概念上是树，但以数组实现。数组中的下标代表树中的节点，每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和，在整个树更新的过程中，这些计算的值也同样会被更新。

　　时间复杂度

　　区间求和：O(log(n))

　　更新：O(log(n))

　　线段树

　　线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。

　　时间复杂度

　　区间查找：O(log(n))

　　更新：O(log(n))

　　堆

　　堆是一种基于树的满足某些特性的数据结构：整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中，父节点的键值永远大于等于所有子节点的键值，根节点的键值是最大的。最小堆中，父节点的键值永远小于等于所有子节点的键值，根节点的键值是最小的。

　　时间复杂度

　　索引：O(log(n))

　　查找：O(log(n))

　　插入：O(log(n))

　　删除：O(log(n))

　　删除最大值/最小值：O(1)

　　以上是南京万和Java培训机构讲师分享的技术面试宝典，后续会为大家提供更多的技术讲解。