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

This article introduces the relevant knowledge of "what is Java linear data structure". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1) Array

You can tell at a glance, like String [], int [], and those that need two glances to see through (see the source code), such as ArrayList, which encapsulates the array internally.

The biggest advantage of the array data structure is that it can be operated according to the subscript (or index). When inserting, it can be inserted directly to a specific location according to the subscript, but at the same time, all the subsequent elements need to move backward. the more data you need to move, the more tired you will be.

Assuming that you already have an ArrayList, you are ready to add an element 55 to the fourth location (superscript 3).

The element after the fifth position in the ArrayList will move backward.

Prepare to remove 23 from ArrayList.

At this point, the elements with subscript 7, 8, 9 move forward.

Briefly summarize the time complexity of ArrayList, which is convenient for everyone to use as a reference when learning.

1. The time complexity of accessing an element through the subscript (that is, get (int index)) is O (1), because it is direct, and the time is constant no matter how many times the data is enlarged.

2. The time complexity of adding an element (that is, add ()) is O (1) because it is added directly to the end.

3. The time complexity of deleting an element is O (n), because to traverse the list, the amount of data increases several times and the time-consuming increases several times.

4. The time complexity of finding an unsorted list is O (n), because it is necessary to traverse the list; the time complexity of finding a sorted list is O (logn), because you can use binary search method, which increases the time-consuming logn times when the data is increased by n times (the log here is based on 2, so it is half possible to find it each time).

2) linked list

Linked lists are discontiguous in physical storage space, but each node either knows who its next node is or who its last node is, as if we are connected by thousands of mountains and rivers. For example, LinkedList is the most typical linked list structure, which is linked to each other by reference.

Every element in LinkedList can be called a Node, and each node contains three items: one is the element itself, the other is the reference address that points to the next element, and the third is the reference address that points to the previous element.

LinkedList looks like this:

The first node has no previous node, so prev is null

The last node has no latter node, so next is null

This is a two-way linked list, and each node is made up of three parts, front and back nodes and values.

Compared to ArrayList,LinkedList, it has the following advantages:

1. LinkedList allows memory to be allocated dynamically, which means that memory allocation is done by the compiler at run time, and we don't need to specify the size when LinkedList declares.

2. LinkedList does not need to store elements in consecutive locations, because nodes can specify the next node or the previous node by reference. In other words, LinkedList is cheap to insert and delete elements because you don't need to move other elements, you just need to update the reference addresses of the previous node and the next node.

3) Stack

The stack is a very useful data structure, like a stack of plates, the first on the bottom, the second on top of the first, the third on top of the second, and the last on top. The stack follows the last-in-first-out principle, that is, "Last In First Out" (LIFO for short)-the last to enter, the first to go out.

For a data structure such as a stack, it has two common actions:

There are many interpretations of push in Chinese. Personally, I prefer to call it "press in", which is very vivid. When we want to put a piece of data on top of the stack, this action is called push.

Pop, similarly, I personally prefer to call it "pop-up", with a very strong animation effect, isn't it? When we want to remove a data from the stack, this action is called pop.

4) queue

Queue, only data can be added at the end of the queue, and the head of the queue can remove the data. Queues appear very frequently in Java, and there are different classes to meet the needs of different scenarios. Such as priority queue PriorityQueue, delay queue DelayQueue, and so on. The queue follows First In First Out, abbreviated as FIFO, that is, first-in, first-out, and the first to enter the queue and the first to come out.

Let's talk about nonlinear data structures.

1) 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.

Trees can be subdivided into the following categories:

1. Ordinary tree: there are no constraints on child nodes.

2. Binary tree: a tree with at most two child nodes per node. Binary tree can be divided into many kinds according to different forms of expression.

2.1. Ordinary binary tree: the parent of each child node does not necessarily have a binary tree with two child nodes.

2.2. Complete binary tree: for a binary tree, its depth is assumed to be d (d > 1). With the exception of layer d, the number of nodes in each layer has reached its maximum, and all nodes in layer d are arranged closely and continuously from left to right.

2.3. 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.

3. Binary search tree: the English name is Binary Search Tree, that is, 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.

3.1. Balanced 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 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.

Red-black tree is a common balanced binary tree, the node is red or black, through color constraints to maintain the balance of the binary tree:

Each node can only be red or black.

The root node is black

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

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.

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

4. B-tree: a self-balanced binary search tree that optimizes read and write operations, which can keep the data in order and have more than two subtrees.

5. B + tree: a variant of B tree.

The TreeNode in HashMap uses the red-black tree, while B-tree and B + tree have typical applications in the index principle of the database.

2) 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 algorithm used is called hashing, which converts an input of any length into a fixed-length output, which is the hash value. For example, MD5 and SHA1 all use hashing algorithm.

Every Java object has a hash value. By default, the hash algorithm is executed by calling the local method to calculate the key code value of the object's memory address + the object's value.

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.

Hash table has a fast query speed (constant magnitude), as well as a relatively fast speed of adding and deleting, so it is very suitable to be used in the environment of massive data.

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).

3) 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.

This is the end of the content of "what is Java linear data structure". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.