Shulou(Shulou.com)06/01 Report--

This article focuses on "what are the common data structures in java". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "what are the common data structures in java"?

①, array

Advantages:

Querying elements by index is fast.

It is also convenient to traverse the array by index.

Disadvantages:

The size of the array is determined after it is created and cannot be expanded.

Arrays can store only one type of data

Adding and removing elements is time-consuming because other elements have to be moved.

②, linked list

The linked list is defined in the book algorithm (4th Edition):

A linked list is a recursive data structure that is either null or a reference to a node (node) that also has an element and a reference to another linked list.

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

Public class LinkedList {

Transient Node first

Transient Node last

Private static class Node {

E item

Node next

Node prev

Node (Node prev, E element, Node next) {

This.item = element

This.next = next

This.prev = prev

}

}

}

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

The disadvantage of one-way linked lists is that they can only be traversed from beginning to end, while two-way linked lists can go forward and backward, finding both the next and the previous one-- an extra storage space needs to be allocated on each node.

The data in the linked list is stored in a "chained" structure, so it can achieve the effect of discontiguous memory, and the array must be a continuous piece of memory.

Since it does not have to be stored sequentially, linked lists can achieve O (1) time complexity when inserting and deleting (you only need to re-point to the reference and do not need to move other elements like an array). In addition, the linked list also overcomes the disadvantage that the array must know the data size in advance, so that flexible dynamic memory management can be realized.

Advantages:

No need to initialize capacity

You can add any element

Only references need to be updated when inserting and deleting.

Disadvantages:

It contains a large number of references and takes up a lot of memory space.

Finding elements requires traversing the entire linked list, which is time-consuming.

③, stack

The stack is like a bucket, the bottom is sealed, the top is open, and the water can go in and out. Friends who have used the bucket should understand this truth: 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 is poured out first, and the water that goes in first is poured out later.

Similarly, the stack stores data according to the principles of "last in, first out" and "first in, first out". The first inserted data is pressed into the bottom of the stack, and the later inserted data is at the top of the stack. When reading out the data, it is read out from the top of the stack.

④, queu

The queue is like a pipe with openings at both ends. 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 comes out later.

Unlike the water pipe, the queue defines both ends, one end is called the head of the line, and the other end is called the end of the line. Only delete operations are allowed at the head of the line (out of the queue) and only insert operations are allowed at the end of the line (join the queue).

Note that the stack is first-in, first-out, and the queue is first-in, first-out-although both are linear tables, the principles are different and the structure is different.

⑤, tree

Tree is a typical nonlinear structure, which is a hierarchical set composed of n (n > 0) finite nodes.

It is called "tree" because this data structure looks like an upside-down tree, but with roots at the top and leaves at the bottom. The tree data structure has the following characteristics:

Each node has only a limited number of children or no child nodes

A node without a parent node is called a root node

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

In addition to the root node, each child node can be divided into multiple disjoint subtrees.

The following figure shows some terms for the tree:

The root node is layer 0, its child node is layer 1, the child node is layer 2, and so on.

Depth: for any node n, the depth of n is the only path from root to n, and the depth of root is 0.

Height: for any node n, the height of n is the longest path from n to a leaf, and the height of all leaves is 0.

There are many kinds of trees, and the common ones are:

Unordered tree: there is no sequential relationship between the children of any node in the tree. So how to understand the disordered tree, what does it look like?

If there are three nodes, one is the parent node and two are sibling child nodes, then there are three situations:

If there are three nodes, one is the parent node and two are child nodes of different levels, then there are six situations:

The unordered tree composed of three nodes can be divided into nine cases.

Binary tree: each node contains at most two subtrees. Binary tree can be divided into many kinds according to different forms of expression.

Complete binary tree: for a binary tree, assume that its depth is d (d > 1). Except for layer d, the number of nodes in all other layers has reached the maximum, and all nodes in layer d are closely arranged continuously from left to right. Such a binary tree is called a complete binary tree.

For example, d is 3, with the exception of layer 3, layer 1 and layer 2 reach the maximum (2 child nodes), and all nodes in layer 3 are closely linked from left to right (H, I, J, K, L). Meets the requirements of a complete binary tree.

Full binary tree: a binary tree in which the number of nodes in each layer reaches the maximum. There are two representations. The first, as shown in the following picture (each layer is full), satisfies that the number of nodes in each layer reaches a maximum of 2.

Second, as shown in the following picture (although each layer is dissatisfied), the number of nodes in each layer still reaches the maximum of 2.

Binary search tree: the English name is Binary Search Tree, or BST, which needs to meet the following conditions:

The left subtree of any node is not empty, and the value of all nodes on the left subtree is less than the value of its root node.

The right subtree of any node is not empty, and the value of all nodes on the right subtree is greater than the value of its root node.

The left and right subtrees of any node are also binary search trees.

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

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

Balanced binary tree: if and only if the height difference between 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 AVL tree according to the English name of scientists.

In essence, the balanced binary tree is also a binary search tree, but in order to limit the height difference between the left and right subtrees and avoid tilting trees and other situations that tend to the evolution of the linear structure, the left and right subtrees of each node in the binary search tree are restricted. The height difference between the left and right subtrees is called the balance factor, and the absolute value of the balance factor of each node in the tree is not greater than 1.

The difficulty of balancing binary tree is how to keep the balance between left and right by left or right rotation when deleting or adding nodes.

The most common balanced binary tree in Java is the red-black tree, with red or black nodes, which maintain the balance of the binary tree 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. In other words, there can be no two adjacent red nodes on a path.

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

B-tree: a self-balanced binary search tree that optimizes read and write operations, which keeps the data orderly and has more than two subtrees. B-tree is used in database indexing technology.

⑥, heap

A heap can be thought of 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 less than the value of its parent node

The heap is always a complete binary tree.

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

⑦, figure

A graph is a complex nonlinear structure, which is composed of a finite non-empty set of vertices and a set of edges between vertices, which is usually expressed as: G (VMagne E), where G denotes a graph, V is the set of vertices in G, and E is the set of edges in G.

In the picture above, there are 4 vertices of V0 and V1, V2 and V3, and there are 5 edges between the 4 vertices.

In a linear structure, there is a unique linear relationship between data elements, and each data element (except the first and last) 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 upper layer (parent node) and multiple elements in the next layer (child node).

In the graphic structure, the relationship between nodes is arbitrary, and there is a possible correlation between any two data elements in the graph.

⑧, hash table

Hash table (Hash Table), also known as hash table, is a data structure that can be accessed directly through key code values (key-value). Its biggest feature is that it can quickly find, insert and delete.

The most important feature of arrays is that they are easy to find and difficult to insert and delete, while linked lists are just the opposite, which are difficult to find and easy to insert and delete. The hash table perfectly combines the advantages of both, and Java's HashMap adds the advantages of trees.

The hash function plays a key role in the hash table. it can transform an input of any length into a fixed-length output, which is the hash value. The hash function makes the access process of a data sequence more rapid and 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). Thus, the corresponding value of k can be directly obtained without traversing.

For any two different data blocks, the possibility of the same hash value is extremely small, that is, for a given data block, it is extremely difficult to find the same data block as its hash value. In addition, for a data block, even if you change only one bit of it, the hash value will be changed very much-this is the value of Hash!

Although it is highly unlikely, it will still happen. If there is a hash conflict, Java's HashMap will add the linked list to the same position in the array, and if the length of the linked list is greater than 8, it will be converted into a red-black tree for processing-this is the so-called zipper method (array + linked list).

To tell you the truth, if I make up for it at this pace, I feel bald, but if I can get stronger, it's worth it-- yes, it's worth it.

At this point, I believe you have a deeper understanding of "what are the common data structures in java?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.