The data structure

An array of

  1. Arrays are declared on the stack, initialized on the heap

  2. Array objects are reference types and can be treated as objects. In Java, objects are in the heap, and arrays, whether they hold primitive types or other object types, are themselves in the heap

  3. When dealing with array elements, we usually use a base loop or a for-each loop.

The list

A linked list is a data structure, equivalent to an array.

Linked lists are inefficient in cyclic traversal, but have obvious advantages in insertion and deletion.

The Hash table

Data structures accessed directly based on Key values. That is, it accesses records by mapping key values to a location in the table to speed up lookups.

If the keyword is k, the value is stored in f(k). Thus, records can be obtained directly without comparison.

The stack

Is a special linear table that can only be inserted and deleted at one end.

It stores data on a “first in, last out” basis, with the first data pushed to the bottom of the stack and the last data at the top.

When data needs to be read, data is popped from the top of the stack (the last data is read first).

Inheriting from vector, thread-safe

The queue

It only allows deletions at the front of the table and insertions at the rear. Like stacks, queues are linear tables with limited operations.

A two-way queue can be inserted and deleted at both ends

The difference between a bidirectional queue and a bidirectional list: a bidirectional list can be inserted and deleted in the middle

Sort binary trees

First, if each node of the ordinary binary tree satisfies:

The values of all nodes in the left subtree are less than the root node, and the values of all nodes in the right subtree are greater than the root node.

Such a binary tree is a sorted binary tree

Red and black tree

Red Black Tree is a self-balanced binary search Tree

It can find, insert and delete in order log n time, where n is the number of elements in the tree

features

Each node is either black or red

The root node is black

Each leaf node (NIL) is black. [Note: leaf nodes are NIL or NULL leaf nodes!]

If a node is red, its children must be black.

All paths from a node to its descendants contain the same number of black nodes