What is the concept and structure of linked list in Java data structure?

1. The concept of linked list

Concept:The linked list is a non-continuous and non-sequential storage structure in the physical storage structure. The logical order of the data elements is realized through the pointer link order in the linked list. ’s

1. A linked list consists of a series of nodes (each element in the linked list is called a node).

2. Nodes can be generated dynamically (malloc) at runtime.

3. Each node includes 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 (see 1.2 Node section for details).

4. Compared with the linear list sequence structure, the linked list operation is complicated. However, since it does not need to be stored in order, the linked list can achieve O(1) complexity when inserting, which is much faster than the sequential list; however, searching for a node or accessing a node with a specific number requires O(n) time, and The sequence list only requires O(1)

2. The node

linked list is composed of nodes, and each node is in the form of a structure. The first variables in the structure are given as needed. The last variable is a pointer of this structure type, which is used to store the first address of the next node‘

The linked list node is divided into two fields
Data field : Store various actual data
Pointer field : Store the address of the next node

(The picture shows a linked list with a sentinel header node)

3. Usage scenarios of linked lists

Linear tables are suitable for using linked storage structures when need to frequently insert or delete data elements.

Because for a linked list, inserting or deleting data only requires creating a node, inputting data, modifying the pointer to connect the node to a certain position in the linked list; and for a sequential list, inserting a Data may need to be moved to other data, which is highly complex.

4. Linked list classification and commonly used structures

Although there are a total of 8 types of linked lists to choose from, In practice, the most commonly used ones are headless one-way non-cyclic linked list and headed two-way cyclic linked list.

1. Headless one-way non-cyclic linked list: commonly known as "singly linked list". The structure is simple and is generally not used to store data alone. In fact, it is more of a substructure of other data structures (such as hash buckets, graph adjacency lists, stack chain structures, etc.)

2. Headed bidirectional circular linked list: the most complex structure, generally used Store data separately. Most of the linked lists actually used are headed bidirectional circular linked lists. Although the structure is the most complex, this structure brings many advantages.

5. Comparison with sequential list

Linked list: Linked list links discrete data into a table through nodes, and inserts and deletes nodes through operations. To achieve access to data.

Sequence table: The sequence table stores data by opening up a continuous memory (directly using an array or malloc and then realloc expansion).

But because realloc expansion is divided into in-situ expansion and off-site expansion, the former is less expensive, while the latter requires not only copying data, but also releasing old space when expanding. Furthermore, when expanding, it will usually be expanded to 2 times the original capacity. Expanding too many times will easily cause a waste of space.

Each member of the sequence table corresponds to a node of the linked list; members and nodes The data type can be a standard C type or a user-defined structure type.

Comparison object	Sequence list	Linked list
Storage space	Continuous	Discontinuous
Inserting or deleting data	It may be necessary to move data, complexity O (n)	Just need to modify the pointer
push	Dynamic sequence table: there is not enough space and needs to be expanded	No "capacity" ” concept, directly malloc the new node when pushing
Application	Requires frequent access	Requires frequent insertion and deletion of data

The above is the detailed content of What is the concept and structure of linked list in Java data structure?. For more information, please follow other related articles on the PHP Chinese website!