In-depth discussion of JAVA's underlying data structures and algorithms

Java is an object-oriented programming language. Developers can use different data structures and algorithms to optimize program performance and write more efficient code. In this article, we will delve into the underlying data structures and algorithms of Java and share some sample code to help you better understand these concepts.

1. Basic data structures

The basic data structures in Java include arrays, linked lists, stacks and queues. These data structures are the basis for all other data structures and algorithms.

1.1 Array

An array is a collection of values ​​that are stored continuously in memory. In Java, arrays can have different data types, such as int, char, String, double, float, etc.

The following is a sample code for a Java array:

int[] nums = new int[5];
nums[0] = 1;
nums[1] = 2;
nums[2] = 3;
nums[3] = 4;
nums[4] = 5;

This code creates an int type array named nums, which contains 5 integers. Next, we assign a value to each element of the array. To access elements in an array, you use index values, for example nums[0] means the first element in the array has a value of 1.

1.2 Linked list

A linked list is a linear data structure. In Java, it consists of nodes. Each node contains a value and a pointer to the next node. Linked lists can be of different types such as singly linked lists, doubly linked lists, and circular linked lists.

The following is a sample code for a Java one-way linked list:

class Node {
    int value;
    Node next;
    public Node(int value) {
        this.value = value;
        next = null;
    }
}

class LinkedList {
    Node head;
    public LinkedList() {
        head = null;
    }
    public void add(int value) {
        Node newNode = new Node(value);
        if(head == null) {
            head = newNode;
        }
        else {
            Node current = head;
            while(current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
}

This code defines a Node class that contains a value and a pointer to the next node. In addition, a LinkedList class is also defined, in which the add() method is used to add new values ​​to the linked list. If the linked list is empty, we set the new node as the head node. Otherwise, we traverse the linked list, find the last node, and add the new node as its next attribute.

1.3 Stack

The stack is a last-in-first-out (LIFO) data structure. In Java, it can be implemented through an array or a linked list. In a stack, elements are added sequentially, but only the most recently added elements are accessible because they are at the top of the stack.

The following is a sample code for a stack implemented by a Java array:

class ArrayStack {
    int[] arr;
    int top;
    int size;
    public ArrayStack(int size) {
        this.size = size;
        arr = new int[size];
        top = -1;
    }
    public void push(int value) {
        if(top == size - 1) {
            System.out.println("Stack overflow!");
            return;
        }
        arr[++top] = value;
        System.out.println("Element pushed: " + value);
    }
    public int pop() {
        if(top == -1) {
            System.out.println("Stack underflow!");
            return -1;
        }
        int value = arr[top--];
        System.out.println("Element popped: " + value);
        return value;
    }
}

This code defines an ArrayStack class, which contains an array, the size of the stack and the index top of the top element in the stack . The push() method adds a new element to the stack and outputs an error message if the stack is full. The pop() method is used to remove the top element from the stack and output an error message if the stack is empty.

1.4 Queue

Queue is a first-in-first-out (FIFO) data structure, which can be implemented through an array or linked list in Java. In a queue, new elements are always added to the end of the queue, and the oldest element added is always at the front of the queue.

The following is a sample code for a queue implemented by a Java linked list:

class Node {
    int value;
    Node next;
    public Node(int value) {
        this.value = value;
        next = null;
    }
}

class Queue {
    Node head, tail;
    public Queue() {
        head = null;
        tail = null;
    }
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if(tail == null) {
            head = tail = newNode;
        }
        else {
            tail.next = newNode;
            tail = newNode;
        }
    }
    public int dequeue() {
        if(head == null) {
            System.out.println("Queue underflow!");
            return -1;
        }
        int value = head.value;
        head = head.next;
        if(head == null) {
            tail = null;
        }
        System.out.println("Element dequeued: " + value);
        return value;
    }
}

This code defines a Node class, which contains a value and a pointer to the next node. In addition, a Queue class is also defined, in which the enqueue() method is used to add new nodes to the queue. If the queue is empty, new nodes are set as head and tail. Otherwise, we link the new node to the tail and update the tail node with the new node. The dequeue() method is used to remove an element from the queue and return its value. If the queue is empty, an error message is output.

2. Common Algorithms

In Java, different algorithms can be used to solve various problems, such as sorting, search, and graphics. Below are several common algorithms and we will continue to explore their implementation in depth.

2.1 Bubble sort

Bubble sort is a simple and easy-to-implement sorting algorithm that sorts an array by comparing adjacent elements and exchanging their positions. This process is repeated until there are no more elements to swap. The following is a sample code for the bubble sort algorithm implemented in Java:

class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j < n - i - 1; j++) {
                if(arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

This code defines a sort() method that accepts an array parameter of type int and is used to sort the array. In the sort() method, we use two nested for loops to iterate through the array and compare adjacent elements. If the element on the left is larger than the element on the right, swap their positions.

2.2 Binary search

Binary search is a search algorithm that can be used to find specific elements in an ordered array. The algorithm compares the middle element of the array to the target element each time to determine whether the target element is on the left or right. This process is repeated until the target element is found or determined not to exist.

The following is a sample code for a binary search algorithm implemented in Java:

class BinarySearch {
    public static int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] == target) {
                return mid;
            }
            else if(arr[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

This code defines a search() method that accepts an array of type int and a target element parameter. In the search() method, we use two pointers left and right to determine the boundaries of the array. We then use a while loop to compare the middle element of the array with the target element to determine the position of the target element. If the target element is smaller than the middle element, the left half is searched. Otherwise, the right half is searched.

2.3 Recursion

Recursion is a self-calling function that can be used to solve various problems. In Java, recursion can be achieved through base cases and recursive calls.

以下是一个使用Java实现的递归算法的示例代码：

class Recursion {
    public static int factorial(int n) {
        if(n == 0) {
            return 1;
        }
        else {
            return n * factorial(n - 1);
        }
    }
}

这个代码定义了一个factorial()方法，使用递归来计算一个整数的阶乘。在factorial中，我们首先定义一个基本情况n=0，并返回1。然后，我们使用n×factorial(n-1)的递归公式来计算更大的数的阶乘。

三、结论

Java提供了一个强大的工具箱来处理各种数据结构和算法，可以用于设计和优化各种程序。在本文中，我们深入探讨了Java的基础数据结构和算法，包括数组、链表、栈、队列、冒泡排序、二分查找和递归，并给出了相应的示例代码。通过这些概念和代码示例的学习，您可以更好地理解Java的实现方式和优化程序的方法。

The above is the detailed content of In-depth discussion of JAVA's underlying data structures and algorithms. For more information, please follow other related articles on the PHP Chinese website!