What is a linked list

The linked list is a non-continuous and non-sequential storage structure on the physical storage unit. The logical order of the data elements is realized through the pointer link order in the linked list. A linked list consists of a series of nodes (each element in the linked list is called a node), and 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. Compared with the linear table sequence structure, the operation is complicated. Since it does not have to be stored in order, the linked list can achieve O(1) complexity when inserting, which is much faster than another linear list, sequential list, but finding a node or accessing a specific numbered node requires O(n) time, and the corresponding time complexities of linear tables and sequential tables are O(logn) and O(1) respectively.

Using the linked list structure can overcome the shortcoming of the array linked list that the data size needs to be known in advance. The linked list structure can make full use of the computer memory space and achieve flexible dynamic memory management. However, the linked list loses the advantage of random reading of the array, and at the same time, the space overhead of the linked list is relatively large due to the increase of the pointer field of the node. The most obvious benefit of a linked list is that the way a regular array arranges associated items may be different from the order in which these data items are arranged in memory or on disk, and access to data often requires switching between different arrangements. Linked lists allow insertion and removal of nodes at any location on the list, but do not allow random access. There are many different types of linked lists: one-way linked lists, doubly linked lists, and circular linked lists. Linked lists can be implemented in a variety of programming languages. The built-in data types of languages ​​like Lisp and Scheme include the access and operation of linked lists. Programming or object-oriented languages ​​such as C, C and Java rely on mutable tools to generate linked lists.

Features

The characteristic of the linked storage representation of a linear table is to use a set of arbitrary storage units to store the data elements of the linear table (this set of storage units can be continuous or different) continuously). Therefore, in order to represent the logical relationship between each data element and its direct successor data element, for the data element, in addition to storing its own information, it is also necessary to store information indicating its direct successor (that is, the storage of the direct successor Location). These two pieces of information form a "node" (as shown in the figure next to the overview), which represents a data element in the linear table. One disadvantage of the linked storage representation of linear tables is that to find a number, you have to start from scratch, which is very troublesome.

Depending on the situation, you can also design other extensions of the linked list yourself. However, data is generally not appended to the edges, because the points and edges of the linked list are basically in one-to-one correspondence (except for the first or last node, but no special circumstances will occur). However, a special case is that if the linked list supports reversing the front and back pointers in a section of the linked list, it may be more convenient to add a reverse mark to the edge.

For non-linear linked lists, you can refer to other related data structures, such as trees and graphs. There is also a data structure based on multiple linear linked lists: skip lists. The speed of basic operations such as insertion, deletion and search can reach O(nlogn), the same as a balanced binary tree.

The domain that stores data element information is called the data domain (let the domain name be data), and the domain that stores the direct successor storage location is called the pointer domain (let the domain name be next). The information stored in the pointer field is also called a pointer or chain.

A linked list consisting of N nodes that respectively represent,,..., are linked in sequence, is called a linked storage representation of a linear list, because each node of such a linked list only contains one pointer field , so it is also called a singly linked list or a linear linked list.

The above is the detailed content of What is a linked list. For more information, please follow other related articles on the PHP Chinese website!