Hey, Nuggets, I’m the Silent King.

Today we come to learn about data structure knowledge, very useful for solid Java basic skills, learned to have a sense of their own boss, hey hey. Data Structure, also known as Data Structure, is a Structure for storing Data. There is a certain relationship between Data and Data, including the logical relationship of Data, the storage relationship of Data and the operation relationship of Data.

In Java, data structures generally fall into two broad categories: linear and nonlinear. Ha ha, this non character has a soul, right?

Let’s start with linear data structures.

1) array

String [], int []; There are also things to look at, such as ArrayList, which encapsulates arrays internally.

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

Suppose you now have an ArrayList and are ready to add an element 55 to the fourth location (subscript 3).

At this point, elements after the fifth position in the ArrayList will be moved backwards.

I’m going to remove 23 from the ArrayList.

The elements with subscripts 7, 8, and 9 move forward.

A brief summary of the time complexity of ArrayList can be used as a reference for learning.

1. The time complexity of accessing an element via the subscript (get(int index)) is O(1), because it is direct, no matter how many times the data is increased, the time is the same.

2. Adding an element (i.e. Add ()) takes O(1) because it is added directly to the end.

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

The time complexity of finding an unsorted list is O(n), because the list is traversed; Searching sorted lists takes O(log n) time, because binary search methods can be used, and when the data increases by n times, the time increases by logn times (log base 2 here, eliminating half of the possibilities for each search).

2) list

Linked lists are discontinuous in physical storage space, but each node either knows who its next node is, or who its last node is, as if we are separated by thousands of mountains and rivers, but have a little link in mind. LinkedList is one of the most typical linked-list structures, linked by reference.

Each element in the LinkedList is called a Node, and each Node contains three items: the element itself, the reference address to the next element, and the reference address to the previous element.

LinkedList looks something like this:

  • The first node has no previous node, so prev is null;
  • The last node is null because there is no next node.
  • This is a bidirectional linked list, where each node is made up of three parts, front and back nodes and values.

LinkedList has the following advantages over ArrayList:

1. LinkedList allows memory to be allocated dynamically, which means memory allocation is done by the compiler at runtime and we do not need to specify the size at LinkedList declaration time.

2. LinkedList does not need to store elements in contiguous locations because nodes can specify the next or previous node by reference. That is, the LinkedList is cheap to insert and delete because there is no need to move other elements, just update the reference addresses of the previous node and the one after it.

3) stack

A stack is a very useful data structure, like a stack of plates, with the first on the bottom, the second on top, the third on top, and the last on top. The stack follows the Last In, First Out principle, or “Last In First Out” (LIFO) — the Last one In, the First one Out.

For a data structure like stack, there are two common actions:

  • I prefer to call it “push”. It’s very vivid. When we want to put a piece of data at the top of the stack, the action is called push.

  • Pop, also, I prefer to call it “pop”, with a strong animation effect, right? When we remove a piece of data from the stack, the action is called pop.

4) queue

Queue, which only allows data to be added at the end of the queue and removed at the beginning of the queue. Queues appear very frequently in Java, and there are different classes to meet the needs of different scenarios. Like PriorityQueue, DelayQueue, etc. The queue follows First In First Out, or FIFO, which means First In First Out, the First person In the queue comes Out First.

Now nonlinear data structures.

1) the tree

Tree is a typical nonlinear structure, which consists of n (N >0) finite nodes. It’s called a tree because the data structure looks like an upside-down tree, with roots at the top and leaves at the bottom. Tree data structures have the following characteristics:

  • Each node has limited or no children.
  • A node without a parent is called the root node.
  • Each non-root node has one and only one parent;
  • In addition to the root node, each child node can be divided into multiple disjoint subtrees.

The following figure shows some tree terminology:

The root node is layer 0, its children are layer 1, their children are layer 2, and so on.

  • Depth: For any node n, the depth of n is the length of the unique path from the root to n, and the depth of the 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 types:

1. Normal tree: No constraints on child nodes.

! [](https://upload-images.jianshu.io/upload_images/1179389-d15d9d09bbf4b809? imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)Copy the code

2. Binary tree: A tree with a maximum of two children per node. The binary tree can be divided into many kinds according to different forms.

2.1 Ordinary binary tree: a binary tree in which the parent of each child node does not necessarily have two children.

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

2.3 Full binary tree: a binary tree with the maximum number of nodes in each layer. There are two representations. In the first case, as shown in the figure below (each layer is full), the number of nodes satisfying each layer reaches a maximum of 2.

Binary Search Tree: Binary Search Tree (BST)

  • The left subtree of any node is not empty, and the value of all nodes in 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 in the right subtree is greater than the value of its root node.
  • The left and right subtrees of any node are binary search trees respectively.

3.1 Balanced binary tree: 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, also known as AVL tree according to the Scientist’s English name, was proposed by the former Soviet Union mathematicians AD Else-Velskil and Landis in 1962.

Balanced binary tree is essentially a binary search tree, but in order to limit the difference in height between the left and right subtrees, avoid the tilt tree tend to linear structure evolution, so for every node in the binary search tree of left and right subtrees limit, difference in height between the left and right subtrees called equilibrium factor, the balance of each node in the tree factors of absolute value is not greater than 1.

The difficulty of balancing binary trees is how to keep the balance between left and right rotation when nodes are deleted or added.

Red-black tree is a common balanced binary tree with red or black nodes. The balance of the binary tree is maintained by color constraints:

  • 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 children are black. That is, two adjacent red nodes cannot appear on the same 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, keeps data in order and has more than two subtrees.

5. B+ tree: A variant of the B tree.

TreeNode in HashMap uses red-black trees, while B trees and B+ trees are typical applications in database indexing principles.

2) Hash table

A Hash Table, also known as a Hash Table, is a data structure that can be accessed directly by key-value. Its biggest feature is that it can be quickly searched, inserted, and deleted. The algorithm we use is called hashing, and it takes an input of arbitrary length and turns it into an output of fixed length, and that output is the hash value. Hashing algorithms like MD5 and SHA1 are used.

Every Java object has a hash value, and the default is to calculate the memory address of the object + the key value of the object’s value by calling a local method to perform the hash algorithm.

The biggest characteristic of array is easy to find, insert and delete difficult; Linked lists, on the other hand, are difficult to find, and easy to insert and delete. Hash tables combine the best of both nicely, and Java’s HashMap adds the best of trees to that.

Hash tables have fast (constant level) query speed, and relatively fast add and delete speed, so it is suitable for use in the environment of massive data.

It is extremely unlikely that any two different blocks of data will have the same hash value, that is, for a given block of data, it is extremely difficult to find a block with the same hash value. Furthermore, if you change even one bit of a block of data, the Hash value can change dramatically — that’s why Hash exists!

Although extremely unlikely, it can still happen. If hashes collide, Java’s HashMap adds a list to the same location in the array, and if the list is larger than 8, it is converted to a red-black tree for processing — this is known as the zipper method (array + list).

Figure 3)

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

The figure above has four vertices, V0, V1, V2 and V3, with five edges between them.

In linear structure, there is a unique linear relationship between data elements, and every data element (except the first and last one) has a unique “precursor” 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 lower layer (child node).

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

PS: By the way, I would like to recommend a crash course in computer science that my sister and I both like. It is really good. If you want to go further in computer science, you must have a look at this course!

For more details on this course, check out this link

In short, no matter how to say, while young, learn more basic computer knowledge, or very sweet very good! I’m the silent king of learning and sharing. If this article is useful to you, please give it a thumbs up and we’ll see you next time