Java data structure and algorithm: detailed explanation of practical cases

Data structures and algorithms are key elements for program efficiency. Commonly used data structures in Java include arrays, linked lists, stacks, and binary trees. Common algorithms include quick sort and binary search. This article explains these concepts in a simple and easy-to-understand manner through practical cases: Array: continuously stores elements of the same type, such as student grades. Linked list: elements are linked through pointers, such as a simulated queue. Stack: follows the LIFO principle, such as tracing function calls. Binary tree: A tree data structure, such as a file system directory. Quick sort: Divide and conquer strategy, divide the array into two parts and sort them separately. Binary search: Perform a binary search on an ordered array to narrow the search scope.

Java data structure and algorithm: detailed explanation of practical cases

Introduction

Data Structures and algorithms are the foundation of computer science, and they determine the efficiency and robustness of programs. This article will explain the commonly used data structures and algorithms in Java in a simple and easy-to-understand manner through a series of practical cases.

Array

Definition: A collection of elements of the same type stored in a continuous memory space.

Practical case: Storing student grades

int[] scores = {90, 85, 78, 95, 82};

Linked list

Definition: Elements are linked by pointers linear data structure.

Actual case: Simulation queue

class Node {
    int value;
    Node next;
}

class Queue {
    Node head;
    Node tail;

    public void enqueue(int value) {
        Node newNode = new Node();
        newNode.value = value;
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    public int dequeue() {
        if (head == null) {
            throw new RuntimeException("Queue is empty");
        }

        int value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }
}

Stack

Definition: Follow last-in-first-out ( LIFO) principle linear data structure.

Practical case: Tracking function call

class Stack<T> {
    private List<T> elements = new ArrayList<>();

    public void push(T element) {
        elements.add(element);
    }

    public T pop() {
        if (elements.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return elements.remove(elements.size() -1);
    }

    public T peek() {
        if (elements.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return elements.get(elements.size() -1);
    }
}

Binary tree

Definition: Contains a root node A tree data structure with zero or more child nodes.

Practical case: File system directory

class TreeNode {
    private String name;
    private List<TreeNode> children;

    // ... 其他代码
}

class FileSystem {
    private TreeNode root;

    // ... 其他代码
}

Sort algorithm

Quick sort

Description: Divide and conquer strategy, divide the array into two parts, sort them separately, and then merge.

Practical case: Sort a set of numbers

public static void quickSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }

    int pivot = arr[0];
    int leftIndex = 0;
    int rightIndex = arr.length - 1;

    while (leftIndex < rightIndex) {
        while (arr[rightIndex] >= pivot && rightIndex > leftIndex) {
            rightIndex--;
        }
        arr[leftIndex] = arr[rightIndex];

        while (arr[leftIndex] <= pivot && rightIndex > leftIndex) {
            leftIndex++;
        }
        arr[rightIndex] = arr[leftIndex];
    }
    arr[leftIndex] = pivot;

    quickSort(arr, 0, leftIndex - 1);
    quickSort(arr, leftIndex + 1, arr.length - 1);
}

Search algorithm

Binary search

Description: Perform a binary search on an ordered array and narrow the search range step by step.

Practical case: Find an element in an array

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

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

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

The above is the detailed content of Java data structure and algorithm: detailed explanation of practical cases. For more information, please follow other related articles on the PHP Chinese website!