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

We learned about sequential storage structure linear tables before, although it is very powerful. But there is one drawback that is not a disadvantage: when inserting and deleting. A large number of elements need to be moved. So how to solve this problem? What we directly think of is to leave a space between the data elements, so it will be convenient to insert later. Then a question arises: how much space should be set aside? At one extreme, we need to insert n elements. In other words, this space needs to be reserved for infinity, so this must be unrealistic.

Here comes what we're going to talk about in this section: chained storage. Let's take a look at the definition of chained storage: in order to represent the logical relationship between each data element and the immediate successor element; the data element needs to store direct successor information in addition to its own information. As follows

Let's take a look at the chain storage logic structure, which is a linear table based on the chain storage structure, and each node contains a data field and a pointer field. The data domain refers to the rough data element itself, while the pointer domain refers to the address where the adjacent nodes are stored. The relationship is as follows

The sequential table refers to the linear table based on the sequential storage structure, and the linked list refers to the linear table based on the linked storage mechanism. There are three kinds of linked lists: a > single linked list, that is, no and nodes only contain the address information that directly succeeds; b > cyclic linked list, that is, the direct succession of the last node in the single linked list is the first node; c > two-way linked list, that is, the node in the single linked list contains the address information of the precursor and successor of beriberi.

Let's take a look at the basic concepts in the linked list: a, head node. A secondary node in a linked list that contains a pointer to the first data element; B. data node. The node that represents the data element in the linked list is expressed in the form of (data element, address), C, tail node. The last data node in the linked list contains empty address information. So how are nodes in a single linked list defined? As follows

Let's take a look at the internal structure of the single linked list, as follows

The meaning of the header node in the single linked list is to assist the positioning of data elements to facilitate insert and delete operations; therefore, there are no actual data elements stored in the header node. So how do you insert data elements at the target location? 1. Start from the beginning node and locate to the target location through the current pointer; 2. Apply for a new Node node from the heap space; 3. Perform the same operation: node- > value = e; node- > next = current- > next; current- > next = node;. Delete data elements at the target location: 1. Start from the start node and locate to the target location through the current pointer; 2. Use the toDel pointer to point to the node to be deleted 3. Perform actions: toDel = current- > next; current- > next = toDel- > next; delete toDel

Through today's study of the linked storage structure of the linear table, it is summarized as follows: 1, the data elements in the linked list are adjacent at noon in the physical memory; 2, the nodes in the linked list contain data fields and pointer fields; 3, the header nodes are used to assist the positioning of data elements to facilitate insert and delete operations; 4, insert and delete operations need to ensure the integrity of the linked list.

Qixi Festival Valentine's Day today, I wish you all a happy Qixi Festival!

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.