Data structures are divided into the following categories

An array of

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;Copy the code

Disadvantages: 1. The size of an array is fixed and cannot be expanded. 2. The array can only store one type of data. Application scenario: Frequent query, small requirement on storage space, and few additions or deletions are required.

The stack

Stacks are a special kindThe linear table, can only operate at one end of a linear table,To the top of the stackAllow operation,The bottom of the stackOperation is not allowed. The characteristics of the stack are:After the advancedOr ratherLast in, first outThe operation of putting an element from the top of the stack is calledInto the stackAnd pull out the element calledOut of the stack.

A stack is structured like a container, and the things that are put in first are taken out later, so a stack is often used in implementationsRecursive functionality canAspects of the scenario, such as the Fibonacci sequence. In our mobile development, the averagepushThere arepopThe controller

The queue

A queue, like a stack, is a linear table, except that it can add elements at one end and take them out at the other, i.e. :First in first out. The operation that puts an element in from one end is calledThe teamAnd extract elements asOut of the team, the sample figure is as follows:

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

The list

The listOn the physical storage unitThe continuous,The order of theStorage structure, the logical order of data elements is through linked listsPointer to the addressImplementation, eachThe elementcontainsThe two nodesOne is for storing elementsData fields(memory space), and the other point to the address of the next nodePointer to the domain. According to thePointer to theLinked lists can form different structures, for exampleSingly linked lists.Two-way linked list.Circular linked listAnd so on.

The list ofadvantages:The listIs a very common data structure,There is no need to initialize capacity, you canAdd or subtract elements arbitrarily; To add or remove an element, you only need to change the values of the nodes before and after the elementPointer fields point to addressesCan, so add, delete quickly;

disadvantages: Because it contains a lot ofPointer to the domain, occupy a large space; Finding elements requiresTraversing the listIt takes a lot of time.

Applicable scenario: A scenario in which a small amount of data needs to be added frequently and deleted

The tree

The treeIt is a kind ofThe data structure, it consists of n (n>=1)Limited nodeMake up a body ofHierarchical relationshipstheA collection of. 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;

There is noThe parent nodeIs calledThe root node;

eachThe root nodeThere is one and only oneThe parent node;

In addition toThe root node, eachChild nodesCan be divided into severaldisjointThe subtree;

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

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 table converts a Key into 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.

Using the advantages of hash tables, it is very convenient to find elements in collections. However, because hash tables are data structures derived from arrays, they are slow in adding and deleting elements. Therefore, it is often necessary to use an array linked list, namely the zipper method. The zipper method is a structure of array associative linked list, which is used in the underlying storage of the earlier hashMap.