A linked list is a linear list stored in what storage structure

The linked list is a linear list stored in a "chained" storage structure. The storage unit addresses occupied by the data elements of the linked list can be continuous or discontinuous. The corresponding storage space can be temporarily and dynamically allocated as needed. The logical relationship between the data elements can be expressed as a "chain" .

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

In order to overcome the shortcomings of the sequential table storage structure, make full use of storage space and improve operating efficiency, linear tables can use another storage structure - Linked storage structure. The linked storage structure of the linear list is referred to as "link list"

1. Overview of the linked list

The storage unit addresses occupied by the data elements of the linked list can be consecutive , or it can be discontinuous, and the corresponding storage space can be temporarily and dynamically allocated as needed. The logical relationship between data elements can be expressed as a "chain".

Insertion and deletion of linked lists do not require moving data elements, only the chain needs to be modified.

Classification of linked lists:

1. Classification according to the method of linked list memory allocation

①Dynamic linked list

②Static linked list

2 .Classified by linking method

①Singly linked list

②Circular linked list

③Double linked list

(They are all dynamic linked lists)

2. Definition of singly linked list

1. Definition

In order to express the logical relationship between each data element ai and its direct successor data element ai 1, for each data element ai, except In addition to storing its own information, it is also necessary to store information indicating its direct successor (successor storage location-address).

The field that stores data element information is called data field, and the field that stores the immediate successor position is called pointer field, the information stored in the pointer domain is called a pointer or chain.

These two parts of information constitute the storage image of the data element ai, which is called node.

n nodes are linked into a linked list, which is the linked storage structure of a linear list (a1, a2, a3,...,an), because each node of the linked list only contains one pointer Domain, so it is called single linked list.

For linear lists, there is always a head and a tail, and linked lists are no exception. The pointer to the first node of the singly linked list in the linked list is called the head pointer. Access to the entire linked list must start from the head pointer, and each subsequent node The points are the positions pointed by the successor pointers of the previous node. The pointer of the last node of the linked list is "empty (usually represented by NULL)" - a null pointer.

In order to facilitate the implementation of various operations on the linked list, a node of the same type is set before the first data node of the singly linked list. This node is called the head node.

The data field of the head node can store a special flag information such as the length of the linked list, or it can not store any data.

The first data node and the last node of the linked list are also called head node and tail node.

2. The similarities and differences between the head pointer and the head node

Head pointer:

• The head pointer refers to the linked list A pointer to the first node. If the linked list has a head node, it is a pointer to the head node.
• The head pointer has an identification function, and the head pointer is often used as the name of the linked list.
• No matter whether the linked list is empty or not, the head pointer is not empty. The head pointer is a necessary element of the linked list.

Head node:

• The head node is established for the unification and convenience of operations. It is placed before the node of the first element, and its data field Generally unintentional.
• With the head node, the operations of inserting a node before the first element node and deleting the first node are unified with those of other nodes.
• The head node is not necessarily a necessary element of the linked list.

3. Code demonstration

/*线性表的单链表存储结构*/
/*结点定义*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*单链表定义*/
typedef struct Node *LinkList;

3. Operation of singly linked list

1. Insertion operation

1) Insertion simulation

Assume that the node storing element e is s, insert s into ai How to operate behind the node?

Thinking: Can the two inserted codes be exchanged?

No, if you switch it over, the subsequent elements such as ai 1 cannot be found, because the pointer field of s does not point to the address of ai 1.

2) Algorithm idea of ​​inserting the i-th data into the node of a singly linked list

• Declare a node p pointing to the first node of the linked list, initialize j=1;
• When j
• If p is empty at the end of the linked list, it means that the i-th element Does not exist; if the search is successful, generate an empty node s (using the malloc function)
• Assign the data element e to s->data, which is s->data=e;
• Insert standard statement: s->next=p->next;p->next=s;
• Return successfully.

2. Delete operation

1) Delete simulation

Assume that the node storing element ai is q, and the operation of deleting node q from a singly linked list is to be implemented .

2) Algorithm idea of ​​deleting the i-th data node in a singly linked list

• Declare a node p pointing to the first node of the linked list point, initialize j=1;
• When j
• If p reaches the end of the linked list If it is empty, it means that the i-th element does not exist; if the search is successful, the node p->next will be deleted and assigned to q
• . Insert the standard statement: p->next=q->next;
• Assign the q node to e, that is, e=q->data;
• Release the q node
• Return successfully.

4. Comparison between singly linked list structure and sequential table structure

Storage method:

• The sequential table uses a continuous storage unit to store the linear table in sequence The data elements
• Singly linked list adopts a linked storage structure, and uses a set of arbitrary storage units to store linear table elements

Time performance:

①Search

• Sequence table O(1)
• Singly linked listO(n)

②Insertion and deletion

• Sequence table O (n)
• Singly linked list O(1)

Space performance:

• The sequence table requires pre-allocated storage space. If it is too large, it will be a waste. If it is too small, it will easily cause overflow
• Singly linked lists do not need to pre-allocate storage space, as much as needed can be allocated, and the number of elements is not limited

For more related knowledge, please visit FAQ column!

The above is the detailed content of A linked list is a linear list stored in what storage structure. For more information, please follow other related articles on the PHP Chinese website!