Recently, in preparation for the interview, I reviewed the following knowledge points about the list and made a record of them. 65
FirstWhat is linked list?？
Linked storage linear list, referred to as linked list. A linked list consists of several linked list elements, which are called nodes. The nodes are logically connected to form a chain storage structure. Memory units that store nodes can be continuous or discontinuous. Logical connections have nothing to do with the order of physical storage.
The list is divided into two domains:
Range: Values used to store nodes
Chain Domain: Address or location used to store the next node
In terms of categorization of linked lists, it can be categorized according to the following two situations:
1、From the memory point of view: linked list can be divided into static linked list and dynamic linked list.
2、From the point of view of linked list storage mode, it can be divided into single linked list, double linked list and circular linked list.
Static linked list:
The elements of linear table are stored in arrays. These elements may be physically consecutive or not consecutive. They are connected by logical relations. Array units store linked list nodes. The chain domain of nodes points to the position of the next element, that is, the subscript of the array unit where the next element is located. displayStatic linked lists, however, need arrays to implement.
Problem raised: The problem of defining the length of an array cannot be prepaid.
Dynamic linked list: (most used in practice)
It improves the disadvantage of static linked list. It dynamically allocates storage units for nodes. When nodes are inserted, the system dynamically allocates space for nodes. When nodes are deleted, the corresponding storage unit should be released in time to prevent memory leakage.
Single linked list:
Single linked list is a structure of sequential storage.
There is a header node, no range, only a connected domain, which stores the address of the first node.
There is a endpoint, there is a range, there is also a chain domain, the chain domain value is always NULL.
Therefore, in order to find the first node or data element in a single linked list, the first node or data element must be found, and the first node must be known, or the whole linked list can not be accessed.
Circular linked list, similar to single linked list, is also a kind of chain storage structure. Circular linked list is performed by single chain. The chain domain of the last node of a single linked list points to NULL, while the establishment of a circular linked list does not require a dedicated header node, so that the chain domain of the last node points to the linked list node.
（The Difference between Circular List and Single List)
Distinction 1. Establishment of linked list. A single linked list needs to create a header node to store the address of the first node. The chain domain of a single list points to NULL. The establishment of a circular list does not require a dedicated header node, so that the chain domain of the last node points to the header node of the list.
Distinguish 2. Judgment of the end of the list. Single linked list judges whether the node is the end of the table, only needs to determine whether the link domain value of the node is NULL. If so, it is the end; otherwise it is not. Whether the circular list disk is the end point or not is to determine whether the chain domain of the node points to the head node of the list.
Double linked list:
Double linked list is also based on single linked list, single linked list is one-way, with a head node, a end node, to access any node, we must know the head node, can not go backwards. The double list adds a chain domain. Through two chain domains, they point to the front node and the back node respectively. In that case, yes.Access to its front and back nodes through any node of the double linked list. However, the double-linked list is not flexible enough. In practical programming, the circular double-linked list is commonly used. But the use of circular double linked list is more troublesome.
Author: Rendering the sentiment of pen and ink
Copyright Statement: This article is the original article of the blogger. Please attach a link to the blog article for reprinting.