©2020-2024 ioDraw All rights reserved
data structure ~01. Basic realization and concept of linear table
Definition of linear table :
A linear table is a finite sequence with the same characteristic data elements . The number of elements in the sequence is called the length of the linear table . General use n(n >= 0) To express . When n =
0 Time , The linear table is empty .
Storage structure of linear table :
The storage structure of linear table includes sequential storage structure and chain storage structure , Sequential storage structure is called sequential table . Linked storage structure is called linked list .
Comparison between sequential list and linked list
a Is the sequence table ,b For linked list
Sequence table
In the sequence table 7 The elements are next to each other , That is, it takes up a piece of space continuously . If you want to add or modify an existing element , It doesn't make it bigger , It's not going to decrease .
Sequential tables require continuous storage space , Storage allocation can only be done in advance . Once it's allocated , No matter how it is operated in the future, it will remain unchanged .
We can see in the picture , There is a table node space on the far right of the order table that is not used . If I want to insert elements in the middle , for instance B and C Insert a new element between , that C And the following elements will move back one position collectively , What about the linked list , It doesn't need to be so much trouble .
Structure definition of sequence table
#define MAXSIZE 10 // The initial size of the order table typedef struct { int data[MAXSIZE]; // An array to hold elements of the order table
int length; // Length of storage sequence table }List; // Definition of sequence table type
Linked list
The nodes of the linked list can be scattered anywhere in memory , And do not need to divide all the nodes required space to the linked list , It's a temporary division based on demand . therefore , Linked list supports dynamic allocation of storage space .
Each node in the linked list needs to reserve a part of space to store the pointer to the next node . The location of the current node in the linked list , Is indicated by the address in the precursor node , It is not determined by its offset from the initial position .
The insert operation of linked list does not need to move multiple elements , Just change the arrow indication .
Single chain list
In addition to the data domain contained in each node , It also contains a pointer field . Used to point to subsequent nodes .
The graph shows a single chain table with leading nodes
In the single chain list with leading nodes , Head pointer head Point to head node . The value range of the head node does not contain any information . Start storage from the successor node of the head node . Head pointer head Never equal to NULL. When head->next be equal to NULL When , The linked list is empty .
Single chain table of node definition
typedef struct node { int data; //data Data fields stored in struct node* next; // Pointer to the successor node }
Node;
Double linked list
You can only go from beginning to end in a single linked list , You can't go from the tail to the head . If the data sequence from the terminal node to the start node is required , The operation of single linked list is very troublesome . therefore , We have a double linked list .
Definition of double linked list node
typedef struct node { int data; //data Data fields stored in struct node* pre; // Pointer to the predecessor node
struct node* next; // Pointer to the successor node }Node;
Node structure diagram of single linked list and double linked list
a Is a single linked list ,b It is a double linked list
The final conclusion
Storage mode
The sequence table uses a group of storage units with continuous addresses to store data elements in turn , Elements are determined by the order of the elements Position between , Therefore, the utilization rate of storage space is high .
Single linked list uses a group of storage units with arbitrary address to store data elements , The section is determined by storing the address value of the next node Position between points , Therefore, the utilization rate of storage space is low .
Time performance comparison
The time complexity of sequential table lookup is O(1), Insert and delete elements that need to be moved , Therefore, the time complexity is O(n). If necessary
Search operations should be performed frequently , But insert and delete operations are rarely performed , Then it is recommended to use a sequence table .
The time complexity of linked list search is O(n), Insert and delete elements without moving them , Therefore, the time complexity is O(1). If necessary
Insert and delete operations should be performed frequently , However, the search operation is rarely carried out , Then it is recommended to use linked list .
Insert and delete nodes according to the ordinal number , You need to find the location of the inserted and deleted nodes by the ordinal number , So the whole The time complexity is
O(n). therefore , Linked list is suitable for insert and delete operations when the amount of data is small , If the amount of data stored is large , It is recommended to use binary tree or other data structure .
Space performance comparison
The sequence table needs to allocate a certain length of storage space in advance , If you don't know in advance the number of elements to be stored , Allocate space
Big will cause the waste of storage space , If the allocation space is too small, time-consuming expansion operation is needed .
Single linked list does not need fixed length storage space , Temporary allocation can be made according to the demand , As long as there is enough memory, it can be allocated , There is no limit to the number of elements stored in a linked list , No need to consider expansion operation .
Technology