数据结构有哪些类型（对于数据结构的简述）

在学习计算机时，数据结构是不可忽视的一点，从考研时的408课程，再到工作中编写软件，网站，要想在计算机领域站住脚跟，数据结构是必备的

在这里，我对于数据结构进行了汇总，并简要描述，在后面会对各种数据结构进行详细介绍

在 Java 中，数据结构主要分为两大类：线性数据结构 和 非线性数据结构。Java 标准库（如 java.util 包）提供了许多现成的数据结构实现，这些实现基于不同的底层存储方式和操作特性。以下是对 Java 中常见数据结构的详细描述：

1. 线性数据结构

线性数据结构是指数据元素之间存在一对一的线性关系。

（1）数组（Array）

数组是一种基本的线性数据结构，用于存储固定大小的同类型数据元素。

• 特点：

  • 元素存储在连续的内存空间中。

  • 支持随机访问，通过索引可以快速访问任意位置的元素，时间复杂度为 O(1)。

  • 插入和删除操作效率较低，通常需要移动大量元素，时间复杂度为 O(n)。

  • 数组的大小在创建后不可变。

• 示例代码：

• int[] array = new int[10];
  array[0] = 1;
  array[1] = 2;
  System.out.println(array[0]); // 输出：1

（2）动态数组（ArrayList）

ArrayList 是 Java 中基于动态数组实现的集合类，它提供了动态扩容的功能。

• 特点：

  • 底层使用数组存储元素。

  • 支持随机访问，时间复杂度为 O(1)。

  • 插入和删除操作效率较低，时间复杂度为 O(n)。

  • 动态扩容，可以根据需要自动调整数组大小。

• 示例代码：

• import java.util.ArrayList;public class Main {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);System.out.println(list.get(0)); // 输出：1list.remove(0);System.out.println(list.get(0)); // 输出：2}
  }

（3）链表（LinkedList）

LinkedList 是 Java 中基于双向链表实现的集合类，它支持高效的插入和删除操作。

• 特点：

  • 底层使用双向链表存储元素。

  • 不支持随机访问，访问任意位置的元素需要从头开始遍历，时间复杂度为 O(n)。

  • 插入和删除操作效率较高，时间复杂度为 O(1)。

  • 适合频繁插入和删除操作的场景。

• 示例代码：

• import java.util.LinkedList;public class Main {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);System.out.println(list.get(0)); // 输出：1list.remove(0);System.out.println(list.get(0)); // 输出：2}
  }

（4）栈（Stack）

栈是一种后进先出（LIFO）的数据结构，Java 提供了 Stack 类来实现栈。

• 特点：

  • 支持快速的插入和删除操作，时间复杂度为 O(1)。

  • 只能在栈顶进行插入和删除操作。

  • 适合实现函数调用、表达式求值等场景。

• 示例代码：

• import java.util.Stack;public class Main {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);System.out.println(stack.pop()); // 输出：2System.out.println(stack.pop()); // 输出：1}
  }

（5）队列（Queue）

队列是一种先进先出（FIFO）的数据结构，Java 提供了 Queue 接口和多种实现类（如 LinkedList、ArrayDeque 等）。

• 特点：

  • 支持快速的插入和删除操作，时间复杂度为 O(1)。

  • 只能在队尾插入元素，在队头删除元素。

  • 适合实现任务调度、消息队列等场景。

• 示例代码：

• import java.util.LinkedList;
  import java.util.Queue;public class Main {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.add(1);queue.add(2);System.out.println(queue.poll()); // 输出：1System.out.println(queue.poll()); // 输出：2}
  }

2. 非线性数据结构

非线性数据结构是指数据元素之间存在多对多的关系。

（1）树（Tree）

树是一种层次化的数据结构，每个节点可以有多个子节点。

• 常见类型：

  • 二叉树（Binary Tree）：每个节点最多有两个子节点。

  • 二叉搜索树（Binary Search Tree）：左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。

  • 平衡二叉树（Balanced Binary Tree）：左右子树的高度差不超过 1。

  • 红黑树（Red-Black Tree）：一种自平衡的二叉搜索树。

  • 堆（Heap）：一种特殊的完全二叉树，分为最大堆和最小堆。

• 示例代码（二叉树）：

• class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
  }public class Main {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);}
  }

（2）图（Graph）

图是一种由节点（顶点）和边组成的复杂数据结构，节点之间可以存在任意关系。

• 特点：

  • 节点之间通过边连接，可以是有向边或无向边。

  • 支持复杂的遍历和搜索算法，如深度优先搜索（DFS）和广度优先搜索（BFS）。

  • 适合表示复杂的关系网络，如社交网络、地图路径等。

• 示例代码（无向图）：

• import java.util.ArrayList;
  import java.util.List;class Graph {private int vertices;private List<List<Integer>> adjacencyList;public Graph(int vertices) {this.vertices = vertices;this.adjacencyList = new ArrayList<>();for (int i = 0; i < vertices; i++) {adjacencyList.add(new ArrayList<>());}}public void addEdge(int src, int dest) {adjacencyList.get(src).add(dest);adjacencyList.get(dest).add(src); // 无向图}public void printGraph() {for (int i = 0; i < vertices; i++) {System.out.println("Adjacency list of vertex " + i);System.out.print("head");for (int j : adjacencyList.get(i)) {System.out.print(" -> " + j);}System.out.println();}}
  }public class Main {public static void main(String[] args) {Graph graph = new Graph(5);graph.addEdge(0, 1);graph.addEdge(0, 4);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(1, 4);graph.addEdge(2, 3);graph.addEdge(3, 4);graph.printGraph();}
  }

（3）哈希表（Hash Table）

哈希表是一种通过哈希函数将键映射到值的数据结构。

• 特点：

  • 提供快速的插入、删除和查找操作，平均时间复杂度为 O(1)。

  • 哈希函数将键映射到存储位置，可能存在冲突，需要解决冲突的方法（如链表法、开放寻址法）。

  • 适合实现字典、缓存等场景。

• 示例代码：

• import java.util.HashMap;public class Main {public static void main(String[] args) {HashMap<String, Integer> map = new HashMap<>();map.put("Alice", 25);map.put("Bob", 30);System.out.println(map.get("Alice")); // 输出：25map.remove("Bob");}
  }