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

In this issue, the editor will bring you about what is a linked list. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

The linked list is a non-continuous and non-sequential storage structure on the physical storage unit, and the logical order of data elements is realized by 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 node can be generated dynamically at run time. Each node consists of two parts: one is the data field in which the data elements are stored, and the other is the pointer domain in which the address of the next node is stored. Compared with the sequential structure of linear table, the operation is complex. Because it does not have to be stored sequentially, linked lists can achieve O (1) complexity when inserting, which is much faster than another linear table sequential table, but it takes O (n) time to find a node or access a specific numbered node, while the corresponding time complexity of linear table and sequential table is O (logn) and O (1), respectively.

Using the linked list structure can overcome the disadvantage that the array linked list needs to know the data size in advance, and the linked list structure can make full use of the computer memory space to realize flexible memory dynamic management. However, the linked list loses the advantage of random reading of the array, and the linked list has a large space overhead due to the increase of the pointer domain of the node. The most obvious advantage of linked lists is that regular arrays may arrange associated items differently from the order of these data items on memory or disk, and data access often has to be converted in a different order. Linked lists allow you to insert and remove nodes anywhere on the table, but do not allow random access. There are many different types of linked lists: unidirectional linked lists, two-way linked lists, and circular linked lists. Linked lists can be implemented in many programming languages. Linked list access and manipulation are included in the built-in data types of languages such as Lisp and Scheme. Programming languages or object-oriented languages such as Cpene Clipper + and Java rely on mutable tools to generate linked lists.

Characteristics

The chained storage representation of a linear table is characterized by using an arbitrary set of storage units to store the data elements of a linear table (which can be continuous or discontiguous). Therefore, in order to represent the logical relationship between each data element and its immediate successor, for a data element, in addition to storing its own information, it is also necessary to store information indicating its direct successor (that is, the storage location of the direct successor). These two pieces of information form a "node" (as shown in the figure next to the overview) that represents a data element in a linear table. The linked storage of linear tables shows that one disadvantage 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 attached to the edges, because the points and edges of the linked list are basically one-to-one (except for the first or last node, but there are no special cases). One exception, however, is that if the linked list supports reversing the front and back pointers in a segment of the linked list, the reverse tag may be more convenient to add to the edge.

For non-linear linked lists, you can see other relevant data structures, such as trees and graphs. In addition, there is a data structure based on multiple linear linked lists: jump table, insert, delete, search and other basic operations can reach O (nlogn), the same as the balanced binary tree.

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

Represented by, respectively, The linked list composed of N nodes in turn is called the linked storage representation of linear list. Because each node of this kind of linked list contains only one pointer domain, it is also called single linked list or linear linked list.

The above is the editor for you to share what is a linked list, if you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

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.