网站建设刂搜金手指下拉贰伍,网站有什么类型,wordpress为何经常被黑,石家庄市和城乡建设局网站前两天V哥跟一个老学员吃饭#xff0c;聊起面试大厂的事#xff0c;说为啥大厂面试第一看基本条件#xff0c;第二就是考数据结构算法#xff0c;其他高阶的内容会比较少#xff0c;最近V哥也在跟大厂对接这一块业务#xff0c;了解得多一些#xff0c;这是因为考察基本…前两天V哥跟一个老学员吃饭聊起面试大厂的事说为啥大厂面试第一看基本条件第二就是考数据结构算法其他高阶的内容会比较少最近V哥也在跟大厂对接这一块业务了解得多一些这是因为考察基本功能力被放到了重要位置大厂认为硬性条件比如学历过关基本功够扎实那对于实际工作用的上层技能内部培养就好也就是相比你掌握了多少多少牛逼的高阶技术他们更在乎你的基本功所以进大厂基本功必须要搞稳否则白扯今天 V 哥把总结好的22个常用的数据结构实现原理和示例分析分享给大家希望对你有帮助觉得内容有收获请帮忙转发给更多需求的朋友共同进步。
1.数组Array
数组是一种线性数据结构它由一系列元素组成这些元素通过索引进行访问。数组可以是一维的一维数组也可以是多维的多维数组在内存中连续存储。
示例代码实现
public class Main {public static void main(String[] args) {// 声明并初始化一个数组int[] array {1, 2, 3, 4, 5};// 访问数组元素System.out.println(第三个元素是 array[2]);// 修改数组元素array[2] 10;System.out.println(修改后的第三个元素是 array[2]);// 遍历数组元素System.out.println(数组元素为);for (int i 0; i array.length; i) {System.out.print(array[i] );}System.out.println();// 数组长度System.out.println(数组长度为 array.length);}
}实现原理解释
数组由相同类型的元素组成这些元素按照一定的顺序存储在内存中每个元素都可以通过索引来访问索引通常从0开始。数组的访问时间复杂度为 O(1)因为可以通过索引直接计算出要访问的元素在内存中的地址从而实现快速访问。数组的插入和删除操作可能比较耗时因为需要移动数组中的元素。在数组的开头或中间插入或删除元素时需要将插入点之后的所有元素向后或向前移动一位。数组的大小通常是固定的因此插入和删除元素时可能需要进行数组的扩容或缩容操作。
2.链表 (Linked List)
链表是由节点组成的线性数据结构每个节点包含数据和指向下一个节点的引用。
示例代码实现
class ListNode {int val;ListNode next;public ListNode(int val) {this.val val;this.next null;}
}public class LinkedList {private ListNode head;public LinkedList() {this.head null;}// 在链表末尾添加一个节点public void add(int val) {if (head null) {head new ListNode(val);} else {ListNode current head;while (current.next ! null) {current current.next;}current.next new ListNode(val);}}
}实现原理解释
链表的实现基于节点的概念。每个节点都包含一个数据元素和一个指向下一个节点的引用。在示例中我们创建了一个ListNode类来表示链表节点。然后我们通过LinkedList类来管理链表其中的add方法用于在链表末尾添加新节点。当链表为空时我们简单地将新节点设置为头节点。否则我们从头节点开始遍历链表直到找到最后一个节点然后将新节点连接到最后一个节点的next引用上。
3.栈 (Stack)
栈是一种后进先出LIFO的数据结构只允许在栈顶进行插入和删除操作。
示例代码实现
import java.util.EmptyStackException;public class Stack {private ListNode top;public Stack() {this.top null;}// 入栈操作public void push(int val) {ListNode newNode new ListNode(val);newNode.next top;top newNode;}// 出栈操作public int pop() {if (isEmpty()) {throw new EmptyStackException();}int val top.val;top top.next;return val;}// 获取栈顶元素public int peek() {if (isEmpty()) {throw new EmptyStackException();}return top.val;}// 判断栈是否为空public boolean isEmpty() {return top null;}
}实现原理解释
栈的实现通常基于链表或数组。在示例中我们选择了链表作为底层数据结构来实现栈。栈的入栈操作push将一个新元素添加到栈顶。这通过创建一个新节点并将其指向原栈顶节点来完成。然后我们将新节点设置为栈顶。栈的出栈操作pop将栈顶元素移除并返回其值。我们将栈顶节点指向原栈顶节点的下一个节点并返回原栈顶节点的值。栈的peek操作用于获取栈顶元素的值而isEmpty操作用于检查栈是否为空。
4.队列 (Queue)
队列是一种先进先出FIFO的数据结构允许在队尾进行插入操作在队首进行删除操作。
示例代码实现
import java.util.LinkedList;public class Queue {private LinkedListInteger list;public Queue() {this.list new LinkedList();}// 入队操作public void enqueue(int val) {list.addLast(val);}// 出队操作public int dequeue() {if (isEmpty()) {throw new IllegalStateException(Queue is empty);}return list.removeFirst();}// 获取队首元素public int peek() {if (isEmpty()) {throw new IllegalStateException(Queue is empty);}return list.getFirst();}// 判断队列是否为空public boolean isEmpty() {return list.isEmpty();}
}实现原理解释
队列的实现通常基于链表或数组。在示例中我们使用了Java标准库提供的LinkedList来实现队列。队列的入队操作enqueue将一个新元素添加到队列的末尾。这通过将新元素添加到链表的末尾来完成。队列的出队操作dequeue将队列首部的元素移除并返回其值。我们使用链表的removeFirst方法来实现。队列的peek操作用于获取队首元素的值而isEmpty操作用于检查队列是否为空。
通过理解这些数据结构的实现原理和示例代码你可以更好地应用它们来解决实际问题并且能够更深入地理解它们的工作原理。
5.双端队列Deque
双端队列Deque也称为双向队列是一种特殊的队列它允许在队列的两端进行插入和删除操作。双端队列可以从头部和尾部同时插入和删除元素因此具有队列和栈的特性。
示例代码实现
以下是使用双向链表实现双端队列的简单示例
import java.util.LinkedList;public class MyDeque {private LinkedListInteger deque;public MyDeque() {deque new LinkedList();}// 从头部插入元素public void addFirst(int item) {deque.addFirst(item);}// 从尾部插入元素public void addLast(int item) {deque.addLast(item);}// 从头部删除元素public int removeFirst() {return deque.removeFirst();}// 从尾部删除元素public int removeLast() {return deque.removeLast();}// 获取头部元素public int getFirst() {return deque.getFirst();}// 获取尾部元素public int getLast() {return deque.getLast();}// 判断双端队列是否为空public boolean isEmpty() {return deque.isEmpty();}// 获取双端队列的大小public int size() {return deque.size();}
}public class Main {public static void main(String[] args) {MyDeque deque new MyDeque();deque.addFirst(1);deque.addLast(2);deque.addFirst(3);deque.addLast(4);System.out.println(双端队列的大小 deque.size());System.out.println(头部元素 deque.getFirst());System.out.println(尾部元素 deque.getLast());while (!deque.isEmpty()) {System.out.print(deque.removeFirst() );}}
}以上代码演示了如何使用双向链表实现双端队列并对双端队列进行了一些基本操作如插入、删除、获取元素等。双端队列是一种非常实用的数据结构在很多场景下都可以发挥作用例如在树的层序遍历、滑动窗口等算法中。
实现原理解释
双端队列允许在队列的两端进行插入和删除操作因此可以在头部和尾部同时执行入队和出队操作。双端队列的底层实现可以使用链表或者数组。使用链表实现时可以很方便地在头部和尾部执行插入和删除操作但是查询操作的时间复杂度为 O(n)使用数组实现时插入和删除操作的时间复杂度为 O(1)但是需要考虑扩容和缩容的问题。双端队列可以用来实现很多其他数据结构例如栈、队列、优先队列等。因为它同时具有队列和栈的特性可以很方便地进行元素的入栈、出栈、入队、出队操作。
6.哈希表 (Hash Table)
哈希表是一种通过哈希函数将关键字映射到表中的位置来实现快速查找的数据结构。
示例代码实现
import java.util.LinkedList;public class HashTable {private static final int SIZE 10; // 哈希表大小private LinkedListEntry[] table; // 使用链表数组实现哈希表public HashTable() {table new LinkedList[SIZE];for (int i 0; i SIZE; i) {table[i] new LinkedList();}}// 哈希函数将关键字映射到哈希表的索引位置private int hashFunction(int key) {return key % SIZE;}// 插入键值对到哈希表中public void put(int key, int value) {int index hashFunction(key);LinkedListEntry list table[index];for (Entry entry : list) {if (entry.key key) {entry.value value; // 如果关键字已经存在则更新值return;}}list.add(new Entry(key, value)); // 否则添加新的键值对}// 获取键对应的值public int get(int key) {int index hashFunction(key);LinkedListEntry list table[index];for (Entry entry : list) {if (entry.key key) {return entry.value; // 返回对应的值}}throw new IllegalArgumentException(Key not found); // 如果键不存在则抛出异常}// 删除指定键的键值对public void remove(int key) {int index hashFunction(key);LinkedListEntry list table[index];for (Entry entry : list) {if (entry.key key) {list.remove(entry); // 删除对应的键值对return;}}throw new IllegalArgumentException(Key not found); // 如果键不存在则抛出异常}// 内部类表示哈希表中的键值对private static class Entry {int key;int value;public Entry(int key, int value) {this.key key;this.value value;}}
}实现原理解释
哈希表通过哈希函数将关键字映射到表中的位置这个位置通常称为哈希桶。在示例中我们使用简单的取模运算作为哈希函数。为了处理哈希冲突即多个不同的关键字映射到同一个哈希桶的情况我们使用链表来存储具有相同哈希值的键值对。插入键值对时首先计算关键字的哈希值并找到对应的哈希桶然后遍历该哈希桶内的链表如果发现已存在相同的关键字则更新对应的值否则在链表末尾添加新的键值对。获取键值对时同样计算出哈希桶的索引并在对应的链表中查找对应的键值对如果找到则返回其值否则抛出异常表示键不存在。删除键值对时同样需要先找到对应的哈希桶和链表然后遍历链表找到对应的键值对并将其删除。
哈希表是一种高效的数据结构能够在平均情况下实现快速的插入、查找和删除操作但在最坏情况下可能会有较高的时间复杂度。
7.树 (Tree)
树是一种层级结构由节点组成每个节点可以有零个或多个子节点。
示例代码实现
class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val val;this.left null;this.right null;}
}public class BinaryTree {private TreeNode root;public BinaryTree() {this.root null;}// 插入节点public void insert(int val) {root insertRecursive(root, val);}// 递归插入节点private TreeNode insertRecursive(TreeNode root, int val) {if (root null) {return new TreeNode(val);}if (val root.val) {root.left insertRecursive(root.left, val);} else if (val root.val) {root.right insertRecursive(root.right, val);}return root;}
}实现原理解释
树的节点由一个数据元素和指向子节点的引用组成。在示例中我们使用TreeNode类来表示树的节点。树的根节点是树的入口点可以通过它遍历整棵树。在示例中我们通过BinaryTree类来管理树其中的insert方法用于插入新节点。插入节点时首先比较要插入的节点值和当前节点的值如果小于当前节点的值则插入到左子树中如果大于当前节点的值则插入到右子树中。递归地在子树中执行相同的操作直到找到合适的插入位置。
树是一种重要的数据结构有着丰富的应用场景包括二叉搜索树、平衡二叉树、红黑树等。对树的深入理解能够帮助我们更好地解决各种问题。
8.平衡二叉树 (Balanced Binary Tree)
平衡二叉树是一种二叉树它的每个节点的左右子树的高度差不超过1。
示例代码实现
class AVLNode {int val;int height;AVLNode left;AVLNode right;public AVLNode(int val) {this.val val;this.height 1;this.left null;this.right null;}
}public class AVLTree {private AVLNode root;public AVLTree() {this.root null;}// 获取节点的高度private int height(AVLNode node) {if (node null) {return 0;}return node.height;}// 获取节点的平衡因子private int balanceFactor(AVLNode node) {if (node null) {return 0;}return height(node.left) - height(node.right);}// 右旋转private AVLNode rightRotate(AVLNode y) {AVLNode x y.left;AVLNode T2 x.right;x.right y;y.left T2;y.height Math.max(height(y.left), height(y.right)) 1;x.height Math.max(height(x.left), height(x.right)) 1;return x;}// 左旋转private AVLNode leftRotate(AVLNode x) {AVLNode y x.right;AVLNode T2 y.left;y.left x;x.right T2;x.height Math.max(height(x.left), height(x.right)) 1;y.height Math.max(height(y.left), height(y.right)) 1;return y;}// 插入节点public void insert(int val) {root insertRecursive(root, val);}// 递归插入节点private AVLNode insertRecursive(AVLNode root, int val) {if (root null) {return new AVLNode(val);}if (val root.val) {root.left insertRecursive(root.left, val);} else if (val root.val) {root.right insertRecursive(root.right, val);} else {return root; // 重复值不允许插入}root.height 1 Math.max(height(root.left), height(root.right));int balance balanceFactor(root);// 左左情况if (balance 1 val root.left.val) {return rightRotate(root);}// 右右情况if (balance -1 val root.right.val) {return leftRotate(root);}// 左右情况if (balance 1 val root.left.val) {root.left leftRotate(root.left);return rightRotate(root);}// 右左情况if (balance -1 val root.right.val) {root.right rightRotate(root.right);return leftRotate(root);}return root;}
}实现原理解释
平衡二叉树是一种自平衡的二叉搜索树保持了每个节点的左右子树的高度差不超过1的特性。在插入新节点时我们首先按照二叉搜索树的规则找到合适的插入位置。然后我们递归地更新从插入位置到根节点的路径上所有节点的高度并检查它们的平衡因子是否满足平衡条件。如果出现不平衡情况我们通过旋转操作来恢复平衡。左旋转和右旋转是平衡二叉树中最基本的旋转操作通过它们可以将不平衡的子树调整为平衡的状态。在插入新节点后我们递归地检查每个祖先节点的平衡因子如果发现不平衡则执行相应的旋转操作。
9.红黑树 (Red-Black Tree)
红黑树是一种自平衡的二叉搜索树它在每个节点上增加了一个存储位来表示节点的颜色可以是红色或黑色并且满足以下性质
每个节点要么是红色要么是黑色。根节点是黑色的。每个叶子节点NIL节点空节点是黑色的。如果一个节点是红色的则它的两个子节点都是黑色的。对于每个节点从该节点到其所有后代叶子节点的简单路径上均包含相同数目的黑色节点。
红黑树通过这些性质保持了一种平衡保证了插入、删除等操作的时间复杂度为O(log n)。
示例代码实现
class RedBlackTreeNode {int val;boolean isRed;RedBlackTreeNode left;RedBlackTreeNode right;RedBlackTreeNode parent;public RedBlackTreeNode(int val) {this.val val;this.isRed true;this.left null;this.right null;this.parent null;}
}public class RedBlackTree {private RedBlackTreeNode root;public RedBlackTree() {this.root null;}// 插入节点public void insert(int val) {RedBlackTreeNode newNode new RedBlackTreeNode(val);root insertNode(root, newNode);fixViolations(newNode);}// 插入节点的辅助方法private RedBlackTreeNode insertNode(RedBlackTreeNode root, RedBlackTreeNode newNode) {if (root null) {return newNode;}if (newNode.val root.val) {root.left insertNode(root.left, newNode);root.left.parent root;} else if (newNode.val root.val) {root.right insertNode(root.right, newNode);root.right.parent root;}return root;}// 修复违反红黑树性质的情况private void fixViolations(RedBlackTreeNode node) {while (node ! null node ! root node.parent.isRed) {if (node.parent node.parent.parent.left) {RedBlackTreeNode uncle node.parent.parent.right;if (uncle ! null uncle.isRed) {node.parent.isRed false;uncle.isRed false;node.parent.parent.isRed true;node node.parent.parent;} else {if (node node.parent.right) {node node.parent;leftRotate(node);}node.parent.isRed false;node.parent.parent.isRed true;rightRotate(node.parent.parent);}} else {RedBlackTreeNode uncle node.parent.parent.left;if (uncle ! null uncle.isRed) {node.parent.isRed false;uncle.isRed false;node.parent.parent.isRed true;node node.parent.parent;} else {if (node node.parent.left) {node node.parent;rightRotate(node);}node.parent.isRed false;node.parent.parent.isRed true;leftRotate(node.parent.parent);}}}root.isRed false;}// 左旋转操作private void leftRotate(RedBlackTreeNode node) {RedBlackTreeNode rightChild node.right;node.right rightChild.left;if (rightChild.left ! null) {rightChild.left.parent node;}rightChild.parent node.parent;if (node.parent null) {root rightChild;} else if (node node.parent.left) {node.parent.left rightChild;} else {node.parent.right rightChild;}rightChild.left node;node.parent rightChild;}// 右旋转操作private void rightRotate(RedBlackTreeNode node) {RedBlackTreeNode leftChild node.left;node.left leftChild.right;if (leftChild.right ! null) {leftChild.right.parent node;}leftChild.parent node.parent;if (node.parent null) {root leftChild;} else if (node node.parent.right) {node.parent.right leftChild;} else {node.parent.left leftChild;}leftChild.right node;node.parent leftChild;}
}实现原理解释
红黑树通过左旋转和右旋转等操作来保持树的平衡。左旋转将一个节点上升到其右子节点的位置而右旋转将一个节点上升到其左子节点的位置。当插入一个新节点后可能会破坏红黑树的性质例如父节点和叔节点都为红色此时需要通过颜色调整和旋转来恢复平衡。插入新节点后我们沿着插入路径向上检查如果当前节点的父节点和叔节点都为红色则需要进行颜色调整否则如果当前节点的父节点为红色而叔节点为黑色则需要进行旋转操作。通过适当的旋转和颜色调整我们可以保持红黑树的平衡性质从而确保其高效的插入、删除和搜索操作的时间复杂度为O(log n)。
10.堆 (Heap)
堆是一种特殊的树形数据结构其中每个节点的值都必须大于或等于最大堆或小于或等于最小堆其子节点的值。
示例代码实现
以下是最小堆的示例代码实现
public class MinHeap {private int[] heap;private int size;private int capacity;public MinHeap(int capacity) {this.capacity capacity;this.size 0;this.heap new int[capacity];}// 获取父节点索引private int parent(int i) {return (i - 1) / 2;}// 获取左子节点索引private int leftChild(int i) {return 2 * i 1;}// 获取右子节点索引private int rightChild(int i) {return 2 * i 2;}// 插入元素public void insert(int value) {if (size capacity) {throw new IllegalStateException(Heap is full);}size;int i size - 1;heap[i] value;// 保持堆的性质while (i ! 0 heap[parent(i)] heap[i]) {swap(i, parent(i));i parent(i);}}// 交换堆中两个元素private void swap(int i, int j) {int temp heap[i];heap[i] heap[j];heap[j] temp;}// 从堆中删除最小元素public int extractMin() {if (size 0) {throw new IllegalStateException(Heap is empty);}if (size 1) {size--;return heap[0];}int root heap[0];heap[0] heap[size - 1];size--;minHeapify(0);return root;}// 保持最小堆性质private void minHeapify(int i) {int left leftChild(i);int right rightChild(i);int smallest i;if (left size heap[left] heap[i]) {smallest left;}if (right size heap[right] heap[smallest]) {smallest right;}if (smallest ! i) {swap(i, smallest);minHeapify(smallest);}}// 获取堆中最小元素public int getMin() {if (size 0) {throw new IllegalStateException(Heap is empty);}return heap[0];}
}实现原理解释
堆通常用数组来实现数组的每个元素对应堆的一个节点。在最小堆中父节点的值始终小于或等于其子节点的值。插入操作保持堆的性质将新元素插入到堆的末尾然后通过上移操作向上比较交换来确保新元素满足堆的性质。删除最小元素操作通常是堆顶元素将堆顶元素移动到末尾然后通过下移操作向下比较交换来确保堆的性质。获取最小元素操作返回堆顶元素即可。在最大堆中父节点的值始终大于或等于其子节点的值操作类似于最小堆只是比较的方式相反。
堆是一种非常重要的数据结构常用于实现优先队列等应用场景能够快速地获取最大或最小元素。
11.图 (Graph)
图是由节点顶点和连接这些节点的边组成的一种数据结构。图可以用于表示各种实际问题中的关系和网络。
示例代码实现
以下是使用邻接表实现的无向图的示例代码
import java.util.*;public class Graph {private int V; // 图中顶点的数量private LinkedListInteger[] adj; // 邻接表表示图的结构public Graph(int V) {this.V V;adj new LinkedList[V];for (int i 0; i V; i)adj[i] new LinkedList();}// 添加边无向图的边是双向的public void addEdge(int v, int w) {adj[v].add(w);adj[w].add(v);}// 深度优先搜索遍历图public void DFS(int v) {boolean[] visited new boolean[V];DFSUtil(v, visited);}private void DFSUtil(int v, boolean[] visited) {visited[v] true;System.out.print(v );for (int n : adj[v]) {if (!visited[n]) {DFSUtil(n, visited);}}}// 广度优先搜索遍历图public void BFS(int v) {boolean[] visited new boolean[V];QueueInteger queue new LinkedList();visited[v] true;queue.add(v);while (!queue.isEmpty()) {int current queue.poll();System.out.print(current );for (int n : adj[current]) {if (!visited[n]) {visited[n] true;queue.add(n);}}}}
}实现原理解释
图的表示方式有多种其中一种常见的方式是邻接表。在示例代码中我们使用了邻接表来表示无向图的结构。在邻接表中对于每个顶点我们都维护一个与之相邻的顶点列表。在示例中我们使用LinkedList数组来表示每个顶点的邻接列表。添加边的操作是双向的因为无向图中的边是双向的所以在添加边时需要同时更新两个顶点的邻接列表。深度优先搜索DFS和广度优先搜索BFS是图的常见遍历算法。DFS通过递归或栈来实现它会沿着图的深度尽可能远地搜索。而BFS通过队列来实现它会逐层遍历图。在示例代码中我们实现了DFS和BFS的遍历算法。
图是一种十分灵活的数据结构能够很好地表示各种实际问题中的关系和网络。深入理解图的遍历算法和性质对于解决各种问题至关重要。
12.字典树 (Trie)
字典树也称为前缀树或单词查找树是一种用于存储关联数组的树形数据结构。它是一种哈希树的变种通常用于高效地检索大量的字符串数据集中的键值。
示例代码实现
以下是字典树的示例代码实现
class TrieNode {TrieNode[] children;boolean isEnd;public TrieNode() {children new TrieNode[26]; // 假设只包含小写字母isEnd false;}
}public class Trie {private TrieNode root;public Trie() {root new TrieNode();}// 向字典树中插入单词public void insert(String word) {TrieNode node root;for (char ch : word.toCharArray()) {int index ch - a;if (node.children[index] null) {node.children[index] new TrieNode();}node node.children[index];}node.isEnd true; // 标记单词结束}// 在字典树中搜索单词public boolean search(String word) {TrieNode node root;for (char ch : word.toCharArray()) {int index ch - a;if (node.children[index] null) {return false;}node node.children[index];}return node ! null node.isEnd; // 检查单词是否结束}// 判断是否存在以指定前缀开头的单词public boolean startsWith(String prefix) {TrieNode node root;for (char ch : prefix.toCharArray()) {int index ch - a;if (node.children[index] null) {return false;}node node.children[index];}return node ! null; // 只需判断是否存在前缀不需要检查是否为完整单词}
}实现原理解释
字典树的节点由一个存储当前字符的数组和一个标记是否是单词结束的布尔变量组成。在示例中我们使用TrieNode类来表示字典树的节点。插入操作将单词中的每个字符按顺序插入到字典树中。对于每个字符如果该字符对应的子节点不存在则创建新的子节点否则移动到下一个子节点。在单词的最后一个字符处将isEnd标记为true表示这是一个完整的单词。搜索操作从根节点开始按照单词中的字符顺序遍历字典树。如果在遍历过程中遇到了空子节点则说明字典树中不包含该单词。如果遍历完所有字符后当前节点的isEnd标记为true则说明该单词存在于字典树中。前缀搜索操作与搜索操作类似只是在搜索过程中不需要检查isEnd标记因为只需要判断是否存在以指定前缀开头的单词不需要完整的单词。
字典树是一种高效的数据结构常用于搜索引擎、拼写检查、自动完成等应用场景中。
13.哈希集合 (HashSet)
哈希集合是一种集合数据结构它基于哈希表实现能够提供快速的插入、删除和查找操作。
示例代码实现
以下是使用哈希表实现的简单哈希集合的示例代码
import java.util.*;public class MyHashSet {private static final int BASE 769;private ListInteger[] buckets;public MyHashSet() {buckets new LinkedList[BASE];for (int i 0; i BASE; i) {buckets[i] new LinkedList();}}// 哈希函数private int hash(int key) {return key % BASE;}// 向集合中插入元素public void add(int key) {int hashKey hash(key);if (!contains(key)) {buckets[hashKey].add(key);}}// 从集合中删除元素public void remove(int key) {int hashKey hash(key);buckets[hashKey].remove(Integer.valueOf(key));}// 检查集合中是否包含元素public boolean contains(int key) {int hashKey hash(key);return buckets[hashKey].contains(key);}
}实现原理解释
哈希集合基于哈希表实现其中哈希函数将键映射到哈希表中的索引位置。在示例中我们使用一个数组来表示哈希表每个数组元素是一个链表用于解决哈希冲突。插入操作首先计算键的哈希值然后将键添加到对应索引处的链表中。在添加之前通常需要检查该键是否已经存在于集合中。删除操作同样需要计算键的哈希值然后在对应索引处的链表中查找并删除该键。查找操作通过计算键的哈希值找到对应索引处的链表然后在链表中查找该键是否存在。
哈希集合是一种高效的数据结构能够在平均情况下提供快速的插入、删除和查找操作。
14.队列 (Queue)
队列是一种先进先出FIFO的数据结构类似于排队。在队列中新元素在队尾添加而从队列中移除元素则发生在队列头部。
示例代码实现
以下是使用链表实现的队列的示例代码
import java.util.*;public class QueueExample {private LinkedListInteger queue;public QueueExample() {queue new LinkedList();}// 入队操作public void enqueue(int item) {queue.addLast(item);}// 出队操作public int dequeue() {if (isEmpty()) {throw new NoSuchElementException(Queue is empty);}return queue.removeFirst();}// 获取队头元素public int peek() {if (isEmpty()) {throw new NoSuchElementException(Queue is empty);}return queue.getFirst();}// 检查队列是否为空public boolean isEmpty() {return queue.isEmpty();}// 获取队列中元素个数public int size() {return queue.size();}
}实现原理解释
队列通常使用链表或数组来实现。在示例中我们使用Java中的LinkedList来实现队列。入队操作将新元素添加到链表的末尾因为队列是先进先出的所以新元素会排在队列的尾部。出队操作从链表的头部移除元素因为队列中的第一个元素最先进入所以需要从队列的头部移除元素。获取队头元素返回链表的头部元素但不移除它。检查队列是否为空判断链表是否为空。获取队列中元素个数返回链表的大小即队列中元素的个数。
队列是一种常见的数据结构在许多应用场景中都有广泛的应用例如任务调度、消息队列、广度优先搜索等算法。
15.栈 (Stack)
栈是一种后进先出LIFO的数据结构类似于一叠盘子。在栈中新元素在顶部添加而移除元素也发生在顶部。
示例代码实现
以下是使用链表实现的栈的示例代码
import java.util.*;public class StackExample {private LinkedListInteger stack;public StackExample() {stack new LinkedList();}// 入栈操作public void push(int item) {stack.addLast(item);}// 出栈操作public int pop() {if (isEmpty()) {throw new EmptyStackException();}return stack.removeLast();}// 获取栈顶元素public int peek() {if (isEmpty()) {throw new EmptyStackException();}return stack.getLast();}// 检查栈是否为空public boolean isEmpty() {return stack.isEmpty();}// 获取栈中元素个数public int size() {return stack.size();}
}实现原理解释
栈通常使用链表或数组来实现。在示例中我们使用Java中的LinkedList来实现栈。入栈操作将新元素添加到链表的末尾因为栈是后进先出的所以新元素会被添加到栈的顶部。出栈操作从链表的末尾移除元素因为栈中的最后一个元素最后进入所以需要从栈的顶部移除元素。获取栈顶元素返回链表的末尾元素但不移除它。检查栈是否为空判断链表是否为空。获取栈中元素个数返回链表的大小即栈中元素的个数。
栈是一种常见的数据结构在计算机科学中有着广泛的应用例如函数调用、表达式求值、深度优先搜索等算法。
16.哈希表 (HashMap)
哈希表是一种常见的数据结构用于存储键值对。它通过哈希函数将键映射到哈希表中的索引位置从而实现快速的插入、删除和查找操作。
示例代码实现
以下是使用拉链法解决冲突的哈希表的示例代码
import java.util.*;class EntryK, V {K key;V value;EntryK, V next;public Entry(K key, V value) {this.key key;this.value value;this.next null;}
}public class MyHashMapK, V {private static final int DEFAULT_CAPACITY 16;private static final double LOAD_FACTOR_THRESHOLD 0.75;private EntryK, V[] buckets;private int size;public MyHashMap() {buckets new Entry[DEFAULT_CAPACITY];size 0;}// 哈希函数private int hash(K key) {return Objects.hashCode(key) % buckets.length;}// 插入键值对public void put(K key, V value) {int index hash(key);if (buckets[index] null) {buckets[index] new Entry(key, value);} else {EntryK, V current buckets[index];while (current ! null) {if (Objects.equals(current.key, key)) {current.value value;return;}if (current.next null) {current.next new Entry(key, value);break;}current current.next;}}size;if ((double)size / buckets.length LOAD_FACTOR_THRESHOLD) {resize();}}// 获取键对应的值public V get(K key) {int index hash(key);EntryK, V current buckets[index];while (current ! null) {if (Objects.equals(current.key, key)) {return current.value;}current current.next;}return null;}// 删除键值对public void remove(K key) {int index hash(key);EntryK, V prev null;EntryK, V current buckets[index];while (current ! null) {if (Objects.equals(current.key, key)) {if (prev null) {buckets[index] current.next;} else {prev.next current.next;}size--;return;}prev current;current current.next;}}// 哈希表是否为空public boolean isEmpty() {return size 0;}// 哈希表的大小public int size() {return size;}// 哈希表扩容private void resize() {EntryK, V[] oldBuckets buckets;buckets new Entry[buckets.length * 2];size 0;for (EntryK, V entry : oldBuckets) {while (entry ! null) {put(entry.key, entry.value);entry entry.next;}}}
}实现原理解释
哈希表通过哈希函数将键映射到哈希表中的索引位置。在示例中我们使用对象的hashCode()方法来生成哈希值。解决冲突当两个不同的键映射到同一个索引位置时会发生冲突。在示例中我们使用拉链法Chaining来解决冲突即将具有相同哈希值的键值对存储在同一个索引位置的链表中。插入操作首先计算键的哈希值然后将键值对插入到对应索引处的链表中。如果已存在相同的键则更新对应的值。获取操作通过哈希函数找到键对应的索引位置然后在对应索引处的链表中查找键对应的值。删除操作类似于获取操作找到键对应的索引位置然后在对应索引处的链表中删除键值对。扩容操作当哈希表的负载因子键值对数量与数组长度的比值超过阈值时会触发扩容操作。扩容后哈希表的大小会变为原来的两倍并重新计算每个键值对的哈希值然后重新插入到扩容后的哈希表中。
哈希表是一种非常常用且高效的数据结构可以在平均情况下提供O(1)的插入、删除和查找操作。在实际应用中哈希表被广泛用于实现各种数据结构如哈希集合、哈希映射等。
17.优先队列 (Priority Queue)
优先队列是一种特殊的队列它允许在插入元素时赋予每个元素一个优先级并且每次出队操作都会返回具有最高优先级的元素。
示例代码实现
以下是使用堆实现的优先队列的示例代码
import java.util.*;public class PriorityQueueExampleT extends ComparableT {private ListT heap;public PriorityQueueExample() {heap new ArrayList();}// 入队操作public void enqueue(T item) {heap.add(item);siftUp(heap.size() - 1);}// 出队操作public T dequeue() {if (isEmpty()) {throw new NoSuchElementException(Priority queue is empty);}T max heap.get(0);int last heap.size() - 1;heap.set(0, heap.get(last));heap.remove(last);siftDown(0);return max;}// 获取队列中优先级最高的元素public T peek() {if (isEmpty()) {throw new NoSuchElementException(Priority queue is empty);}return heap.get(0);}// 检查队列是否为空public boolean isEmpty() {return heap.isEmpty();}// 获取队列中元素个数public int size() {return heap.size();}// 上移操作保持堆的性质private void siftUp(int i) {while (i 0) {int parent (i - 1) / 2;if (heap.get(i).compareTo(heap.get(parent)) 0) {break;}swap(i, parent);i parent;}}// 下移操作保持堆的性质private void siftDown(int i) {int size heap.size();while (i size) {int left 2 * i 1;int right 2 * i 2;int max i;if (left size heap.get(left).compareTo(heap.get(max)) 0) {max left;}if (right size heap.get(right).compareTo(heap.get(max)) 0) {max right;}if (max i) {break;}swap(i, max);i max;}}// 交换元素位置private void swap(int i, int j) {T temp heap.get(i);heap.set(i, heap.get(j));heap.set(j, temp);}
}实现原理解释
优先队列通常使用堆来实现堆是一种特殊的树形数据结构满足堆的性质例如最大堆或最小堆。入队操作将新元素插入到堆的末尾然后通过上移操作向上比较交换来确保新元素满足堆的性质。出队操作删除堆顶元素然后将堆的末尾元素移动到堆顶并通过下移操作向下比较交换来确保堆的性质。获取优先级最高的元素操作返回堆顶元素。优先队列可以用于实现诸如任务调度、事件驱动等应用场景其中需要根据某种优先级来决定下一步的操作。
18.AVL 树
AVL 树是一种自平衡二叉搜索树它保持了二叉搜索树的特性并且在插入或删除节点时通过旋转操作来保持树的平衡使得树的高度始终保持在较小的范围内从而提高了搜索、插入和删除操作的效率。
示例代码实现
以下是 AVL 树的简单实现示例
class TreeNode {int val;TreeNode left;TreeNode right;int height;public TreeNode(int val) {this.val val;this.height 1;}
}public class AVLTree {private TreeNode root;// 获取树的高度private int height(TreeNode node) {if (node null) {return 0;}return node.height;}// 获取节点的平衡因子private int balanceFactor(TreeNode node) {if (node null) {return 0;}return height(node.left) - height(node.right);}// 更新节点的高度private void updateHeight(TreeNode node) {node.height Math.max(height(node.left), height(node.right)) 1;}// 右旋操作private TreeNode rightRotate(TreeNode y) {TreeNode x y.left;TreeNode T x.right;x.right y;y.left T;updateHeight(y);updateHeight(x);return x;}// 左旋操作private TreeNode leftRotate(TreeNode x) {TreeNode y x.right;TreeNode T y.left;y.left x;x.right T;updateHeight(x);updateHeight(y);return y;}// 插入节点public TreeNode insert(TreeNode node, int val) {if (node null) {return new TreeNode(val);}if (val node.val) {node.left insert(node.left, val);} else if (val node.val) {node.right insert(node.right, val);} else {// 重复值不处理return node;}updateHeight(node);int balance balanceFactor(node);// 左子树不平衡if (balance 1 val node.left.val) {return rightRotate(node);}// 右子树不平衡if (balance -1 val node.right.val) {return leftRotate(node);}// 左右情况先左旋再右旋if (balance 1 val node.left.val) {node.left leftRotate(node.left);return rightRotate(node);}// 右左情况先右旋再左旋if (balance -1 val node.right.val) {node.right rightRotate(node.right);return leftRotate(node);}return node;}
}实现原理解释
AVL 树通过维护每个节点的平衡因子来保持树的平衡平衡因子定义为节点的左子树高度和右子树高度的差。当插入或删除节点导致树失去平衡时需要通过旋转操作来恢复平衡。根据失衡的情况可以进行四种旋转操作左旋、右旋、左右旋、右左旋。在 AVL 树中每个节点的平衡因子必须为 -1、0 或 1。如果某个节点的平衡因子不在这个范围内则需要进行相应的旋转操作来调整树的结构以恢复平衡。插入节点时需要递归地将节点插入到正确的位置并在递归回溯过程中更新节点的高度和检查平衡因子。如果插入后导致树失去平衡则进行相应的旋转操作来恢复平衡。
AVL 树是一种高效的自平衡二叉搜索树能够保持较低的平均搜索时间。在需要高效地进行搜索、插入和删除操作的场景中AVL 树是一种非常有用的数据结构。
19.红黑树 (Red-Black Tree)
红黑树是一种自平衡的二叉搜索树它保持了二叉搜索树的特性并且通过对节点着色和旋转操作来保持树的平衡从而确保了树的高度始终保持在对数范围内提高了搜索、插入和删除操作的效率。
示例代码实现
以下是红黑树的简单实现示例
enum Color {RED, BLACK
}class TreeNode {int val;TreeNode left;TreeNode right;Color color;public TreeNode(int val) {this.val val;this.color Color.RED; // 默认新插入节点为红色}
}public class RedBlackTree {private TreeNode root;// 左旋操作private TreeNode leftRotate(TreeNode node) {TreeNode rightChild node.right;node.right rightChild.left;rightChild.left node;rightChild.color node.color;node.color Color.RED;return rightChild;}// 右旋操作private TreeNode rightRotate(TreeNode node) {TreeNode leftChild node.left;node.left leftChild.right;leftChild.right node;leftChild.color node.color;node.color Color.RED;return leftChild;}// 颜色翻转private void flipColors(TreeNode node) {node.color Color.RED;node.left.color Color.BLACK;node.right.color Color.BLACK;}// 检查节点是否为红色private boolean isRed(TreeNode node) {return node ! null node.color Color.RED;}// 插入节点public void insert(int val) {root insert(root, val);root.color Color.BLACK; // 根节点始终为黑色}private TreeNode insert(TreeNode node, int val) {if (node null) {return new TreeNode(val);}if (val node.val) {node.left insert(node.left, val);} else if (val node.val) {node.right insert(node.right, val);}// 调整树结构保持红黑树的特性if (isRed(node.right) !isRed(node.left)) {node leftRotate(node);}if (isRed(node.left) isRed(node.left.left)) {node rightRotate(node);}if (isRed(node.left) isRed(node.right)) {flipColors(node);}return node;}
}实现原理解释
红黑树通过对节点着色红色或黑色和旋转操作来保持树的平衡。红黑树的每个节点具有颜色属性可以是红色或黑色。根据红黑树的性质根节点和叶子节点NIL 节点必须为黑色红色节点的子节点必须为黑色。插入操作时首先将新插入的节点着为红色然后根据不同的情况进行旋转和颜色调整操作以保持红黑树的特性。插入节点后通过旋转和颜色调整操作保持了树的平衡性并且树的高度始终保持在对数范围内从而提高了搜索、插入和删除操作的效率。
红黑树是一种高效的自平衡二叉搜索树常用于实现各种高级数据结构和算法如Java中的TreeMap和TreeSet。
20. B树 (B-Tree)
B 树是一种多路搜索树它具有以下特点每个节点可以包含多个子节点每个节点中的键值按顺序排列并且对应的子树范围也按顺序排列。B 树通常用于数据库和文件系统等需要大量数据存储和高效检索的场景。
示例代码实现
B 树的实现相对复杂以下是简化版本的示例代码
class BTreeNode {int[] keys;int numKeys;BTreeNode[] children;boolean leaf;public BTreeNode(int t, boolean leaf) {this.keys new int[2 * t - 1];this.children new BTreeNode[2 * t];this.numKeys 0;this.leaf leaf;}
}public class BTree {private BTreeNode root;private int t; // B 树的度public BTree(int t) {this.root null;this.t t;}// 在 B 树中搜索给定的键public boolean search(int key) {return search(root, key);}private boolean search(BTreeNode node, int key) {int i 0;while (i node.numKeys key node.keys[i]) {i;}if (i node.numKeys key node.keys[i]) {return true;}if (node.leaf) {return false;}return search(node.children[i], key);}// 在 B 树中插入键public void insert(int key) {if (root null) {root new BTreeNode(t, true);root.keys[0] key;root.numKeys 1;} else {if (root.numKeys 2 * t - 1) {BTreeNode newRoot new BTreeNode(t, false);newRoot.children[0] root;splitChild(newRoot, 0);root newRoot;}insertNonFull(root, key);}}private void insertNonFull(BTreeNode node, int key) {int i node.numKeys - 1;if (node.leaf) {while (i 0 key node.keys[i]) {node.keys[i 1] node.keys[i];i--;}node.keys[i 1] key;node.numKeys;} else {while (i 0 key node.keys[i]) {i--;}i;if (node.children[i].numKeys 2 * t - 1) {splitChild(node, i);if (key node.keys[i]) {i;}}insertNonFull(node.children[i], key);}}private void splitChild(BTreeNode parentNode, int childIndex) {BTreeNode childNode parentNode.children[childIndex];BTreeNode newChildNode new BTreeNode(t, childNode.leaf);newChildNode.numKeys t - 1;for (int j 0; j t - 1; j) {newChildNode.keys[j] childNode.keys[j t];}if (!childNode.leaf) {for (int j 0; j t; j) {newChildNode.children[j] childNode.children[j t];}}childNode.numKeys t - 1;for (int j parentNode.numKeys; j childIndex 1; j--) {parentNode.children[j 1] parentNode.children[j];}parentNode.children[childIndex 1] newChildNode;for (int j parentNode.numKeys - 1; j childIndex; j--) {parentNode.keys[j 1] parentNode.keys[j];}parentNode.keys[childIndex] childNode.keys[t - 1];parentNode.numKeys;}
}实现原理解释
B 树是一种平衡的多路搜索树每个节点可以包含多个子节点。节点中的键值按顺序排列并且对应的子树范围也按顺序排列。B 树的度degree定义为每个节点中子节点的最小数量通常用 t 来表示。根据度的大小B 树可以是 2-3 树、2-3-4 树等。插入操作时首先搜索到合适的叶子节点并在叶子节点中插入新的键值。如果插入后导致节点的键值数量超过了阈值则进行节点分裂操作。节点分裂操作将节点一分为二并将中间的键值提升到父节点。如果父节点的键值数量超过了阈值则递归进行分裂操作。B 树具有平衡性可以保持较低的高度并且可以实现高效的搜索、插入和删除操作。在需要大量数据存储和高效检索的场景中B 树是一种非常有用的数据结构。
21.Trie 树
Trie 树字典树是一种树形数据结构用于高效地存储和检索字符串集合。它的特点是每个节点都代表一个字符串的前缀从根节点到每个节点的路径构成一个字符串。
示例代码实现
以下是 Trie 树的简单实现示例
class TrieNode {TrieNode[] children;boolean isEnd;public TrieNode() {children new TrieNode[26]; // 假设只包含小写字母isEnd false;}
}public class Trie {private TrieNode root;public Trie() {root new TrieNode();}// 插入单词public void insert(String word) {TrieNode node root;for (char c : word.toCharArray()) {int index c - a;if (node.children[index] null) {node.children[index] new TrieNode();}node node.children[index];}node.isEnd true;}// 搜索单词public boolean search(String word) {TrieNode node searchPrefix(word);return node ! null node.isEnd;}// 搜索前缀public boolean startsWith(String prefix) {return searchPrefix(prefix) ! null;}private TrieNode searchPrefix(String prefix) {TrieNode node root;for (char c : prefix.toCharArray()) {int index c - a;if (node.children[index] null) {return null;}node node.children[index];}return node;}
}实现原理解释
Trie 树是一种树形数据结构每个节点代表一个字符串的前缀。根节点代表空字符串每个节点的子节点代表该节点对应的字符串后面添加一个字符后得到的新前缀。Trie 树的每个节点包含一个数组数组的大小通常为字符集大小例如ASCII码中的26个小写字母数组中的每个元素对应一个可能的字符表示该字符在当前节点的子节点中是否存在。插入操作时从根节点开始逐个遍历待插入字符串的字符根据字符找到对应的子节点并创建新节点如果子节点不存在。在插入完成后标记最后一个节点为单词结束节点。搜索操作时从根节点开始逐个遍历待搜索字符串的字符根据字符找到对应的子节点如果子节点不存在则表示字符串不存在于 Trie 树中。Trie 树的时间复杂度取决于字符串的长度对于每个操作插入、搜索、删除时间复杂度均为 O(m)其中 m 表示字符串的长度。Trie 树可以实现高效的字符串存储和检索。
22.Bloom Filter
Bloom Filter布隆过滤器是一种高效的数据结构用于判断一个元素是否属于一个集合。它可以快速地告诉你一个元素不在集合中或者可能在集合中。
示例代码实现
以下是 Bloom Filter 的简单实现示例
import java.util.BitSet;public class BloomFilter {private BitSet bitSet;private int size;private int[] hashFunctions;public BloomFilter(int size, int numHashFunctions) {this.bitSet new BitSet(size);this.size size;this.hashFunctions new int[numHashFunctions];}// 添加元素public void add(String element) {for (int i 0; i hashFunctions.length; i) {int hash hash(element, i);bitSet.set(hash);}}// 查询元素是否可能存在public boolean contains(String element) {for (int i 0; i hashFunctions.length; i) {int hash hash(element, i);if (!bitSet.get(hash)) {return false;}}return true;}// 哈希函数private int hash(String element, int index) {// 实际应用中通常采用多种哈希函数这里简化为使用字符串的哈希码return (element.hashCode() index) % size;}
}实现原理解释
Bloom Filter 的实现原理比较简单基本思想是使用多个哈希函数来表示一个元素在集合中的存在情况。Bloom Filter 主要有两个基本操作插入元素和查询元素。
插入元素将要插入的元素经过多个哈希函数计算得到多个哈希值并将对应的位数组中的位置设为1。查询元素对于查询元素同样经过多个哈希函数计算得到多个哈希值并检查对应的位数组中的位置是否都为1。如果有任何一位为0则可以确定该元素一定不在集合中如果所有位都为1则该元素可能在集合中但也有可能是误判。
由于 Bloom Filter 只是用来判断一个元素可能存在于一个集合中因此在查询结果为存在时还需要进一步验证。Bloom Filter 是一种空间效率和时间效率都较高的数据结构适用于需要快速判断元素是否可能存在于集合中的场景但不适用于需要100%准确性的场景。
在实际应用中可以使用更复杂的哈希函数并根据实际情况选择合适的位数组大小和哈希函数数量以平衡空间占用和查询性能。Bloom Filter 主要用于缓存、数据库查询优化等场景能够显著降低查询时间和存储空间的开销。
最后
好了以上是 V 哥整理的22个数据结构的案列实现和原理解释V 哥建议数据结构一定要理解原理和实现逻辑代码实现不一定是一样的只要满足原理即可最近遇到有参加 OD 面试的机考是必须开着摄像头共享屏幕现写代码考的就是数据结构这类题然后技术面试依然是数据结构算法题即问即答想要通过面试收藏起来慢慢学习吧。关注威哥爱编程一起成长。
