What are the java data structures?

Java data structures include: 1. List; 2. Vector; 3. ArrayList; 4. LinkedList; 5. Set; 6. HashSet; 7. LinkedHashSet; 8. SortedSet; 9. Map; 10. HashMap .

The operating environment of this article: windows10 system, java 1.8, thinkpad t480 computer.

There are several commonly used data structures in Java, which are mainly divided into two main interfaces: Collection and map (the interface only provides methods and does not provide implementation), and the data structures ultimately used in the program are inherited from these The data structure class of the interface.

Collection---->Collections   
Map----->SortedMap------>TreeMap          Map------>HashMap
Collection---->List----->(Vector \ ArryList \ LinkedList)
Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)

List (interface)

List is an ordered Collection. Use this interface to accurately control the insertion position of each element. Users can use the index (the position of the element in the List, similar to the array subscript) to access the elements in the List, which is similar to Java arrays.

Vector

List based on array (Array) actually encapsulates some functions that arrays do not have for us to use, so it is difficult to avoid the limitations of arrays, and the performance is also impossible Beyond arrays. Therefore, where possible, we should use arrays more. Another very important point is that Vector is thread synchronized (sychronized), which is also an important difference between Vector and ArrayList.

ArrayList

Like Vector, it is a linked list based on an array, but the difference is that ArrayList is not synchronized. Therefore, it is better than Vector in terms of performance, but when running in a multi-threaded environment, you need to manage the synchronization of threads yourself.

LinkedList

LinkedList is different from the previous two Lists. It is not based on arrays, so it is not limited by array performance.

Each node (Node) contains two aspects of content:

1. The data of the node itself;

2. The information of the next node ( nextNode).

So when adding and deleting actions to LinkedList, you don’t have to move a lot of data like array-based ArrayList. This can be achieved by simply changing the relevant information of nextNode. This is the advantage of LinkedList.

List Summary

All Lists can only hold tables composed of a single object of different types, not Key-Value pairs. For example: [tom,1,c]

All Lists can have the same elements, for example, Vector can have [tom,koo,too,koo]

All Lists can have There are null elements, such as [tom,null,1]

Array-based List (Vector, ArrayList) is suitable for query, while LinkedList is suitable for addition and deletion operations

Set (interface)

Set is a Collection that does not contain repeated elements

HashSet

Although Set and List both implement the Collection interface, their implementation methods are quite different. List is basically based on Array. But Set is implemented on the basis of HashMap. This is the fundamental difference between Set and List. The storage method of HashSet is to use the Key in HashMap as the corresponding storage item of Set. It will be clear at a glance if you look at the implementation of the add(Object obj) method of HashSet.

LinkedHashSet

A subclass of HashSet, a linked list.

SortedSet

Ordered Set is implemented through SortedMap.

Map (Interface)

Map is a container that associates key objects and value objects, and a value object can be a Map, and so on, thus forming a multiple level mapping. For key objects, like Set, the key objects in a Map container are not allowed to be repeated. This is to maintain the consistency of the search results; if there are two key objects that are the same, then you want to get the value object corresponding to that key object. There will be a problem. Maybe what you get is not the value object you thought, and the result will be confusion. Therefore, the uniqueness of the key is very important and is in line with the nature of the set.

Of course, during use, the value object corresponding to a certain key may change. In this case, the last modified value object will correspond to the key. There is no uniqueness requirement for value objects. You can map any number of keys to a value object without any problems (but it may cause inconvenience to your use. You don’t know what you are getting. is the value object corresponding to that key).

(Free video tutorial sharing: java video tutorial)

HashMap

Implementation of Map interface based on hash table. This implementation provides all optional mapping operations and allows null values ​​and null keys. (The HashMap class is much the same as a Hashtable, except that it is not synchronized and allows null.) This class does not guarantee the order of the map, and in particular it does not guarantee that the order is immutable. In addition, HashMap is not thread-safe, which means that there may be problems in a multi-threaded environment, while Hashtable is thread-safe.

TreeMap

TreeMap stores keys in order,

HashTable

(1) Hashtable is a hash table, and the content it stores is the key Value pair (key-value) mapping.

(2) Hashtable inherits from Dictionary and implements Map, Cloneable, and java.io.Serializable interfaces.

(3) Hashtable functions are all synchronous, which means it is thread-safe. Neither its key nor value can be null.

Differences between several commonly used classes

1. ArrayList: Single element, high efficiency, mostly used for query

2. Vector: Single element, thread-safe, mostly used for query

3. LinkedList: Single element, mostly used for insertion and deletion

4. HashMap: elements are in pairs, and elements can be empty

5. HashTable: Elements are in pairs, thread-safe, elements cannot be empty

Vector, ArrayList and LinkedList

In most cases, ArrayList is the best in terms of performance, but when the elements in the collection need LinkedList will perform better when inserting and deleting frequently, but the performance of the three of them is not as good as that of arrays. In addition, Vector is thread synchronized. Therefore:

If you can use an array (the element type is fixed and the array length is fixed), please try to use an array instead of List;

If there are no frequent deletion and insertion operations, there is no need to think too much For threading issues, give priority to ArrayList;

If used under multi-thread conditions, you can consider Vector;

If frequent deletions and insertions are required, LinkedList comes into play;

If you don’t know anything, there’s nothing wrong with using ArrayList.

Stack

The stack is a special linear list that can only be inserted and deleted at one end. It stores data according to the principle of first in, last out. The data that enters first is pushed to the bottom of the stack, and the last

data is on the top of the stack. When data needs to be read, data is popped from the top of the stack (the last data is pushed to the bottom of the stack). one read out).

Queue

A special linear table that only allows deletion operations at the front end of the table (front) and insertion operations at the back end (rear) of the table.

The end that performs the insertion operation is called the tail of the queue, and the end that performs the deletion operation is called the head of the queue. When there are no elements in the queue, it is called an empty queue.

Array

In programming, for the convenience of processing, several variables of the same type are organized in an ordered form. These collections of similar data elements arranged in order are called arrays. In C language, arrays are constructed data types. An array can be decomposed into multiple array elements, and these array elements can be basic data types or constructed types. Therefore, according to the type of array elements, arrays can be divided into various categories such as numerical arrays, character arrays, pointer arrays, and structure arrays.

Linked list

A non-continuous, non-sequential storage structure on physical storage units. The logical order of data elements is realized through the pointer link order in the linked list.

The linked list consists of a series of nodes (each element in the linked list is called a node), and the nodes can be dynamically generated at runtime. Each node consists of two parts:

One is the data field that stores data elements, and the other is the pointer field that stores the address of the next node.

Tree

A tree is a finite set K containing n (n>0) nodes, and a relationship N is defined in K. N satisfies the following conditions:

(1) There is and is only one node k0. It has no predecessor for the relationship N. K0 is called the root node of the tree. Referred to as the root (root)

(2) Except for K0, each node in k has and has only one predecessor for the relationship N.

(3) Each node in K can have m successors (m>=0) for the relationship N.

Heap

In computer science, a heap is a special tree data structure, each node has a value. Usually what we call the data structure of a heap refers to a binary heap. The characteristic of a heap is that the root node has the smallest (or largest) value, and the two subtrees of the root node are also a heap.

Hash table

If there is a record with the keyword equal to K in the structure, it must be at the storage location of f(K). Thus, the records being searched can be obtained directly without comparison. Call

this correspondence f a hash function (Hash function), and the table built based on this idea is a hash table.

Related recommendations:

The above is the detailed content of What are the java data structures?. For more information, please follow other related articles on the PHP Chinese website!