从零开始用Java实现：8种核心数据结构与5大算法

admin 2025-06-28 阅读:4 评论:0

在编程世界中，数据结构和算法是构建高效程序的基石。作为一门广泛使用的编程语言，Java提供了强大的工具集来实现各种数据结构和算法。本文将深入探讨如何使用Java实现常见的数据结构和算法，帮助开发者提升编程能力和面试竞争力。一、数据结构实现篇...

在编程世界中，数据结构和算法是构建高效程序的基石。作为一门广泛使用的编程语言，Java提供了强大的工具集来实现各种数据结构和算法。本文将深入探讨如何使用Java实现常见的数据结构和算法，帮助开发者提升编程能力和面试竞争力。

一、数据结构实现篇

1. 数组(Array)的实现

数组是最基础的数据结构，Java中数组是定长的，但我们可以通过以下方式实现动态数组：

从零开始用Java实现：8种核心数据结构与5大算法

public class DynamicArray<T> {
    private Object[] array;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public DynamicArray() {
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }

    // 添加元素方法
    public void add(T element) {
        ensureCapacity();
        array[size++] = element;
    }

    // 扩容方法
    private void ensureCapacity() {
        if(size == array.length) {
            int newCapacity = array.length * 2;
            array = Arrays.copyOf(array, newCapacity);
        }
    }

    // 其他方法...
}

2. 链表(LinkedList)的实现

链表是另一种基础数据结构，下面是单向链表的Java实现：

从零开始用Java实现：8种核心数据结构与5大算法

public class SinglyLinkedList<T> {
    private static class Node<T> {
        T data;
        Node<T> next;

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

    private Node<T> head;
    private int size;

    // 添加节点到链表尾部
    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        if(head == null) {
            head = newNode;
        } else {
            Node<T> current = head;
            while(current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // 其他方法...
}

二、算法实现篇

1. 排序算法实现

快速排序(Quick Sort)的Java实现

public class QuickSort {
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if(low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for(int j = low; j < high; j++) {
            if(arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2. 搜索算法实现

二分查找(Binary Search)的Java实现

public class BinarySearch {
    public static int search(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;

            if(sortedArray[mid] == target) {
                return mid;
            } else if(sortedArray[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // 未找到
    }
}

三、高级数据结构实现

1. 哈希表(HashMap)的实现

public class MyHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;

    private Entry<K, V>[] table;
    private int size;

    static class Entry<K, V> {
        final K key;
        V value;
        Entry<K, V> next;

        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public MyHashMap() {
        table = new Entry[DEFAULT_CAPACITY];
        size = 0;
    }

    public V put(K key, V value) {
        // 实现put逻辑
        // ...
    }

    public V get(K key) {
        // 实现get逻辑
        // ...
    }

    // 其他方法...
}

2. 二叉搜索树(BST)的实现

public class BinarySearchTree<T extends Comparable<T>> {
    private static class Node<T> {
        T data;
        Node<T> left;
        Node<T> right;

        Node(T data) {
            this.data = data;
        }
    }

    private Node<T> root;

    public void insert(T data) {
        root = insert(root, data);
    }

    private Node<T> insert(Node<T> node, T data) {
        if(node == null) {
            return new Node<>(data);
        }

        int cmp = data.compareTo(node.data);
        if(cmp < 0) {
            node.left = insert(node.left, data);
        } else if(cmp > 0) {
            node.right = insert(node.right, data);
        }

        return node;
    }

    // 其他方法...
}