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

This article mainly introduces the Internet linked list is a kind of linear table using what storage structure storage, the text is very detailed, has a certain reference value, interested friends must read!

A linked list is a linear list stored in a "chained" storage structure. The addresses of storage units occupied by the data elements of the linked list can be continuous or discontinuous, and the corresponding storage space can be temporarily and dynamically applied for allocation according to needs. The logical relationship between data elements can be expressed by "chain."

Operating environment: Windows 7, Dell G3 PC.

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

I. Overview of linked list

The addresses of storage units occupied by the data elements of the linked list can be continuous or discontinuous, and the corresponding storage space can be temporarily and dynamically applied for allocation according to needs. The logical relationship between data elements can be expressed by "chain."

The insertion and deletion of a linked list does not require moving data elements, but only modifying the chain.

Chain classification:

1. Classified by linked list memory allocation implementation

① Dynamic linked list

② Static linked list

2. Categories by link type

① Single strand list

② Circular linked list

③ Double-linked list

(They are all dynamic lists)

2. Definition of single-linked list 1. Definition

In order to represent the logical relationship between each data element ai and its immediate successor data element ai+1, it is necessary to store, for each data element ai, information indicating its immediate successor (storage location of successor-address) in addition to the information stored for itself.

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

These two pieces of information make up the storage map of data element ai, called a node.

The n nodes are linked into a linked list, i.e., a linear list (a1, a2, a3,..., An) chain storage structure, because each node of the linked list contains only one pointer field, so it is called a single-linked list.

For linear tables, there is always a head and tail, and linked lists are no exception. The pointer to the first node in the linked list is called the head pointer. The access of the whole linked list must start from the head pointer, and each node after that is the position pointed to by the subsequent pointer of the previous node. The pointer to the last node of the linked list is null (usually NULL)-null pointer.

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

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

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

2. Differences and similarities between head pointer and head node

Head pointer:

The first pointer is the pointer to the first node in the list, or if the list has a head node, the pointer to the head node.

The head pointer has an identification function, and the common head pointer is prefixed with the name of the linked list.

The head pointer is not empty, whether the linked list is empty or not. The head pointer is a necessary element of the linked list.

Head node:

The head node is set up for the unity and convenience of operation, placed before the node of the first element, and its data field is generally unintentional.

With the head node, the operations of inserting nodes 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/* Single-linked list storage structure of linear table *//* Node definition */typedef struct Node{ ElemType data; struct Node *next;}Node;/* Single-linked list definition */typedef struct Node *LinkList;

3. Operation of single-linked list 1. Insertion operation 1) Insertion simulation

Suppose the node storing element e is s, insert s after ai node, how to operate?

Thinking: Can two inserted codes be exchanged?

No, if reversed, it will cause the elements after ai+1 and so on not to be found, because the pointer field of s does not point to the address of ai+1.

2) Algorithm idea of inserting the ith data into the node of single-linked list

Declare a node p pointing to the first node of the list, initialize j=1;

When jdata, that is s->data=e;

Insert standard statements: s->next=p->next;p->next=s;

Return to success.

2. Delete operation 1) Delete simulation

If the node that stores the element ai is q, the operation of deleting the single-linked list from node q is to be implemented.

2) Algorithm idea of deleting ith data node in single-linked list

Declare a node p pointing to the first node of the list, initialize j=1;

When jnext is assigned to q

Insert standard statements: p->next=q->next;

If q is assigned to e, then e=q->data;

Release q node

Return to success.

IV. Comparison of single-chain list structure and sequence list structure

Storage method:

A sequential table stores the data elements of a linear table in sequence in a continuous memory cell

Single linked list adopts chain storage structure, and stores linear table elements with a group of arbitrary storage units.

Time performance:

① Search

O(1)

O(n)

② Insertion and deletion

O(n)

O(1)

Space performance:

Sequence table needs to pre-allocate storage space, large points, waste, small points easy to overflow

Single-linked lists do not require pre-allocation of storage space, as much as needed can be allocated, the number of elements is not limited

The above is "Internet linked list is a kind of linear table using what storage structure storage" all the contents of this article, thank you for reading! Hope to share the content to help everyone, more relevant knowledge, welcome to pay attention to 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.