Contents of this article:

  • Data structure classification
  • 1, the array
  • 2, stack
  • 3, the queue
  • 4, list
  • 5, trees,
  • Hash table
  • 7, heap
  • 8, figure

Data structure classification

Data structure refers to the set of data elements which have one or more relations with each other and the composition of the relationship between the data elements in the set.

Commonly used data structures are: array, stack, linked list, queue, tree, graph, heap, hash table, etc., as shown in the figure:



Each type of data structure has a unique way of storing data. Here are their structures and advantages and disadvantages.

1, the array

An array is a structure in which multiple elements can be stored consecutively in memory. Allocation in memory is also continuous. Elements in an array are accessed by array subscripts, which start at 0. For example, the following code assigns 1 to the first element of the array.

Int [] data = new int[100]; data[0] = 1; 12Copy the code

Advantages: 1, according to the index query elements fast 2, according to the index traversal number group convenient

Disadvantages: 1, the size of the array is fixed, cannot be expanded 2, the array can only store one type of data 3, add, delete operation is slow, because other elements need to be moved.

Application scenario: Frequent query, small requirement on storage space, and few additions or deletions are required.

2, stack

A stack is a special linear table, which can only be operated on one end of the linear table. Operations are allowed at the top of the stack, but not at the bottom of the stack. The characteristics of the stack are: first in, last out, or last in, first out, the operation of putting an element from the top of the stack is called on the stack, and removing an element is called on the stack.



The stack is structured like a container, and the things that are put in first come out later, so the stack is often used to implement recursive energy scenarios, such as the Fibonacci sequence.

3, the queue

A queue, like a stack, is a linear table, except that it can add elements at one end and pull them out at the other, i.e., first-in, first-out. The operation of putting an element in from one end is called enqueuing, and taking an element out is called enqueuing, as shown in the following figure:



Usage scenario: Because of the characteristics of queue first in first out, it is very suitable for multi-threaded blocking queue management.

4, list

A linked list is a discontinuous, non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by the pointer address of the linked list. Each element contains two nodes, one is the data domain (memory space) where the element is stored, and the other is the pointer domain pointing to the address of the next node. According to the point of the pointer, linked lists can form different structures, such as single linked lists, bidirectional linked lists, circular linked lists, etc.



Advantages of linked lists:

Linked list is a very common data structure, no need to initialize the capacity, can arbitrarily add and subtract elements;

When adding or deleting elements, you only need to change the pointer field of the node before and after the two elements to point to the address, so adding and deleting quickly;

Disadvantages: Because it contains a large number of pointer fields, it takes up large space; Finding elements requires traversing the linked list to find them, which is time-consuming.

Application scenario: A small amount of data needs to be added frequently and deleted

5, trees,

Tree is a kind of data structure, which is composed of N (N >=1) finite nodes to form a set with hierarchical relationship. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down. It has the following characteristics:

  • Each node has zero or more child nodes;
  • 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.

In everyday applications, we talk about and use more of one of the structures of trees, which isBinary tree.



Binary tree is a special kind of tree, which has the following characteristics:

1. Each node has at most two subtrees, and the degree of the node is at most 2. 2. The left and right subtrees are ordered and cannot be reversed. 3. Even if a node has only one subtree, distinguish between left and right subtrees.

Binary tree is a useful compromise scheme, it adds and deletes elements quickly, and also has a lot of algorithm optimization in the search aspect, so, binary tree has both the benefits of linked list, but also has the benefits of array, is the optimization scheme of both, is very useful in dealing with large quantities of dynamic data.

Extension: binary tree has a lot of extended data structures, including balanced binary tree, red black tree, B+ tree, etc., these data structures derived from the binary tree on the basis of a lot of functions, widely used in practical applications, such as mysql database index structure is B+ tree, and HashMap source code used in the red black tree. These binary trees are powerful, but algorithmically complex, and it takes time to learn.

Hash table

A hash table, also known as a hash table, is a data structure that is accessed directly by key and value. The key and value are mapped to a location in the set, so that the corresponding elements in the set can be found quickly.

Record storage location =f(key)

F is a hash function, and a hash function converts a Key to an integer number through a fixed algorithmic function called a hash function, and then modulates that number to the length of the array. The result is the index of the array. The value is stored in the array space with the number as the subscript. This storage space can take full advantage of array lookup to find elements, so the search is fast.

Hash table is also quite common in applications. For example, some set classes in Java are constructed based on hash principles, such as HashMap and HashTable. It is very convenient to find elements of sets by using the advantages of hash table. Adding and removing elements is slow, so a lot of times you need to use an array linked list, which is the zipper method. The zipper method is a kind of structure of array combined linked list, which is used in the underlying storage of the earlier hashMap. Until jdK1.8, the structure is changed to array plus red-black tree. The example figure is as follows:



Each member of the array contains a pointer to the head of a linked list, which may be empty or have many elements. We assign elements to different linked lists based on some characteristics of the elements, and also based on these characteristics, find the correct linked list, and then find the element from the linked list.

There are many application scenarios of hash table, of course, there are also many problems to consider, such as the problem of hash conflict, if not handled well will waste a lot of time, resulting in application crash.

7, heap

A heap is a special data structure that can be viewed as an array object of a tree with the following properties:

  • The value of a node in the heap is always no greater than or less than its parent;
  • The heap is always a complete binary tree.

The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap. Common heap have binary heap, Fibonacci heap and so on.

A heap is defined as follows: a sequence of N elements {k1,k2,ki… Kn} is called a heap if and only if the following relation is satisfied.

(< = k2i, ki ki < = k2i + 1) or (ki > = k2i, ki > = k2i + 1), (I = 1, 2, 3, 4… N /2), the expression satisfying the former becomes the small top heap, and the expression satisfying the latter is the large top heap. The structure diagram of the two can be arranged by complete binary tree, as shown in the following example:



Because of the characteristics of heap order, generally used to do the array sort, called heap sort.

8, figure

A graph consists of a finite set V of nodes and a set E of edges. In order to be different from tree structure, nodes are often called vertices in graph structure, edges are ordered pairs of vertices, and if there is an edge between two vertices, it means that the two vertices have adjacent relationship.

According to the direction of vertex pointing, it can be divided into undirected graph and directed graph:





Graph is a more complex data structure, in the storage of data has a more complex and efficient algorithm, respectively, there are adjacency matrix, adjacency list, cross linked list, adjacency multiple list, edge set number group and other storage structures, here do not expand, readers are interested in learning in-depth.

The original link: blog.csdn.net/yeyazhishan…