数据结构——Java

数组

Java数组是一种基础且重要的数据结构，用于存储一组相同类型的数据元素。

在Java中，数组有以下关键特性：

1. 同质性：数组中的每个元素都具有相同的数据类型。
2. 有序性：数组中的元素是有序排列的，可以通过索引（从0开始的整数）来访问各个元素。
3. 可变性：可以在运行时动态地更改数组的大小，例如使用new关键字创建数组时指定其大小。
4. 灵活性：数组可以是一维的，也可以是多维的，如二维数组和三维数组等。
5. 动态初始化与静态初始化：可以在声明数组时直接为其分配内存空间（动态初始化），或者在声明后通过赋值来初始化数组（静态初始化）。
6. 遍历方式：可以使用循环结构来遍历数组的所有元素，进行读取或修改操作。
7. 数组操作：可以进行多种操作，包括但不限于复制、排序、搜索等。
8. 内存管理：数组在内存中是连续存储的，这意味着它们占用一块连续的内存空间。
9. 引用类型：Java中的数组是引用类型，这意味着数组变量存储的是数组对象的引用，而不是实际的元素。
10. 数组长度：可以通过数组的length属性获取其长度，即数组中元素的个数。
11. 默认值：数组在创建时，如果没有显式初始化，会自动赋予默认值，例如数值类型数组默认为0，对象类型数组默认为null。

代码示例：

// 声明一个整型数组
int[] numbers = new int[5];

// 初始化数组元素
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
numbers[3] = 4;
numbers[4] = 5;

// 输出数组元素
for (int i = 0; i < numbers.length; i++) {
    System.out.println(numbers[i]);
}

// 使用增强for循环遍历数组元素
for (int number : numbers) {
    System.out.println(number);
}

// 创建并初始化一个字符串数组
String[] names = {"Alice", "Bob", "Charlie", "David"};

// 输出数组长度
System.out.println("Array length: " + names.length);

// 查找数组中的元素
int index = -1;
for (int i = 0; i < names.length; i++) {
    if (names[i].equals("Charlie")) {
        index = i;
        break;
    }
}
if (index != -1) {
    System.out.println("Found Charlie at index: " + index);
} else {
    System.out.println("Charlie not found in the array");
}

// 复制数组
int[] copy = Arrays.copyOf(numbers, numbers.length);

// 排序数组
Arrays.sort(numbers);

// 二分查找
int target = 3;
int result = Arrays.binarySearch(numbers, target);
if (result >= 0) {
    System.out.println("Found " + target + " at index: " + result);
} else {
    System.out.println(target + " not found in the array");
}

链表

Java中的链表是一种动态数据结构，用于存储元素序列。

链表由一系列节点组成，每个节点包含两部分：一部分是存储数据的值，另一部分是指向下一个节点的引用。这种结构允许在不连续的内存空间中存储数据，从而提供了灵活的内存管理。链表可以根据节点之间链接的方向和数量分为不同类型，包括单向链表、双向链表和循环链表等。

1. 单向链表：每个节点只包含指向下一个节点的链接，而最后一个节点的链接指向null。
2. 双向链表：每个节点包含指向前一个节点和后一个节点的链接，这使得可以从两个方向遍历链表。
3. 循环链表：链表中的最后一个节点指向第一个节点，形成一个闭环。

与ArrayList相比，LinkedList在增加和删除操作上更高效，因为它不需要移动大量元素来维护连续的内存空间。但是，这也意味着在随机访问元素时，链表的效率较低，因为它需要从头节点或尾节点开始逐个遍历直到找到目标元素。

链表提供了一种灵活且高效的数据存储方式，特别适合于需要频繁插入和删除操作的场景。

 代码示例：

// 创建单向链表节点类
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 创建单向链表类
class LinkedList {
    Node head;

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

// 测试链表类
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.display(); // 输出： 1 -> 2 -> 3 -> null
    }
}

栈

Java中的栈是一种后进先出(Last In First Out, LIFO)的数据结构，它继承自Vector类，提供了一系列的操作方法来管理数据。

栈的主要功能包括：

• 压栈（push）：将元素放入栈顶。
• 出栈（pop）：移除栈顶元素并返回该元素。
• 查看栈顶（peek）：返回栈顶元素，但不从栈中移除它。
• 判断栈是否为空（empty）：如果栈中没有元素，则返回true。
• 获取栈的大小（size）：返回栈中的元素数量。

栈的典型应用场景包括：

• 函数调用的执行：在程序执行过程中，函数的局部变量和返回地址都是通过栈来管理的。
• 表达式求值：计算器使用栈来处理中缀、后缀表达式的计算。
• 历史记录：如浏览器后退功能，可以用一个栈来记录用户访问过的网页。

代码示例：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 创建一个空栈
        Stack<Integer> stack = new Stack<>();

        // 向栈中添加元素
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 查看栈顶元素
        System.out.println("栈顶元素：" + stack.peek()); // 输出：栈顶元素：3

        // 弹出栈顶元素
        int topElement = stack.pop();
        System.out.println("弹出的元素：" + topElement); // 输出：弹出的元素：3

        // 遍历栈中的元素
        System.out.println("栈中的元素：");
        for (Integer element : stack) {
            System.out.println(element);
        }
        // 输出：
        // 栈中的元素：
        // 2
        // 1
    }
}

 队列

在Java中，队列是一种基于先进先出（FIFO）原则的线性数据结构。它允许我们在一端添加元素，并在另一端移除元素。这种顺序确保了最先进入队列的元素会最先被取出。

队列在Java中通常有两种实现：LinkedList和ArrayDeque。它们都实现了Queue接口，该接口定义了队列的基本操作，如入队、出队和查看队头元素等。

在多线程环境中，队列常用于任务调度。新任务被加入队列尾部，而工作线程则从队列头部取出任务执行，确保任务按照提交的顺序依次执行，有效避免了线程竞争问题。此外，队列还常用于处理事件驱动系统中的事件排队、缓存管理等场景。

代码示例：

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // 创建一个空队列
        Queue<Integer> queue = new LinkedList<>();

        // 向队列中添加元素
        queue.add(1);
        queue.add(2);
        queue.add(3);

        // 查看队头元素
        System.out.println("队头元素：" + queue.peek()); // 输出：队头元素：1

        // 出队并返回队头元素
        int headElement = queue.poll();
        System.out.println("出队的元素：" + headElement); // 输出：出队的元素：1

        // 遍历队列中的元素
        System.out.println("队列中的元素：");
        for (Integer element : queue) {
            System.out.println(element);
        }
        // 输出：
        // 队列中的元素：
        // 2
        // 3
    }
}

 哈希表

Java中的哈希表是一种基于哈希函数实现的存储结构，它能够快速地进行数据的插入、删除和查找操作。

哈希表（Hash Table）是一种高效的数据结构，它通过使用哈希函数将键（Key）映射到表中一个位置来访问记录，这个过程称为散列。理想的哈希函数会将键均匀地分布在整个表上，以减少冲突（即不同的键映射到同一位置）。在没有冲突的情况下，哈希表的操作时间复杂度可以达到O(1)，即常数时间复杂度。

在Java集合框架中，HashMap是最常用的哈希表实现。它允许使用任何非null对象作为键或值，且键和值的类型可以不同。HashMap的主要操作包括添加（put）、删除（remove）、修改（replace）和查找（get）键值对。由于HashMap不是线程安全的，所以在多线程环境下可能需要使用ConcurrentHashMap或其他同步机制来确保数据的一致性。

此外，Java中还有Hashtable类，它是早期提供的哈希表实现，与HashMap相比，Hashtable是线程安全的，但是它的方法是同步的，这意味着在多线程环境下性能可能会受到影响。因此，如果不需要线程安全，HashMap通常是更好的选择。

 代码示例：

import java.util.HashMap;
import java.util.Map;

public class HashTableExample {
    public static void main(String[] args) {
        // 创建一个空的哈希表
        Map<String, Integer> hashMap = new HashMap<>();

        // 向哈希表中添加元素
        hashMap.put("apple", 1);
        hashMap.put("banana", 2);
        hashMap.put("orange", 3);

        // 获取键对应的值
        int value = hashMap.get("banana");
        System.out.println("Value of 'banana': " + value); // 输出：Value of 'banana': 2

        // 遍历哈希表中的元素
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
        // 输出：
        // Key: apple, Value: 1
        // Key: banana, Value: 2
        // Key: orange, Value: 3

        // 删除键为'banana'的元素
        hashMap.remove("banana");

        // 检查哈希表中是否包含某个键
        boolean containsKey = hashMap.containsKey("banana");
        System.out.println("Contains key 'banana': " + containsKey); // 输出：Contains key 'banana': false
    }
}

树

Java中的树是一种非线性的数据结构，用于存储具有层次关系的数据。

在Java中，树结构由节点和边构成，具有以下特点：

1. 根节点：树的起始节点，没有父节点。
2. 子节点：根节点下的节点称为子节点。
3. 父节点：一个节点下面的直接连接节点称为父节点。
4. 叶子节点：没有子节点的节点称为叶子节点。
5. 子树：一个节点及其所有子节点、子节点的子节点等构成的树称为子树。

在实际应用中，根据节点的子节点数量，树可以分为多种类型，如二叉树、多叉树等。二叉树是每个节点最多有两个子节点的树，常用于排序、搜索和组织数据等场景。

代码示例：

// 定义树节点类
class TreeNode {
    int val; // 节点的值
    TreeNode left; // 左子节点
    TreeNode right; // 右子节点

    public TreeNode(int val) {
        this.val = val;
    }
}

// 创建树节点
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

// 遍历树节点
void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.val); // 访问当前节点
    traverse(node.left); // 递归遍历左子树
    traverse(node.right); // 递归遍历右子树
}

// 调用遍历方法
traverse(root);

 堆

Java中的堆是内存中的一个区域，主要用于存储动态分配的对象。以下是对Java堆的一些详细解释：

1. 存储对象：堆用于存储通过new操作符创建的对象实例。它是JVM管理的内存中最大的一块，用于存放不断生成的各种各样的对象。
2. 共享内存区域：Java堆是所有线程共享的内存区域，不像栈那样每个线程都有自己独立的空间。
3. 自动内存管理：由于堆空间的内存不需要连续，它的大小可以动态扩展和收缩，以适应程序的需要。同时，JVM通过垃圾回收器自动管理这块内存区域，定期清理不再使用的对象。
4. 性能特点：与栈相比，访问堆内存的速度较慢，因为其内存分配是在运行时动态进行的。但堆的优势在于可以动态地分配内存大小，使得程序在运行时根据需要创建对象。
5. 引用计数器：在堆中，每个对象都有一个引用计数器。当没有任何引用变量指向该对象时，其引用计数器变为0，该对象可能被垃圾收集器视为垃圾并进行回收。
6. 分代管理：为了更好地管理内存，JVM通常将堆划分为新生代和老年代两部分。新生代用于存放新创建的对象，而老年代存放长时间存活的对象。这种划分有助于提高垃圾回收的效率。

代码示例：

// 创建对象并分配内存空间
Object obj = new Object();

// 获取对象的引用计数器
System.out.println(obj.hashCode()); // 输出对象的哈希码，即引用计数器的值

// 将对象设置为null，使其成为垃圾回收的候选对象
obj = null;

// 执行垃圾回收操作
System.gc();

 图

Java中的图是一种复杂的非线性数据结构，它表示了元素之间的“多对多”关系。

图由两部分组成：顶点（Vertex）和边（Edge）。顶点是图中的数据元素，而边则表示顶点之间的关系。在图的表示中，通常使用字母V来表示顶点集合，E来表示边集合，因此一个图可以表示为G = (V, E)。以下是图的几个基本概念：

• 顶点：图中的数据元素，也称为节点。在一个社交网站的好友关系图中，每个用户都可以被视为一个顶点。
• 边：连接两个顶点的线，表示顶点之间的关系。边可以是单向的或双向的，具体取决于它们表示的关系类型。
• 度：一个顶点的度是指与该顶点相连的边的数量。在有向图中，度分为入度和出度，分别表示指向该顶点和从该顶点出发的边的数量。
• 路径：在图中，路径是指一系列的边，它们按顺序连接了一系列的顶点。路径的概念在图的遍历和搜索算法中非常重要。
• 循环：如果一条路径的起点和终点相同，那么这条路径就是一个循环。
• 连通性：在无向图中，如果从任何一个顶点都可以通过路径到达任何其他顶点，那么这个图是连通的。

代码示例：

import java.util.*;

class Graph {
    private Map<String, List<String>> adjacencyList;

    public Graph() {
        adjacencyList = new HashMap<>();
    }

    // 添加顶点
    public void addVertex(String vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new ArrayList<>());
        }
    }

    // 添加边
    public void addEdge(String vertex1, String vertex2) {
        if (adjacencyList.containsKey(vertex1) && adjacencyList.containsKey(vertex2)) {
            adjacencyList.get(vertex1).add(vertex2);
            adjacencyList.get(vertex2).add(vertex1); // 如果是无向图，需要添加这行代码
        }
    }

    // 打印图的邻接表表示
    public void printGraph() {
        for (Map.Entry<String, List<String>> entry : adjacencyList.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addEdge("A", "B");
        graph.addEdge("B", "C");
        graph.printGraph();
    }
}