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 }
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 .