「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;

        @Override
        public boolean hasNext() {
            return cursor!=total;
        }

        @Override
        public E next() {
            return (E) all[cursor++];
        }

        @Override
        public 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()); // 输出：30
        System.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;
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E>{
        private Node node = head;

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public 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;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E>{
        private Node node = first;

        @Override
        public boolean hasNext() {
            return node!=null;
        }

        @Override
        public 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()); // 输出：A
        System.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。

通过对这些数据结构的深入理解和灵活运用，可以显著提升程序的性能和可维护性。