「Java 数据结构全面解读」：从基础到进阶的实战指南
数据结构是程序设计中的核心部分，用于组织和管理数据。Java 提供了丰富的集合框架和工具类，涵盖了常见的数据结构如数组、链表、栈、队列和树等。本文将系统性地介绍这些数据结构的概念、特点以及在 Java 中的实现，并通过代码示例进行演示。
一、数据结构基础概念
数据结构研究的是数据的逻辑结构和物理结构，以及它们之间的关系。
1.1 数据的逻辑结构
数据的逻辑结构反映了数据元素之间的逻辑关系，而与存储位置无关。常见逻辑结构包括：
- 散列结构：元素之间除了“同属一个集合”外，没有其他关系。
- 线性结构：元素之间存在一对一的关系，例如数组、链表。
- 树形结构：元素之间存在一对多的关系，例如二叉树。
- 图形结构：元素之间存在多对多的关系。
1.2 数据的物理结构
数据的物理结构描述了数据在计算机内存中的存储方式，主要有：
- 数组结构：元素在内存中是连续存储的，即元素存储在一整块连续的存储空间中，此时根据索引的查询效率是非常高的，因为可以根据下标索引直接一步到位找到元素位置，如果在数组末尾添加和删除元素效率也非常高。缺点是，如果事先申请足够大的内存空间，可能造成空间浪费，如果事先申请较小的内存空间，可能造成频繁扩容导致元素频繁搬家。另外，在数组中间添加、删除元素操作，就需要移动元素，此时效率也要打折。
- 链式结构：元素在内存中是不要求连续存储的，但是元素是封装在结点当中的，结点中需要存储元素数据，以及相关结点对象的引用地址。结点与结点之间可以是一对一的关系，也可以一对多的关系，比如：链表、树等。遍历链式结构只能从头遍历，对于较长的链表来说查询效率不高，对于树结构来说，查询效率比链表要高一点，因为每次可以确定一个分支，从而排除其他分支，但是相对于数组来说，还是数组[下标]的方式更快。树的实现方式有很多种，无非就是在添加/删除效率 与 查询效率之间权衡。
- 索引结构：元素在内存中是不要求连续存储的，但是需要有单独的一个索引表来记录每一个元素的地址，这种结构根据索引的查询效率很高，但是需要额外存储和维护索引表。。
- 哈希结构：元素的存储位置需要通过其hashCode值来计算，查询效率也很多，但是要考虑和解决好哈希冲突问题。
数据结构和算法是一门完整并且复杂的课程
二、Java 中常见的数据结构实现
Java 提供了丰富的数据结构支持，包括动态数组、链表、栈、队列和树等。这些数据结构主要通过 java.util 包中的类实现。
2.1 数组
动态数组特点
逻辑结构特点：线性结构
物理结构特点：
- 申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。
- 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。
例如：整型数组
例如：对象数组
自定义动态数组(拓展)示例代码
package com.test.list;import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;public class MyArrayList<E> implements Iterable<E>{private Object[] all;private int total;public MyArrayList(){all = new Object[10];}public void add(E e) {ensureCapacityEnough();all[total++] = e;}private void ensureCapacityEnough() {if(total >= all.length){all = Arrays.copyOf(all, all.length + (all.length>>1));}}public void insert(int index, E value) {//是否需要扩容ensureCapacityEnough();//添加元素的下标检查addCheckIndex(index);if(total-index > 0) {System.arraycopy(all, index, all, index+1, total-index);}all[index]=value;total++;}private void addCheckIndex(int index) {if(index<0 || index>total){throw new IndexOutOfBoundsException(index+"越界");}}public void delete(E e) {int index = indexOf(e);if(index==-1){throw new NoSuchElementException(e+"不存在");}delete(index);}public void delete(int index) {//删除元素的下标检查checkIndex(index);if(total-index-1 > 0) {System.arraycopy(all, index+1, all, index, total-index-1);}all[--total] = null;}private void checkIndex(int index) {if(index<0 || index>total){throw new IndexOutOfBoundsException(index+"越界");}}public void update(int index, E value) {//更新修改元素的下标检查checkIndex(index);all[index] = value;}public void update(E old, E value) {int index = indexOf(old);if(index!=-1){update(index, value);}}public boolean contains(E e) {return indexOf(e) != -1;}public int indexOf(E e) {int index = -1;if(e==null){for (int i = 0; i < total; i++) {if(e == all[i]){index = i;break;}}}else{for (int i = 0; i < total; i++) {if(e.equals(all[i])){index = i;break;}}}return index;}public E get(int index) {//获取元素的下标检查checkIndex(index);return (E) all[index];}public int size() {return total;}public Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private int cursor;@Overridepublic boolean hasNext() {return cursor!=total;}@Overridepublic E next() {return (E) all[cursor++];}@Overridepublic void remove() {MyArrayList.this.delete(--cursor);}}
}
测试类
package com.test.list;import java.util.Iterator;public class TestMyArrayList {public static void main(String[] args) {MyArrayList<String> my = new MyArrayList<>();my.add("hello");my.add("java");my.add("java");my.add("world");my.add(null);my.add(null);my.add("list");my.add("data");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("-------------------------");System.out.println("在[1]插入JAVA移动技术栈后：");my.insert(1, "JAVA移动技术栈");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("--------------------------");System.out.println("删除[1]位置的元素后：");my.delete(1);System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("删除null元素后：");my.delete(null);System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("------------------------------");System.out.println("替换[3]位置的元素为JAVA移动技术栈后：");my.update(3, "JAVA移动技术栈");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("替换java为JAVA后：");my.update("java", "JAVA");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("------------------------------------");System.out.println("是否包含java：" +my.contains("java"));System.out.println("java的位置：" + my.indexOf("java"));System.out.println("haha的位置：" + my.indexOf("haha"));System.out.println("[0]位置元素是：" + my.get(0));System.out.println("------------------------------------");System.out.println("删除字符串长度>4的元素后：");Iterator<String> iterator = my.iterator();while(iterator.hasNext()) {String next = iterator.next();if(next != null && next.length()>4) {iterator.remove();}}System.out.println("元素个数：" + my.size());for (String string : my) {System.out.println(string);}}
}
2.2 链表
链表特点
- 数据存储在结点中，结点通过指针连接。
- 插入和删除效率高，查询效率低。
- Java 提供了
LinkedList类实现链表，支持双向链表。
示例代码
import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {LinkedList<String> linkedList = new LinkedList<>();linkedList.add("A");linkedList.add("B");linkedList.add("C");System.out.println(linkedList); // 输出：[A, B, C]}
}
2.3 栈
栈特点
- 先进后出（FILO） 或 后进先出（LIFO）：最后插入的元素最先被移除。
- 栈只是逻辑结构，其物理结构可以是数组，也可以是链表，即栈结构分为顺序栈和链式栈。
- 核心类库中的栈结构有
Stack和LinkedList。Stack就是顺序栈，它是Vector的子类，而LinkedList是链式栈。
核心操作方法
peek()：查看栈顶元素，不弹出。pop()：弹出栈顶元素。push(E e)：压入栈顶。
示例代码
import java.util.Stack;public class StackExample {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(10);stack.push(20);stack.push(30);System.out.println(stack.pop()); // 输出：30System.out.println(stack.peek()); // 输出：20}
}
自定义单链表（拓展）
package com.test.list;import java.util.Iterator;public class MyOneWayLinkedList<E> implements Iterable<E>{private Node head;private int total;public void add(E e){Node newNode = new Node(e, null);if(head == null){head = newNode;}else{Node node = head;while(node.next!=null){node = node.next;}node.next = newNode;}total++;}private Node[] findNodes(Object obj){Node[] result = new MyOneWayLinkedList.Node[2];Node node = head;Node find = null;Node beforeFind = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}beforeFind = node;node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}beforeFind = node;node = node.next;}}result[0] = beforeFind;result[1] = find;return result;}public void delete(Object obj){Node[] nodes = findNodes(obj);Node beforeFind = nodes[0];Node find = nodes[1];if(find != null){if(beforeFind == null){head = find.next;}else {beforeFind.next = find.next;}total--;}}private Node findNode(Object obj){return findNodes(obj)[1];}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value) {Node find = findNode(old);if(find != null){find.data = value;}}public int size() {return total;}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node node = head;@Overridepublic boolean hasNext() {return node != null;}@Overridepublic E next() {E value = node.data;node = node.next;return value;}}private class Node{E data;Node next;Node(E data, Node next) {this.data = data;this.next = next;}}
}
测试类
package com.test.list;public class TestMyOneWayLinkedList{public static void main(String[] args) {MyOneWayLinkedList<String> my = new MyOneWayLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");System.out.println("一共有：" + my.size());System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的结果：");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替换java,null后：");my.update("java","JAVA");my.update(null,"chai");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("删除hello,JAVA,null后：");my.delete("hello");my.delete("JAVA");my.delete(null);System.out.println("所有元素：");for (String s : my) {System.out.println(s);}}
}
自定义双链表（拓展）
package com.test.list;import java.util.Iterator;public class MyLinkedList<E> implements Iterable<E>{private Node first;private Node last;private int total;public void add(E e){Node newNode = new Node(last, e, null);if(first == null){first = newNode;}else{last.next = newNode;}last = newNode;total++;}public int size(){return total;}public void delete(Object obj){Node find = findNode(obj);if(find != null){if(find.prev != null){find.prev.next = find.next;}else{first = find.next;}if(find.next != null){find.next.prev = find.prev;}else{last = find.prev;}find.prev = null;find.next = null;find.data = null;total--;}}private Node findNode(Object obj){Node node = first;Node find = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}node = node.next;}}return find;}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value){Node find = findNode(old);if(find != null){find.data = value;}}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node node = first;@Overridepublic boolean hasNext() {return node!=null;}@Overridepublic E next() {E value = node.data;node = node.next;return value;}}private class Node{Node prev;E data;Node next;Node(Node prev, E data, Node next) {this.prev = prev;this.data = data;this.next = next;}}
}
自定义双链表测试
package com.test.list;public class TestMyLinkedList {public static void main(String[] args) {MyLinkedList<String> my = new MyLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");System.out.println("一共有：" + my.size());System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的结果：");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替换java,null后：");my.update("java","JAVA");my.update(null,"chai");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("删除hello，JAVA,null后：");my.delete("hello");my.delete("JAVA");my.delete(null);System.out.println("所有元素：");for (String s : my) {System.out.println(s);}}
}
2.4 队列
队列特点
队列是逻辑结构，其物理结构可以是数组，也可以是链表。队列有普通队列、双端队列、并发队列等等，核心类库中的队列实现类有很多（后面会学到很多），LinkedList 是双端队列的实现类。
Queue 除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。Queue 实现通常不允许插入 null 元素，即使在允许 null 的实现中，也不应该将 null 插入到队列中，因为 null 也用作某些方法的特殊返回值，表明队列不包含元素。
| 抛出异常 | 返回特殊值 | |
|---|---|---|
| 插入 | add(e) | offer(e) |
| 移除 | remove() | poll() |
| 检查 | element() | peek() |
双端队列（Deque）
Deque，名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。Deque 接口的实现类有 ArrayDeque 和 LinkedList，它们一个底层是使用数组实现，一个使用双向链表实现。
| 第一个元素（头部） | 最后一个元素（尾部） | |||
|---|---|---|---|---|
| 抛出异常 | 特殊值 | 抛出异常 | 特殊值 | |
| 插入 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| 移除 | removeFirst() | pollFirst() | removeLast() | pollLast() |
| 检查 | getFirst() | peekFirst() | getLast() | peekLast() |
此接口扩展了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：
**Queue** 方法 | 等效 **Deque** 方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：
| 堆栈方法 | 等效 **Deque** 方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
结论：Deque 接口的实现类既可以用作 FILO 堆栈使用，又可以用作 FIFO 队列使用。
示例代码
import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {Queue<String> queue = new LinkedList<>();queue.add("A");queue.add("B");queue.add("C");System.out.println(queue.poll()); // 输出：ASystem.out.println(queue.peek()); // 输出：B}
}
2.5 二叉树
二叉树特点
- 每个节点最多有两个子节点。
- Java 提供了
TreeMap和TreeSet类实现基于红黑树的有序集合。
示例代码
import java.util.TreeMap;public class TreeMapExample {public static void main(String[] args) {TreeMap<Integer, String> treeMap = new TreeMap<>();treeMap.put(1, "One");treeMap.put(2, "Two");treeMap.put(3, "Three");System.out.println(treeMap); // 输出：{1=One, 2=Two, 3=Three}}
}
普通二叉树：
public class BinaryTree<E>{private TreeNode root; //二叉树的根结点private int total;//结点总个数private class TreeNode{//至少有以下几个部分TreeNode parent;TreeNode left;E data;TreeNode right;public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {this.parent = parent;this.left = left;this.data = data;this.right = right;}}
}
TreeMap红黑树：
public class TreeMap<K,V> {private transient Entry<K,V> root;private transient int size = 0;static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK;/*** Make a new cell with given key, value, and parent, and with* {@code null} child links, and BLACK color.*/Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}}
}
三、总结与建议
Java 提供了对常见数据结构的完整支持，无论是基础的数组、链表，还是复杂的树、队列，都可以通过标准库轻松实现。在实际开发中，应根据场景选择合适的数据结构：
- 快速随机访问：选择
ArrayList。 - 频繁插入和删除：选择
LinkedList。 - 先进后出：选择
Stack。 - 先进先出：选择
Queue。 - 有序存储：选择
TreeMap或TreeSet。
通过对这些数据结构的深入理解和灵活运用，可以显著提升程序的性能和可维护性。
![【C++】P2550 [AHOI2001] 彩票摇奖](https://i-blog.csdnimg.cn/direct/fc6ac6d93b4745b591bb8a8e48f86779.png#pic_right)
