详细介绍java中的数据结构(Java数据结构全面解析与应用指南)

原创

ithorizon 6个月前 (10-20) 阅读数 19 #后端开发

Java数据结构全面解析与应用指南

一、Java数据结构概述

Java中的数据结构是指用于存储和组织数据的方案，它们是程序设计中的基础。合理地选择和使用数据结构，可以有效地节约程序的高效和性能。Java提供了充裕的数据结构，包括线性结构、树状结构、图形结构等。

二、线性结构

1. 数组（Array）

数组是Java中最基本的数据结构之一，它是一组类型相同的元素的集合。数组的长度在创建时就已经确定，且不可改变。


int[] arr = new int[10]; // 创建一个长度为10的整型数组

2. 链表（LinkedList）

链表是一种动态的数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。Java中的LinkedList类实现了List接口，提供了链表的基本操作。


LinkedList linkedList = new LinkedList<>();
linkedList.add(1); // 添加元素
linkedList.add(2);
linkedList.add(3);

3. 栈（Stack）

栈是一种后进先出（LIFO）的数据结构。Java中的Stack类实现了Vector类，提供了栈的基本操作，如push、pop、peek等。


Stack stack = new Stack<>();
stack.push(1); // 入栈
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 出栈，输出3

4. 队列（Queue）

队列是一种先进先出（FIFO）的数据结构。Java中的Queue接口及其实现类，如LinkedList、PriorityQueue等，提供了队列的基本操作。


Queue queue = new LinkedList<>();
queue.add(1); // 入队
queue.add(2);
queue.add(3);
System.out.println(queue.poll()); // 出队，输出1

三、树状结构

1. 树（Tree）

树是一种分层数据结构，由节点组成，每个节点有零个或多个子节点。Java中的TreeMap和TreeSet类实现了SortedMap和SortedSet接口，提供了基于红黑树的实现。


TreeMap treeMap = new TreeMap<>();
treeMap.put("apple", 1);
treeMap.put("banana", 2);
treeMap.put("cherry", 3);

2. 二叉树（Binary Tree）

二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。Java中的BinaryTreeNode类可以用于构建二叉树。


class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
    BinaryTreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

3. 堆（Heap）

堆是一种特殊的树状结构，通常用于实现优先队列。Java中的PriorityQueue类实现了Queue接口，提供了基于堆的实现。


PriorityQueue priorityQueue = new PriorityQueue<>();
priorityQueue.add(3);
priorityQueue.add(1);
priorityQueue.add(2);
System.out.println(priorityQueue.poll()); // 输出1

四、图形结构

1. 图（Graph）

图是一种繁复的数据结构，由节点（顶点）和边组成。Java中的Graph类可以用于构建图，并提供图的遍历和搜索等操作。


class Graph {
    private int numVertices;
    private List> adjLists;
    Graph(int numVertices) {
        this.numVertices = numVertices;
        adjLists = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<>());
        }
    }
    void addEdge(int src, int dest) {
        adjLists.get(src).add(dest);
        adjLists.get(dest).add(src); // 无向图
    }
    // ... 其他方法
}

2. 有向图（Directed Graph）

有向图是图的一种特殊形式，其中的边有方向，即从一个节点到另一个节点的单向连接。


class DirectedGraph extends Graph {
    DirectedGraph(int numVertices) {
        super(numVertices);
    }
    void addEdge(int src, int dest) {
        adjLists.get(src).add(dest); // 只添加单向边
    }
}

3. 重量图（Weighted Graph）

重量图是图的另一种形式，其中的边有权重，即从一个节点到另一个节点的距离或成本。


class WeightedGraph extends Graph {
    private List> adjLists;
    WeightedGraph(int numVertices) {
        super(numVertices);
        adjLists = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<>());
        }
    }
    void addEdge(int src, int dest, int weight) {
        Edge edge = new Edge(src, dest, weight);
        adjLists.get(src).add(edge);
        // 如果是无向图，还需要添加反向边
    }
    class Edge {
        int src;
        int dest;
        int weight;
        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }
}