Java数据结构

Java是一门强类型的编程语言，其在数据结构方面也提供了各种优秀的实现。Java数据结构既可以是Java编程语言自身的数据结构，也可以是各种算法的基础。

一、数组

数组是一种线性结构，它在内存中占据一段连续的地址。Java提供了数组支持，允许我们创建一维或多维数组。一维数组定义如下：

int[] intArray = new int[10];

它定义了一个长度为10的整型数组。访问数组元素的语法如下：

int firstElement = intArray[0];
int secondElement = intArray[1];

多维数组的定义如下：

int[][] intArray = new int[10][5];

其中第一个维度表示行数，第二个维度表示列数。访问多维数组元素的语法如下：

int firstElement = intArray[0][0];
int secondElement = intArray[0][1];
int thirdElement = intArray[1][0];

二、链表

链表是一种动态数据结构，它由一系列节点组成，每个节点包含一个数据元素和指向下一个节点的指针。Java实现链表的方式有很多种，下面介绍其中一种经典的实现方式。

链表节点定义如下：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

其中val表示节点的值，next表示指向下一个节点的指针。创建链表的语法如下：

ListNode head = new ListNode(0);
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
head.next = node1;
node1.next = node2;

在这个例子中，head节点没有实际意义，它只是一个表头。链表节点可以通过指针遍历：

ListNode cur = head.next;
while (cur != null) {
    int value = cur.val;
    cur = cur.next;
}

三、栈和队列

栈和队列都是数据结构中的经典代表，它们分别在第三章和第四章的内容中详细介绍，这里简单提及它们的Java实现方式。

栈的Java实现是：使用LinkedList类作为底层容器，通过其addFirst和removeFirst方法模拟栈的入栈和出栈操作。

class MyStack {
    LinkedList list = new LinkedList
   ();
    // 入栈
    public void push(int x) {
        list.addFirst(x);
    }
    // 出栈
    public int pop() {
        return list.removeFirst();
    }
    // 返回栈顶元素
    public int top() {
        return list.getFirst();
    }
}

   
  

队列的Java实现是：使用LinkedList类作为底层容器，通过其addLast和removeFirst方法模拟队列的入队和出队操作。

class MyQueue {
    LinkedList list = new LinkedList
   ();
    // 入队
    public void push(int x) {
        list.addLast(x);
    }
    // 出队
    public int pop() {
        return list.removeFirst();
    }
    // 返回队列头部元素
    public int peek() {
        return list.getFirst();
    }
}

   
  

四、二叉树

二叉树是一种非线性数据结构，它由节点和指向节点的二叉树边组成。Java实现二叉树的方式有很多，这里简单介绍一种。

二叉树节点的定义如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

二叉树可以通过递归遍历：

private void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    int value = node.val;
    traverse(node.right);
}

五、哈希表

哈希表是一种高效的查找数据结构，Java内置了多种哈希表相关的类和接口，它们支持快速的插入/删除/查找操作。这里介绍其中的HashMap类。

HashMap是一种基于哈希表的Map接口实现，它提供了键值对的存储和遍历功能。

以字符串类型为例，放入HashMap的过程如下：

Map map = new HashMap<>();
map.put("apple", 1);
map.put("orange", 2);
map.put("banana", 3);

  

访问HashMap的过程如下：

int value1 = map.get("apple");
int value2 = map.get("orange");
int value3 = map.get("banana");

六、堆

堆是一种优先队列，它可以快速的插入和删除某个元素，并且按照一定的规则进行排序，使得堆中的最小值或最大值总是可以快速的找到。Java提供了优先队列的支持，可以通过Heap实现。

使用Java Heap创建小根堆如下：

PriorityQueue minHeap = new PriorityQueue
   ((n1, n2) -> n1 - n2);

   
  

在这个例子中，定义了一个Lambda表达式，它告诉Java如何比较两个数的大小。

可以将元素插入堆中：

minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);

可以从堆中取出元素：

int smallest = minHeap.peek();
int smallest1 = minHeap.poll();
int smallest2 = minHeap.poll();

七、图

图是一种非线性数据结构，它由节点和连接这些节点的边构成。Java提供了两种主要的图实现方式：邻接矩阵和邻接表。

邻接矩阵的Java实现如下：

class MatrixGraph {
    private int[][] matrix;
    public MatrixGraph(int n) {
        matrix = new int[n][n];
    }
    public void addEdge(int u, int v) {
        matrix[u][v] = 1;
    }
    public boolean hasEdge(int u, int v) {
        return matrix[u][v] == 1;
    }
}

其中matrix数组表示邻接矩阵，每一个元素matrix[i][j]表示从i到j是否有边。

邻接表的Java实现如下：

class ListGraph {
    private Map> map = new HashMap
   >();
    public void addEdge(int u, int v) {
        List
     list = map.getOrDefault(u, new ArrayList
     ());
        list.add(v);
        map.put(u, list);
    }
    public boolean hasEdge(int u, int v) {
        List
       list = map.get(u);
        return list != null && list.contains(v);
    }
}

      
     
    
   
  

在这个例子中，ListGraph使用了Map和List来存储图的信息。

结束语

Java数据结构提供了丰富的数据结构类型，以及相应的API和实现方式。Java程序员可以依据自己的具体需求来选择最优的数据结构，以达到代码结构清晰、逻辑清晰、性能优秀的效果。我们在实际编程中要使用它们并且熟识它们，才能在数据结构上有更好的掌控能力。