Java Common Basic Data Structures

Directory Stack: Queue: Array: Linked List: Red and Black Tree: Summary

Stack:

stack Also known as stack, it is a linear table with limited operation, and its limitation is that it only allows insertion and deletion operations on the first side of the table, and does not allow addition, search, deletion and other operations at any other position.

Simply put, using the set of this structure, the access to elements has the following characteristics

1. First in and then out.

2. The entrance and exit of the stack are the top positions of the stack.

Pressing stack: It is to store elements, store elements to the top position of the stack, and the existing elements in the stack move one position to the bottom of the stack at a time.

Bomb stack: It is to take elements, take out the elements at the top of the stack, and the existing elements in the stack move one position to the top of the stack in turn.

Queue:

queue Queue for short, like Stack 1, is also a linear table with limited operations. Its limitation is that only insertions are allowed on one side of the table and deletions are allowed on the other side of the table.

Simply put, using the set of this structure, the access to elements has the following characteristics:

1. First in, first out

2. The entrance and exit of the queue occupy one side respectively, for example, the left side is the entrance and the right side is the exit

Array:

Array Is an ordered sequence of elements, and the array opens up a continuous space in memory, and stores elements in this space, so that the corresponding data can be quickly found through index.

Storing data in this way has the following characteristics:

1. Find elements quickly, and you can quickly access elements at specified positions through indexes.

2. Adding and deleting elements is slow. When adding elements at the specified index position, it is necessary to create a new array, store the specified new elements at the specified index position, and then copy the original array elements to the corresponding index position of the new array according to the index

To delete elements, it is necessary to create a new array, copy the elements of the original array to the corresponding index position of the new array according to the index, and do not copy the elements at the specified index position in the original array to the new array.

Linked list:

Linked List Consists of a series of nodes node, which can be dynamically generated at runtime. Each node consists of two parts: one is a data field for storing data elements, and the other is a pointer field for storing the address of the next node. Linked list is divided into one-way linked list and two-way linked list. Two-way linked list refers to the reference of the upper node and the pointer of the next node, while one-way linked list refers to the pointer of only the next node.

Simply put, using the collection of data structures, the storage of data has the following characteristics:

A plurality of nodes are connected by address. The query is slow. If you want to find an element, you need to look backward through the connected nodes in turn. Add and delete quickly, only need to modify the address of the next element.

Red and Black Trees:

2-tree: It is an ordered tree with no more than 2 nodes per node

Simply understand, a 2-tree is a tree structure with at most two subtrees per node. The top node is called the root node, and the two sides are called the left subtree and the right subtree.

The red-black tree itself is a 2-fork search number. After the node is inserted, the number is still a 2-fork search number, which means that the key values of the number are still orderly.

Constraints of red and black trees:

Nodes can be red or black The root node is black The leaf nodes are black The children of each red node are black The number of black nodes is the same on all paths from any 1 node to every 1 leaf node

Characteristics of red and black trees:

The speed is very fast, approaching the balanced tree, and the minimum and maximum times of finding leaf elements are no more than twice.

Summarize

That's all for this article. I hope I can help you, and I hope you can pay more attention to this site!