What are the commonly used data structures in Java?

Java data structures include: 1. Array; 2. Linked list, a recursive data structure; 3. Stack, which stores data according to the principles of "last in, first out" and "first in, last out"; 4. Queue; 5. Tree, which is a collection of hierarchical relationships composed of n (n>0) limited nodes; 6. Heap; 7. Graph; 8. Hash table.

The operating environment of this tutorial: windows7 system, java8 version, DELL G3 computer.

Common Java Data Structures

What are the differences between these 8 data structures?

①, Array

Advantages:

• Querying elements by index is very fast;

• It is also very convenient to traverse the array by index.

Disadvantages:

• The size of the array is determined after creation and cannot be expanded;

• Arrays can only store one type of data;

The operations of adding and deleting elements are time-consuming because other elements need to be moved.

②. Linked list

• The book "Algorithm (4th Edition)" defines a linked list like this:

  The linked list is a recursive data structure. It is either empty (null) or a reference to a node (node). The node also has an element and a pointer to another linked list. citation.

  Java's LinkedList class can express the structure of a linked list very vividly in the form of code:

public class LinkedList<E> {
    transient Node<E> first;
    transient Node<E> last;

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

• This is a This is a doubly linked list. The current element item has both prev and next, but the prev of first is null and the next of last is null. If it is a one-way linked list, there is only next and no prev.

Since the linked list does not need to be stored in a sequential manner, the linked list can achieve O(1) time complexity when inserting and deleting (just need to re- Just point to the reference, no need to move other elements like an array). In addition, the linked list also overcomes the shortcoming of the array that the data size must be known in advance, thus enabling flexible dynamic memory management.

Advantages:

• No need to initialize capacity;

• You can add any element;

• Only the reference needs to be updated when inserting and deleting.

Disadvantages:

• contains a large number of references and takes up a large amount of memory space;

• Search The elements need to traverse the entire linked list, which is time-consuming.

③、Stack

The stack is like a bucket, the bottom is sealed and the top is open, water can You can go in and out. Friends who have used buckets should understand this principle: the water that goes in first is at the bottom of the bucket, and the water that goes in later is at the top of the bucket; the water that goes in last is poured out first, and the water that goes in first is poured out last.

Similarly, the stack stores data according to the principles of "last in, first out" and "first in, last out". The data inserted first is pushed to the bottom of the stack, and the data inserted later is on the top of the stack. The data is read out. time, read sequentially starting from the top of the stack.

④、Queue

The queue is like a section of water pipe, with both ends open. Water goes in at one end and comes out at the other end. The water that goes in first comes out first, and the water that goes in last comes out last.

Somewhat different from the water pipe, the queue will define two ends, one end is called the head of the queue, and the other end is called the tail of the queue. The head of the queue only allows deletion operations (dequeuing), and the tail of the queue only allows insertion operations (enqueueing).

⑤. Tree

The tree is a typical nonlinear structure, which is composed of n A set of hierarchical relationships composed of (n>0) limited nodes.

The reason why it is called "tree" is because this data structure looks like an upside-down tree, except that the root is at the top and the leaves are at the bottom. The tree data structure has the following characteristics:

• Each node has only limited child nodes or no child nodes;

• There is no parent node The node is called the root node;

• Each non-root node has and has only one parent node;

• Except for the root node, each child node Can be divided into multiple disjoint subtrees.

The following figure shows some terms for trees:

Based on the characteristics of the binary search tree, its advantage over other data structures is that the time complexity of search and insertion is low, which is O(logn). If we want to find 5 elements from the above picture, we start from the root node 7. If we find 5, it must be on the left of 7. If we find 4, then 5 must be on the right of 4. If we find 6, then 5 must be on the left of 6. Side, found.

Ideally, by finding nodes through BST, the number of nodes that need to be checked can be halved.

Balanced binary tree: A binary tree if and only if the height difference between the two subtrees of any node is not greater than 1. The highly balanced binary tree proposed by the former Soviet mathematicians Adelse-Velskil and Landis in 1962 is also called an AVL tree according to the scientists' English name.

The balanced binary tree is essentially a binary search tree. However, in order to limit the height difference between the left and right subtrees and avoid situations such as tilted trees that tend to evolve toward linear structures, each of the binary search trees is The left and right subtrees of the node are restricted. The height difference between the left and right subtrees is called the balance factor. The absolute value of the balance factor of each node in the tree is not greater than 1.

The difficulty of balancing a binary tree is how to maintain left-right balance through left- or right-hand rotation when nodes are deleted or added.

The most common balanced binary tree in Java is the red-black tree. The nodes are red or black. The balance of the binary tree is maintained through color constraints:

1) Each node can only be Red or black

2) The root node is black

3) Each leaf node (NIL node, empty node) is black.

4) If a node is red, both of its child nodes are black. That is to say, two adjacent red nodes cannot appear on a path.

5) All paths from any node to each of its leaves contain the same number of black nodes.

⑥, Heap

The heap can be regarded as an array object of a tree, with The following characteristics:

• The value of a node in the heap is always not greater than or not less than the value of its parent node;

• The heap is always A complete binary tree.

The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap.

In a linear structure, a unique linear relationship is satisfied between data elements, and each data element (except the first and last) Each has a unique "predecessor" and "successor";

In the tree structure, there is an obvious hierarchical relationship between data elements, and each data element is only related to one element in the previous layer (parent node) and multiple elements (child nodes) of the next layer are related;

In the graph structure, the relationship between nodes is arbitrary, and any two data elements in the graph may be related. .

⑧, Hash table

Hash table, also called hash table, is a type of hash table that can pass key code values (key-value) direct access data structure, its biggest feature is that it can quickly implement search, insertion and deletion.

The biggest feature of an array is that it is easy to search, but difficult to insert and delete; on the contrary, the linked list is difficult to search, but easy to insert and delete. Hash tables perfectly combine the advantages of both. Java's HashMap also adds the advantages of trees on this basis.

The hash function plays a very key role in the hash table. It can transform input of any length into a fixed length Output, the output is the hash value. The hash function makes the access process of a data sequence faster and more efficient. Through the hash function, the data elements can be quickly located.

If the keyword is k, its value is stored in the storage location of hash(k). Therefore, the value corresponding to k can be obtained directly without traversal.

For any two different data blocks, the possibility of having the same hash value is extremely small. That is to say, for a given data block, it is extremely difficult to find a data block with the same hash value. Furthermore, for a data block, even if only one bit of it is changed, the change in the hash value will be very large - this is the value of Hash!

Although the possibility is extremely small, it will still happen. If a hash conflict occurs, Java's HashMap will add a linked list to the same position in the array. If the length of the linked list is greater than 8, it will be converted into red and black. The tree is processed - this is the so-called zipper method (array linked list).

For more programming related knowledge, please visit: Programming Video! !

The above is the detailed content of What are the commonly used data structures in Java?. For more information, please follow other related articles on the PHP Chinese website!