What data structure is a linked list?

A linked list is a non-continuous and non-sequential storage structure on a physical storage unit. The logical order of data elements is realized through the pointer link order in the linked list; simply speaking, the linked storage structure of a linear list The generated table is called a "linked list". Each data element in the linked list is composed of two parts: 1. The information itself, called the "data field"; 2. The pointer to the direct successor, called the "pointer field". These two parts of information form the storage structure of data elements, which are called "nodes"; n nodes are linked to each other through pointer fields to form a linked list.

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

Data structure is the way a computer stores and organizes data. A data structure refers to a collection of data elements that have one or more specific relationships with each other. Often, carefully selected data structures can lead to higher operating or storage efficiency. Data structures are often related to efficient retrieval algorithms and indexing techniques.

The linked list in the data structure

The linked list is a non-linear physical storage unit. Continuous, non-sequential storage structure, the logical order of 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.

The data that are one after another in the logical structure are not next to each other like the sequence table when actually stored. On the contrary, data is randomly distributed in various locations in the memory. This storage structure is called linked storage of a linear list.

Due to decentralized storage, in order to reflect the logical relationship between data elements, each data element must be equipped with a pointer when it is stored to point to its direct successor element, that is, each data element. Both point to the next data element (the last one points to NULL (empty)).

As shown in the figure above, when each data element is linked to its next data element with a pointer, a chain is formed, and the head of the chain is Located in the first data element, this storage method is chain storage.

The table generated by the linked storage structure of the linear table is called a "linked list".

The composition of data elements in the linked list

Each element itself consists of two parts:

• itself Information is called the "data field";

• The pointer pointing to the immediate successor is called the "pointer field".

These two parts of information constitute the storage structure of data elements, which are called "nodes". n nodes are linked to each other through pointer fields to form a linked list.

Head node, head pointer and first node

Head node: Sometimes, at the first point in the linked list An additional node will be added before the node. The data field of the node generally does not store data (in some cases, it can also store information such as the length of the linked list). This node is called the head node.

If the pointer field of the head node is empty (NULL), it indicates that the linked list is an empty list. The head node is not necessary for the linked list. When dealing with certain problems, adding a head node to the linked list will make the problem simpler.

Head node: The node where the first element in the linked list is located. It is the first node after the head node.

Head pointer: always points to the position of the first node in the linked list (if the linked list has a head node, the head pointer points to the head node; otherwise, the head pointer points to the first node).

The difference between head node and head pointer: The head pointer is a pointer, which points to the head node or first node of the linked list; the head node is an actual node, which Contains data field and pointer field. The direct manifestation of the two in the program is that the head pointer is only declared but no storage space is allocated, and the head node is declared and the actual physical memory of a node is allocated.

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 computer memory space and achieve flexible memory dynamics. manage. 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.

Features

The linked storage representation of a linear table is characterized by using a set of arbitrary storage units to store the data elements of the linear table (this set of storage units can be continuous or discontinuous). 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 parts of information form a "node" (as shown in the figure below), 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.

According to 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.

Inserting and removing nodes from linked lists

Linked lists allow the insertion and removal of nodes at any position on the table, but do not allow random access.

1. Insert a node into the linked list

• Insert the head node into the linked list, which is divided into three types according to the insertion position:

• Insert into the head of the linked list, that is, between the head node and the first node;

• Insert into a certain position in the middle of the linked list;

• Insert to the end of the linked list;

##Although the insertion position is different, the same insertion method is used. It is divided into two steps, as shown in the figure above:

• Point the next pointer of the new node to the node after the insertion position;

• The next pointer of the node before the insertion position points to the insertion node;

Tip: When doing the insertion operation, you must first find the previous node at the insertion position. In Figure 4, also That is to find node 1, and the corresponding node 2 can be represented by the next pointer of node 1. In this way, step 1 is performed first, and then step 2 is performed. There is no need to add other auxiliary pointers during the implementation process.

2. Delete a node from the linked list

When you need to delete a node from the linked list, you need to perform two steps:

• Remove the node from the linked list;

• Manually release the node and recycle the memory space occupied by the node;

More related For knowledge, please visit the

FAQ column!

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