数据结构详解
2415字约8分钟
数据结构算法计算机基础编程基础
2025-07-16
什么是数据结构
数据结构是计算机存储、组织数据的方式,它描述了数据元素之间的逻辑关系。好的数据结构设计可以提高算法的效率,是编程的基础。
主要分类
- 线性结构:数组、链表、栈、队列
- 树形结构:二叉树、AVL树、红黑树、B树
- 图形结构:图、邻接矩阵、邻接表
- 散列结构:HashMap、HashSet、布隆过滤器
线性结构
1. 数组(Array)
基本概念
- 连续的内存空间
- 通过索引访问元素
- 固定长度(Java中可变)
Java实现
public class ArrayDemo {
public static void main(String[] args) {
// 一维数组
int[] numbers = {1, 2, 3, 4, 5};
// 二维数组
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// 动态数组
ArrayList<Integer> dynamicArray = new ArrayList<>();
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
// 数组操作
System.out.println("数组长度: " + numbers.length);
System.out.println("第一个元素: " + numbers[0]);
System.out.println("最后一个元素: " + numbers[numbers.length - 1]);
}
}时间复杂度
- 访问:O(1)
- 查找:O(n)
- 插入:O(n)
- 删除:O(n)
2. 链表(Linked List)
基本概念
- 节点通过指针连接
- 不连续的内存空间
- 支持动态增删
Java实现
// 链表节点
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
// 单链表
public class LinkedList {
private ListNode head;
private int size;
public LinkedList() {
this.head = null;
this.size = 0;
}
// 在头部插入
public void addFirst(int val) {
ListNode newNode = new ListNode(val);
newNode.next = head;
head = newNode;
size++;
}
// 在尾部插入
public void addLast(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);
}
size++;
}
// 删除指定值
public boolean remove(int val) {
if (head == null) return false;
if (head.val == val) {
head = head.next;
size--;
return true;
}
ListNode current = head;
while (current.next != null) {
if (current.next.val == val) {
current.next = current.next.next;
size--;
return true;
}
current = current.next;
}
return false;
}
// 查找元素
public boolean contains(int val) {
ListNode current = head;
while (current != null) {
if (current.val == val) {
return true;
}
current = current.next;
}
return false;
}
// 获取大小
public int size() {
return size;
}
// 打印链表
public void print() {
ListNode current = head;
while (current != null) {
System.out.print(current.val + " -> ");
current = current.next;
}
System.out.println("null");
}
}时间复杂度
- 访问:O(n)
- 查找:O(n)
- 插入:O(1)(头部)/ O(n)(尾部)
- 删除:O(1)(头部)/ O(n)(尾部)
3. 栈(Stack)
基本概念
- 后进先出(LIFO)
- 只能在一端操作
- 常用于函数调用、表达式求值
Java实现
public class Stack<T> {
private ArrayList<T> elements;
public Stack() {
this.elements = new ArrayList<>();
}
// 入栈
public void push(T element) {
elements.add(element);
}
// 出栈
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return elements.remove(elements.size() - 1);
}
// 查看栈顶
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return elements.get(elements.size() - 1);
}
// 判断是否为空
public boolean isEmpty() {
return elements.isEmpty();
}
// 获取大小
public int size() {
return elements.size();
}
}
// 使用示例
public class StackDemo {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
// 入栈
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈大小: " + stack.size());
System.out.println("栈顶元素: " + stack.peek());
// 出栈
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
System.out.println();
}
}时间复杂度
- 入栈:O(1)
- 出栈:O(1)
- 查看栈顶:O(1)
4. 队列(Queue)
基本概念
- 先进先出(FIFO)
- 一端入队,另一端出队
- 常用于广度优先搜索、任务调度
Java实现
public class Queue<T> {
private ArrayList<T> elements;
public Queue() {
this.elements = new ArrayList<>();
}
// 入队
public void enqueue(T element) {
elements.add(element);
}
// 出队
public T dequeue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return elements.remove(0);
}
// 查看队首
public T peek() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return elements.get(0);
}
// 判断是否为空
public boolean isEmpty() {
return elements.isEmpty();
}
// 获取大小
public int size() {
return elements.size();
}
}
// 使用示例
public class QueueDemo {
public static void main(String[] args) {
Queue<String> queue = new Queue<>();
// 入队
queue.enqueue("任务1");
queue.enqueue("任务2");
queue.enqueue("任务3");
System.out.println("队列大小: " + queue.size());
System.out.println("队首任务: " + queue.peek());
// 出队
while (!queue.isEmpty()) {
System.out.println("处理任务: " + queue.dequeue());
}
}
}时间复杂度
- 入队:O(1)
- 出队:O(n)(需要移动元素)
- 查看队首:O(1)
树形结构
1. 二叉树(Binary Tree)
基本概念
- 每个节点最多有两个子节点
- 左子树和右子树
- 常用于搜索和排序
Java实现
// 二叉树节点
class TreeNode {
int val;
TreeNode left;
TreeNode right;
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 = insertRec(root, val);
}
private TreeNode insertRec(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertRec(root.left, val);
} else if (val > root.val) {
root.right = insertRec(root.right, val);
}
return root;
}
// 中序遍历
public void inorderTraversal() {
inorderRec(root);
}
private void inorderRec(TreeNode root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.val + " ");
inorderRec(root.right);
}
}
// 前序遍历
public void preorderTraversal() {
preorderRec(root);
}
private void preorderRec(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preorderRec(root.left);
preorderRec(root.right);
}
}
// 后序遍历
public void postorderTraversal() {
postorderRec(root);
}
private void postorderRec(TreeNode root) {
if (root != null) {
postorderRec(root.left);
postorderRec(root.right);
System.out.print(root.val + " ");
}
}
// 层序遍历
public void levelOrderTraversal() {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.val + " ");
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
}
// 查找节点
public boolean search(int val) {
return searchRec(root, val);
}
private boolean searchRec(TreeNode root, int val) {
if (root == null || root.val == val) {
return root != null;
}
if (val < root.val) {
return searchRec(root.left, val);
}
return searchRec(root.right, val);
}
}时间复杂度
- 查找:O(log n)(平衡树)/ O(n)(不平衡树)
- 插入:O(log n)(平衡树)/ O(n)(不平衡树)
- 删除:O(log n)(平衡树)/ O(n)(不平衡树)
2. 平衡二叉树(AVL Tree)
基本概念
- 自平衡的二叉搜索树
- 左右子树高度差不超过1
- 通过旋转操作保持平衡
Java实现
class AVLNode {
int val;
AVLNode left;
AVLNode right;
int height;
AVLNode(int val) {
this.val = val;
this.left = null;
this.right = null;
this.height = 1;
}
}
public class AVLTree {
private AVLNode root;
// 获取节点高度
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
// 获取平衡因子
private int getBalance(AVLNode node) {
return node == null ? 0 : 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 = insertRec(root, val);
}
private AVLNode insertRec(AVLNode node, int val) {
if (node == null) {
return new AVLNode(val);
}
if (val < node.val) {
node.left = insertRec(node.left, val);
} else if (val > node.val) {
node.right = insertRec(node.right, val);
} else {
return node; // 重复值
}
// 更新高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
// 获取平衡因子
int balance = getBalance(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;
}
}图形结构
1. 图(Graph)
基本概念
- 由顶点和边组成
- 有向图和无向图
- 常用于网络、社交关系建模
Java实现
import java.util.*;
class Graph {
private Map<Integer, List<Integer>> adjacencyList;
public Graph() {
this.adjacencyList = new HashMap<>();
}
// 添加顶点
public void addVertex(int vertex) {
if (!adjacencyList.containsKey(vertex)) {
adjacencyList.put(vertex, new ArrayList<>());
}
}
// 添加边
public void addEdge(int source, int destination) {
addVertex(source);
addVertex(destination);
adjacencyList.get(source).add(destination);
// 无向图需要添加反向边
// adjacencyList.get(destination).add(source);
}
// 深度优先搜索
public void dfs(int startVertex) {
Set<Integer> visited = new HashSet<>();
dfsRec(startVertex, visited);
}
private void dfsRec(int vertex, Set<Integer> visited) {
visited.add(vertex);
System.out.print(vertex + " ");
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited.contains(neighbor)) {
dfsRec(neighbor, visited);
}
}
}
// 广度优先搜索
public void bfs(int startVertex) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(startVertex);
queue.offer(startVertex);
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
// 检查是否有环
public boolean hasCycle() {
Set<Integer> visited = new HashSet<>();
Set<Integer> recStack = new HashSet<>();
for (int vertex : adjacencyList.keySet()) {
if (hasCycleUtil(vertex, visited, recStack)) {
return true;
}
}
return false;
}
private boolean hasCycleUtil(int vertex, Set<Integer> visited, Set<Integer> recStack) {
if (recStack.contains(vertex)) {
return true;
}
if (visited.contains(vertex)) {
return false;
}
visited.add(vertex);
recStack.add(vertex);
for (int neighbor : adjacencyList.get(vertex)) {
if (hasCycleUtil(neighbor, visited, recStack)) {
return true;
}
}
recStack.remove(vertex);
return false;
}
}散列结构
1. HashMap
基本概念
- 键值对存储
- 通过哈希函数计算存储位置
- 平均时间复杂度O(1)
Java实现
public class CustomHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private Node<K, V>[] table;
private int size;
private float loadFactor;
@SuppressWarnings("unchecked")
public CustomHashMap() {
this.table = new Node[DEFAULT_CAPACITY];
this.size = 0;
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 内部节点类
private static class Node<K, V> {
K key;
V value;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// 计算哈希值
private int hash(K key) {
return key == null ? 0 : Math.abs(key.hashCode() % table.length);
}
// 放入键值对
public V put(K key, V value) {
int index = hash(key);
if (table[index] == null) {
table[index] = new Node<>(key, value);
} else {
Node<K, V> current = table[index];
while (current.next != null) {
if (Objects.equals(current.key, key)) {
V oldValue = current.value;
current.value = value;
return oldValue;
}
current = current.next;
}
if (Objects.equals(current.key, key)) {
V oldValue = current.value;
current.value = value;
return oldValue;
}
current.next = new Node<>(key, value);
}
size++;
// 检查是否需要扩容
if ((float) size / table.length >= loadFactor) {
resize();
}
return null;
}
// 获取值
public V get(K key) {
int index = hash(key);
Node<K, V> current = table[index];
while (current != null) {
if (Objects.equals(current.key, key)) {
return current.value;
}
current = current.next;
}
return null;
}
// 删除键值对
public V remove(K key) {
int index = hash(key);
Node<K, V> current = table[index];
Node<K, V> prev = null;
while (current != null) {
if (Objects.equals(current.key, key)) {
if (prev == null) {
table[index] = current.next;
} else {
prev.next = current.next;
}
size--;
return current.value;
}
prev = current;
current = current.next;
}
return null;
}
// 检查是否包含键
public boolean containsKey(K key) {
return get(key) != null;
}
// 获取大小
public int size() {
return size;
}
// 是否为空
public boolean isEmpty() {
return size == 0;
}
// 扩容
@SuppressWarnings("unchecked")
private void resize() {
Node<K, V>[] oldTable = table;
table = new Node[table.length * 2];
size = 0;
for (Node<K, V> node : oldTable) {
while (node != null) {
put(node.key, node.value);
node = node.next;
}
}
}
}最佳实践
1. 选择合适的数据结构
// 需要快速访问:使用数组或HashMap
int[] numbers = new int[1000];
HashMap<String, Integer> cache = new HashMap<>();
// 需要频繁插入删除:使用链表
LinkedList<String> tasks = new LinkedList<>();
// 需要后进先出:使用栈
Stack<String> undoStack = new Stack<>();
// 需要先进先出:使用队列
Queue<String> taskQueue = new LinkedList<>();
// 需要排序和搜索:使用树
TreeSet<Integer> sortedNumbers = new TreeSet<>();2. 性能优化
// 预分配容量
ArrayList<Integer> list = new ArrayList<>(1000);
HashMap<String, Integer> map = new HashMap<>(1000, 0.75f);
// 使用迭代器而不是索引
for (Integer num : list) {
System.out.println(num);
}
// 避免装箱拆箱
int[] primitiveArray = new int[1000]; // 而不是 Integer[]3. 内存管理
// 及时清理引用
public void cleanup() {
// 清理不再使用的数据结构
list.clear();
map.clear();
stack.clear();
queue.clear();
}
// 使用弱引用避免内存泄漏
WeakHashMap<String, Object> weakMap = new WeakHashMap<>();