Shulou(Shulou.com)06/02 Report--

This article focuses on "what are the general Java data structures". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the general Java data structures"?

1. Array

Arrays are fixed-size structures that can hold items of the same data type. It can be an integer array, a floating-point array, a string array, or even an array array (such as a two-dimensional array). The array is indexed, which means that random access can be made.

Array operation

Traversal: traverses all elements and prints them.

Insert: inserts one or more elements into an array.

Deleting: removing elements from an array

Search: search for elements in an array. You can search for an element by its value or index

Update: updates the value of an existing element at a given index

Application of array

Used as the basis for building other data structures, such as array lists, heaps, hash tables, vectors, and matrices.

Used for different sorting algorithms, such as insert sort, quick sort, bubble sort and merge sort.

two。 Linked list

A linked list is a sequential structure consisting of a sequence of linear sequential items linked to each other. Therefore, you must access the data sequentially and cannot access it randomly. Linked lists provide a simple and flexible representation of dynamic sets.

Let's consider the following terms related to linked lists. You can get a clear idea by referring to figure 2.

The elements in the linked list are called nodes.

Each node contains a key and a pointer to its successor (called next).

An attribute named head points to the first element of the linked list.

The last element of the linked list is called the tail.

Fig 2. Visualization of basic Terminology of Linked Lists

The following are the various types of linked lists available.

Single chain list-items can only be traversed in the positive direction.

Double linked list-you can traverse items in both forward and backward directions. The node consists of an additional pointer called previous, which points to the previous node.

Circular Link list-Link list where the previous pointer to the head points to the tail and the next pointer to the tail number points to the head.

Linked list operation

Search: find the first element with key k in a given linked list through a simple linear search and return a pointer to that element

Insert: insert a key in the list of links. Inserts can be done in three different ways: at the beginning of the list, at the end of the list, and then in the middle of the list.

Delete: removes element x from the given linked list. You cannot delete a node step by step. Deletion can be done in three different ways: delete from the beginning of the list, delete from the end of the list, and then delete from the middle of the list.

Application of linked list

Used for symbol table management in compiler design.

Used to switch between programs that use Alt Tab (implemented using circular linked lists).

3. Stack

The stack is a LIFO (last-in, first-out-the last placed element can be accessed first) structure, which is usually found in many programming languages. This structure is called a "stack" because it is similar to a real-world stack-a board stack.

Stack operation

Here are two basic operations that can be performed on the stack. Refer to figure 3 for a better understanding of stack operations.

Push push: inserts an element at the top of the stack.

Pop pop-up: delete the topmost element and return.

Fig 3. Visualization of basic Operations of Stacks

In addition, the following additional features are provided for the stack to check its status.

Peep peep: returns the top element of the stack without deleting it.

IsEmpty: check whether the stack is empty.

IsFull: check that the stack is full.

Application of stack

Used for expression evaluation (for example: shunting yard algorithm for parsing and evaluating mathematical expressions).

Used to implement function calls in recursive programming.

4. Queue

A queue is a FIFO (first-in, first-out-first-placed element that can be accessed first) structure, which is usually found in many programming languages. This structure is called a "queue" because it is similar to a queue in the real world-people wait in the queue.

Queue operation

Here are two basic operations that can be performed on the queue. Refer to figure 4 for a better understanding of stack operations.

Queuing: insert an element at the end of the queue.

Queuing: removes an element from the beginning of the queue.

Fig 4. Visualization of Basic Operations of Queues

Application of queues

Used to manage threads in multithreading.

Used to implement a queuing system (for example, priority queue).

5. Hash table

A hash table is a data structure that stores values with keys associated with each key. In addition, if we know the key associated with the value, it effectively supports lookup. Therefore, insertion and search are very effective regardless of the size of the data.

When stored in a table, direct addressing uses an one-to-one mapping between values and keys. However, this method is problematic when there are a large number of key-value pairs. The table will have many records and will be so large that it may be impractical or even impossible to store given the memory available on a typical computer. To avoid this problem, we use a hash table.

Hash function

A special function called hash function (h) is used to overcome the above problems in direct addressing.

In direct access, the value with the key k is stored in slot k. Using the hash function, we can calculate the index of the table (slot) that each value points to. The value calculated using the hash function of the given key is called the hash value, which represents the index of the table to which the value is mapped.

H: hash function

K: the key whose hash value should be determined

M: the size of the hash table (number of slots available). A prime of an exact power not close to 2 is a good choice for m.

Fig 5. Representation of a Hash Function

1 → 1 → 1

5 → 5 → 5

23 → 23 → 3

63 → 63 → 3

From the last two examples given above, we can see that conflicts occur when the hash function generates the same index for multiple keys. We can resolve conflicts by selecting the appropriate hash function h and using techniques such as linking and open addressing.

Application of hash table

Used to implement database indexing.

Used to implement associative arrays.

Used to implement the Settings data structure.

6. Tree

A tree is a hierarchical structure in which data is organized hierarchically and linked together. This structure is different from the link list, where items are linked in linear order.

In the past few decades, various types of trees have been developed to suit certain applications and meet certain restrictions. Some examples are binary search trees, B trees, red and black trees, expansion trees, AVL trees, and n-ary trees.

Binary search tree

As the name implies, a binary search tree (BST) is a binary tree in which data is organized in a hierarchical structure. This data structure stores values in sorted order, which we will examine in detail in this lesson.

Each node in the binary search tree contains the following attributes.

Key: the value stored in the node.

Left: pointer to the child on the left.

Right: the pointer to the correct child.

P: a pointer to the parent node.

The binary search tree has unique properties that can distinguish it from other trees. This property is called the binary-search-tree property.

Make x a node in the binary search tree.

If y is a node in the left subtree of x, then y.key ≤ x.key

If y is a node in the right subtree of x, then y.key ≥ x.key

Fig 6. Visualization of Basic Terminology of Trees.

Application of trees

Binary tree: used to implement expression parsers and expression solvers.

Binary search tree: used in many search applications that constantly input and output data.

Heap: used by JVM (Java virtual machine) to store Java objects.

Trap: for wireless networks.

7. Heap

Heap is a special case of a binary tree, in which the values of the parent node and its child nodes are compared and arranged accordingly.

Let's see how to represent the heap. Heaps can be represented using trees and arrays. Figures 7 and 8 show how we use binary trees and arrays to represent binary heaps.

Fig 7. Binary Tree Representation of a Heap

Fig 8. Array Representation of a Heap

There can be two types of heaps.

Minimum heap-the key of the parent is less than or equal to the key of the child. This is called the min-heap attribute. The root will contain the minimum value of the heap.

Maximum number of heaps-the key of the parent is greater than or equal to the key of the child. This is called the max-heap attribute. The root will contain the maximum value of the heap.

Application of reactor

Used to implement priority queues because priority values can be sorted according to heap properties.

Heap can be used to implement the queue function in O (log n) time.

Used to find the k minimum (or maximum) values in a given array.

Used for heap sorting algorithms.

8. Figure

A graph consists of a finite set of vertices or nodes and a set of edges that connect these vertices.

The order of the graph is the number of vertices in the graph. The size of a graph is the number of edges in the graph.

If two nodes are connected to each other through the same side, they are called adjacent nodes.

Directed graph

If all edges of graph G have directions indicating what is the starting vertex and what is the ending vertex, the graph is called a directed graph.

We say (ugraine v) incidence from vertex u or away from vertex u, and then incident to or enter vertex v.

Self-loop: from the vertex to its own edge.

Undirected graph

If all edges of a graph G have no direction, it is called an undirected graph. It can be propagated in two ways between two vertices.

If a vertex is not connected to any other node in the graph, it is said to be isolated.

The application of graph

Used to represent social media networks. Each user is a vertex and an edge is created when the user connects.

Pages and links used to represent search engines. Pages on the Internet are linked to each other through hyperlinks. Each page is a vertex, and the hyperlink between two pages is an edge. Used for page ranking in Google.

Used to represent the location and alignment in the GPS. The position is the vertex and the route connecting the position is the edge. Used to calculate the shortest path between two locations.

At this point, I believe you have a deeper understanding of "what are the general Java data structures?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.