In the previous article, we analyzed and discussed the principle and implementation of the sequential storage structure of the linear table. This article will analyze and discuss the realization principle of the chain storage structure of the linear table, another storage structure.

1, linear list chain storage structure

The chain storage structure stores the data elements of a linear table by linking the nodes that store the data elements with pointer fields. A pointer is a variable that points to the address of a physical storage unit. We call a structure consisting of a data element and one or more pointer fields a node. The data domain is used to store data elements and the pointer domain is used to construct the association between data elements. The characteristic of chain storage structure is that the logical relation between data elements is expressed in the link relation of nodes. A linear list with a chained storage structure is called a linked list. According to the different pointer fields and the different methods of node chain construction, linked lists are mainly divided into single linked list, single circular linked list and bidirectional circular linked list.

2. Single linked lists

In a singly linked list, the nodes that make up the list have only one pointer field that points to their immediate successors.

2.1 Representation method of single linked list

According to the above discussion, we can know the structure of each node in the single linked list as shown in the figure below:

The structure of a single linked list node can be defined as follows:

typedef struct Node{
    DataType   data;// Store data
    struct Node *next; // Store a pointer to the next element node
} SLNode;
Copy the code

Data is used to store data elements, and next is used to store Pointers to the next node. There are two types of single-linked lists: leading node and non-leading node. We put theA pointer to a single linked list is called a header pointer.The first node to which a header pointer points that does not hold data elements is called a header. Singly linked lists are usually constructed as singly linked lists of leading nodes. Singly linked lists without leading nodes are not discussed here. The figure below shows the structure of a single linked list of leading nodes.Head represents the head pointer, and the data field part of the head node is usually shaded on the graph to indicate that the node is the head node. The symbol “^” indicates a null pointer.A null pointer is used to indicate the end of the list. A NULL pointer is represented by NULL in the algorithm description. In the sequential storage structure, the array is used to store data elements. What the user requests from the system is a piece of memory space with contiguous addresses, so any two data elements that are logically adjacent are physically adjacent. Chain storage structure, initialized to an empty, whenever there is a need to store the new data elements, the user only apply to the system dynamic storage space needed to insert in the chain, and the application of the memory space is likely to be at a different time address is discontinuous, so in the chain store structure of arbitrary two adjacent logical data element in physics is not necessarily adjacent, The logical ordering of data elements is achieved through pointer links in the chain.

2.2 Operation realization of single linked list

2.2.1 initialize the ListInitiate(SLNode **head)

Each node in a singly linked list is requested from the system as needed, which is called a dynamic memory space request. The dynamically allocated memory space must be released by the applicant when it is no longer needed.

void ListInitiate(SLNode **head){
    *head = (SLNode *)malloc(sizeof(SLNode));// apply a header
    (*head)->next = NULL;
}
Copy the code

Before initialization, head does not have a specific address value. During initialization, head gets the specific address value, which is returned to the calling function. Therefore, head is designed to be the pointer type of the pointer.

2.2.2 Get the current number of elements ListLength(SLNode *head)
int  ListLength(SLNode *head){
    SLNode *p = head;
    int size = 0;
    while(p->next ! =NULL) {// When the next pointer field of a node is NULL, the table structure is terminated
        p = p->next;
        size++;
    }
    return size;
}
Copy the code
  1. Before the loop, the pointer variable p points to the head node and the count variable size is assigned 0.
  2. The loop ends with the condition p-> Next! = NULL, in the loop, each time the pointer p points to its value points to its successor, increment the count variable size by 1.
  3. The function returns the count variable size.
ListInsert(SLNode *head,int I,DataType x)

Insert the node of the data element X before the I (0≤ I ≤size0\leq I \leq size0≤ I ≤size) position of the singly linked list of the leading node, return 1 on success, return 0 on failure.

int ListInsert(SLNode *head,int i,DataType x){
    SLNode *p = head;
    int j = - 1;
    /* Find the previous node of the insertion position I -1*/
    while(p->next ! =NULL && j < i- 1){
        p = p->next;
        j++;
    }
    if(j ! = i- 1) {printf("Insert position parameter error");
        return 0;
    }
    SLNode *q = (SLNode *)malloc(sizeof(SLNode));// Create a new node
    q->data = x;// Assign the value of x to the new node

    q->next = p->next;// The pointer to the new node points to node I
    p->next = q;// change the pointer field of p to point to the new node
    return 1;
}
Copy the code
  1. Firstly, the i-1 node is found in the single linked list and indicated by the pointer P.
  2. Dynamically apply for a node storage space indicated by pointer Q, and assign the data element x to the data element field q->data = x of the new node;
  3. Q ->next = p->next;
  4. Ai −1a_{i-1}ai−1 = q, p->next = q;

The operation of insertion is shown in the figure below:

ListDelete(SLNode *head,int I,DataType *x)

Delete the I th node (0≤ I ≤size0\leq I \leq size0≤ I ≤size) of the single linked list of the leading node, and the data field value of the deleted node is brought back by X. 1 is returned after the deletion, and 0 is returned after the deletion.

int ListDelete(SLNode *head,int i,DataType *x){
    SLNode *p = head;
    int j = - 1;
    while(p->next ! =NULL&& p->next->next ! =NULL && j < i- 1){
        p = p->next;
        j++;
    }
    if(j ! = i- 1) {printf("Insert position parameter error");
        return 0;
    }
    SLNode *s = p->next;
    *x = s->data;
    p->next = p->next->next;
    free(s);
    return 1;
}
Copy the code
  1. The i-1 node is found in the single linked list and indicated by the pointer P.
  2. SLNode *s = p->next; assign the data element value of node AIa_iai to x: *x = s->data.
  3. Unchain aia_iai: p->next = p->next->next and free aia_iai: free(s).

Delete data elements as shown below:

ListGet(SLNode *head,int I,DataType *x)

Get the value of the data field of the I (0≤ I ≤size0\leq I \leq size0≤ I ≤size) node of the singly linked list of the lead node, which is returned by x.

int ListGet(SLNode *head,int i,DataType *x){
    SLNode *p = head;
    int j = - 1;
    while(p->next ! =NULL && j < i){
        p = p->next;
        j++;
    }

    if(j ! = i){printf("Error taking element position argument");
        return 0;
    }

    *x = p->data;
    return  1;
}
Copy the code
2.2.6 Destroy single linked list ListDestory(SLNode **head)

Because the node space of a single linked list is dynamically allocated by the program, and the system is only responsible for automatically reclaiming the statically allocated memory space in the program, so compared with the sequential list, the single linked list needs to add an operation to destroy the single linked list to release the dynamically allocated memory space before the calling program exits.

void ListDestory(SLNode **head){
    SLNode *p ,*p1;
    p = *head;
    while(p->next ! =NULL){
        p1 = p;
        p = p->next;
        free(p1);
    }
    *head = NULL;
}
Copy the code

2.3 time complexity of single linked list operations

The time complexity analysis method of insert and delete operations of single linked list is similar to that of sequential list. The difference is that single-linked list inserts and deletes do not move data elements, only compare them. So when the probability of inserting a data element at any location in the singly linked list is equal, the average number of comparisons between data elements is: \


E i s = ∑ i = 0 n P i ( n – i ) = 1 n + 1 ∑ i = 0 n ( n – i ) = n 2 E_{is} = \sum\limits_{i=0}^n P_{i}(n-i) = \frac{1}{n+1} \sum\limits_{i=0}^n (n-i) = \frac{n}{2}

The average number of times a data element in a single linked list is deleted and compared is: \


E d l = ∑ i = 0 n – 1 q i ( n – i ) = 1 n ∑ i = 0 n – 1 ( n – i ) = n – 1 2 E_{dl} = \sum\limits_{i=0}^{n-1} q_{i}(n-i) = \frac{1}{n} \sum\limits_{i=0}^{n-1} (n-i) = \frac{n-1}{2}

From the above analysis, it can be seen that:

  1. The average time complexity for inserting and deleting a data element in a singly linked list is O(n).
  2. The time complexity of finding the number of single linked list data elements and destroying single linked list is O(n).
  3. The operation of fetching data elements in a single linked list has nothing to do with the number of data elements N, and its time complexity is O(1).
  4. Compared with the sequential list, the main advantage of single linked list is that the maximum number of data elements need not be determined in advance; The main disadvantage is that each node must have a pointer field, so the utilization efficiency of space unit is not high, and the algorithm of single linked list operation is more complex.

2.4. Circular singly linked lists

Circular singly linked list is another form of singly linked list. Its structure features that the pointer field of the last node in the list is no longer the closing mark, but points to the first node of the whole list, so that the list forms a ring. Like singly linked lists, circular singly linked lists also have leading node structure and non-leading node structure. The circular singly linked lists with leading nodes are convenient to insert and delete. In practice, cyclic singly linked lists with leading nodes are more common. The following figure shows the circular single-linked list structure of the lead node.

Singly linked lists are convenient to go from the end of the list to the end of the list, but not from the end of the list to the head of the list, while circular singly linked lists are convenient to go from the end of the list to the head of the list. When the sequence of data elements to be processed has the characteristic of ring structure, it is suitable to use circular singly linked list. The operation implementation of the circular single-linked list of the leading node is similar to that of the single-linked list of the leading node, and the differences are as follows:

  1. Change the statement (*head)->next = NULL to (*head)->next = *head in the initialization function.
  2. Loop through the judgment conditions in other functions p->next! = NULL and p->next->next! NULL in = NULL is changed to head.

3. Bidirectional linked lists

Each node in the bidirectional linked list has a precursor pointer domain in addition to its successor pointer domain. Like singly linked lists, bidirectionally linked lists have a leading node and a non-leading node. Bidirectionally linked lists with leading nodes are more common. In addition, bidirectional lists can also have cyclic and non-cyclic structures. Cyclic bidirectional lists are more commonly used. In a bidirectional circular linked list, each node contains three fields, namely, data domain, next domain and prior domain. Data domain is the data domain, next domain is the pointer domain pointing to the subsequent node, and prior domain is the pointer domain pointing to the precursor node. The following figure shows the structure of the nodes of the bidirectional circular linked list.

Thus, the bidirectional circular linked list expressed in C language is summarized as follows:

typedef struct Node{
    DataType   data;// Store data
    struct Node *next; // Store a pointer to a subsequent node
    struct Node *prior; // store a pointer to a precursor node
} DLNode;
Copy the code

It is not difficult to find the descendants of the current node in a singly linked list by using the next pointer of the current node, but to see the precursor of the current node, you need to start over from the head pointer. For a program that needs to find the successors and precursors of the current node frequently, the time efficiency of using a single linked list is very low, and the bidirectional linked list is the best choice to effectively solve this kind of problem. The structure of the bidirectional circular linked list of the leading node is shown in the figure below.

3.1 Operation realization of bidirectional circular linked list

P ->next->prior==p ->next->prior==p; p->next->prior==p; P ->prior->next==p ->next==p ->next==p

Initialize ListInitiate(DLNode **head)

Before initialization, head does not have a specific address value. During initialization, head gets the specific address value, which is returned to the calling function. Therefore, head is designed to be the pointer type of the pointer.

void ListInitiate(DLNode **head) {
    *head = (DLNode *) malloc(sizeof(DLNode));
    (*head)->prior = *head;
    (*head)->next = *head;
}
Copy the code
ListInsert(DLNode *head, int I, DataType x)

Insert the node of the data element X before the I (0≤ I ≤size0\leq I \leq size0≤ I ≤size) position of the head, return 1 on success, return 0 on failure.

int ListInsert(DLNode *head, int i, DataType x) {
    DLNode *p = head->next;
    int j = 0;
    while(p ! = head && j < i) { p = p->next; j++; }if(j ! = i) {printf("Insert in wrong position");
        return 0;
    }

    DLNode *s = (DLNode *) malloc(sizeof(DLNode));
    s->data = x;

    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return 1;
}
Copy the code
  1. So I’m going to find the node at the ith position in the list and I’m going to call it p.
  2. Dynamically apply for a node storage space indicated by pointer S, and assign the data element x to the data element field s->data = x of the new node;
  3. P ->prior = p-> next = s; p->prior->next = s;
  4. The successor of the new node S points to p: s->next = p.
  5. P’s precursor pointer points to S.

The insertion operation is shown in the figure below:

ListDelete(DLNode *head, int I, DataType *x)

Delete the I th node (0≤ I ≤size0\leq I \leq size0≤ I ≤ SIZE) of the bipartite linked list of the leading node, and the data field value of the deleted node is brought back by X. The value of the deleted node is returned 1 on successful deletion and 0 on failure deletion.

int ListDelete(DLNode *head, int i, DataType *x) {
    DLNode *p = head->next;
    int j = 0;
    while(p->next ! = head && j < i) { p = p->next; j++; } *x = p->data;if(j! =i){printf("Error deleting location parameter");
        return 0;
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return 1;
}
Copy the code
  1. So I’m going to find the node at the ith position in the list and I’m going to call it p.
  2. Assign the value of the data element at node I to x: *x = p->data.
  3. P ->prior->next = p->next
  4. Modify the pointer to the precursor of p’s successor node to point to p’s precursor node.

The deletion operation is as follows:

3.1.4 Get the current number of elements ListLength(DLNode *head)
int ListLength(DLNode *head){
    DLNode *p = head;
    int size = 0;
    while(p->next ! = head){ p = p->next; size++; }return size;
}
Copy the code
  1. Before the loop, the pointer variable p points to the head node and the count variable size is assigned 0.
  2. The loop ends with the condition p-> Next! = head, in the loop, each time the pointer p points to its value to the next node, increment the count variable size by one.
  3. The function returns the count variable size.
3.1.5 Destroying a Single Linked list ListDestory(DLNode **head)

Like a single linked list, the node space of a bidirectional circular list is dynamically claimed by the program, and the system is only responsible for automatically reclaiming the statically allocated memory space in the program.

void ListDestory(DLNode **head){
    DLNode *p = *head;
    DLNode *p1;
    int n = ListLength(*head);
    for (int i = 0; i <= n; i++) {
        p1 = p;
        p = p->next;
        free(p1);
    }
    *head = NULL;
}
Copy the code