- Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
preface
In “data structure and Algorithm —- order table” summarized their own learning for order table, here is a brief review
- A sequential list is a linear structure that uses a sequential storage structure for storage.
- It has a relatively large advantage in search, can search according to the subscript, time complexity is 0(1)
- For insert and delete operations, the time complexity is O(N) and the search efficiency is low
- In terms of space, the order table needs to determine the size of space during initialization, which may be insufficient or too large for opening space, which is not flexible enough. However, the release of space does not need to be considered when deleting elements
This blog summarizes another linear table storage structure —- chain storage structure.
A single linked list
Linear lists are stored in memory in a chained structure, known as linked lists. Linked lists can be divided into one-way linked lists and two-way linked lists according to whether there are precursors and successors. This article first discusses one-way linked lists.
A one-way linked list is a node that contains a data field and a pointer field, where the data field stores data and the pointer field stores the pointer address of the next node. Its definition can be as follows:
typedef struct Node {
ElemType data; / /! The < data fields
struct Node *next; / /! < pointer field, store the pointer address of the next node
}LinkNode;
Copy the code1. Initialization of unidirectional linked lists
Before initialization, explain a few concepts:
- Header: a value that points to the first node in a linked list, stores no value, and has an empty or meaningless data field
- Header node: The first node in a linked list that stores the value of actual meaning
- Endnode: The last node in a linked list, followed by the head in the case of a circular list
In fact, the header serves as a flag. It is possible to implement the linked list without setting the header, but in the later operation, the code will be relatively troublesome. Here is the initialization code for a single linked list:
typedef int Status; /* Status is the type of the function, and its value is the Status code of the function result, such as OK */
typedef int ElemType; /* ElemType specifies the element type, depending on the actual situation. Int */ is assumed here
typedef struct Node {
ElemType data; / /! The < data fields
struct Node *next; / /! < pointer field, store the pointer address of the next node
}LinkNode;
typedef LinkNode * LinkList;
Status initLinkList(LinkList *L) {
*L = (LinkList)malloc(sizeof(LinkNode));
if (*L == NULL) { // error tolerance, open up failure situations
return ERROR;
}
LinkList temp = NULL;
LinkList r = *L;
for (int i = 0; i <= 10; i++) { // The for loop can be removed if 0 ~ 10 is added by default
temp = (LinkNode *)malloc(sizeof(LinkNode));
temp->data = i;
r->next = temp;
r = temp;
}
r->next = NULL;
return OK;
}
Copy the code2. Traversal of single linked lists
Single linked list traversal is relatively simple, the code is as follows:
void displayLink(LinkList L) {
if (L->next == NULL) {
printf("Linked list is empty");
return;
}
LinkList temp = L->next;
printf("The list element data is: \n");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
Copy the codeL is the head node of the single linked list. If the subsequent node is empty, it indicates that the linked list does not store the actual value, so the linked list is judged to be empty. When traversing the list, execute temp = temp->next; Statement, when temp is empty, it indicates that the list traversal is complete.
3, forward interpolation method to build a single linked list
The construction of a single linked list is divided into two types, namely, the forward interpolation method and the back interpolation method. This section first explains the forward interpolation method.
Front-interpolation, as the name implies, inserts list elements from the front. When the linked list is empty, insert an element, then the header points to that element; when the element is inserted, the successor of the new element points to the successor of the header, and then the successor of the header points to the newly inserted node, as shown below:
The code is as follows:
Status headInsert(LinkList *L) {
*L = (LinkList)malloc(sizeof(LinkNode));
if (*L == NULL) {
return ERROR;
}
(*L)->next = NULL; // The header is prepended to NULL, which affects the successor of the first new node inserted
LinkList temp = NULL;
for (int i = 0; i <= 10; i++) {
temp = (LinkList)malloc(sizeof(LinkNode));
temp->data = i;
temp->next = (*L)->next; // Assign next of the head node to next of the new node each time
(*L)->next = temp; // make the next of the header point to the new node
}
return OK;
}
Copy the code4, post-interpolation method to build a single linked list
When the first element is inserted, next of the first node points to the inserted element, next of the element points to NULL, next of the previous element points to the new element, and next of the new element points to NULL, as shown below:
The code is as follows:
Status tailInsert(LinkList *L) {
*L = (LinkList)malloc(sizeof(LinkNode));
if (*L == NULL) {
return ERROR;
}
LinkList temp = NULL;
LinkList r = *L; // the variable r records the position of the last node. The initial value is the header
for (int i = 0; i <= 10; i++) {
temp = (LinkNode *)malloc(sizeof(LinkNode));
temp->data = i;
r->next = temp; // Insert the new node at the end of the list
r = temp; // Change the value of r, where the last node is the newly inserted node, and point r to that node
}
r->next = NULL; // Set next to NULL on the last node to prevent traversal crashes
return OK;
}
Copy the codeCompared with the front interpolation method and the back interpolation method, it can be found that compared with the front interpolation method, the back interpolation method will have a temporary marker variable R, but the back interpolation method is more logical in practice.
5. Single linked list insertion and deletion
Note that both front and back interpolation are ways of building a single linked list by inserting new nodes at the front or back of the list, not in the middle. This section looks at insertion and deletion of singly linked lists.
1.5.1 Insertion of single linked lists
Different from the sequential structure, the insertion of a single linked list does not need to move all the elements after the insertion position backward, but to change the pointing of the node before the insertion position and the pointing of the new node, which can be divided into the following steps:
- 1. Locate the target before the insertion position
- Temp next points to Target next
- Target next points to temp, a new node
Refer to the figure below for details:
One thing to note is that step 2 must precede step 3, otherwise the original successor will not be found. Insert the following code:
Status insertElement(LinkList *L, ElemType e, **int** place) {
if(! (*L) || place <1) {
return ERROR;
}
LinkList target = (*L)->next;
// find the node before the insertion position
for (int i = 1; i < place && target; target = target->next, i++) {}
// Check if the location is found
if(! target)return ERROR;
// Create new node
LinkList temp = (LinkList)malloc(sizeof(LinkNode));
if(! temp) {return ERROR;
}
temp->data = e;
// Point next of the new node to targe's next
temp->next = target->next;
target->next = temp;
return OK;
}
Copy the code1.5.2 Deletion of single linked list
Compared with insertion, the deletion step of single linked list is relatively simple, but they all need a common step, that is, to find the position of the operation node, which can be summarized into the following steps:
- 1. Locate the target before the node to be deleted
- 2. Point target’s next to next of the node to be deleted
- 3. Release the memory of the node to be deleted
Please refer to the following figure for steps:
The code looks like this:
Status deleteElement(LinkList *L, **int** place) {
if ((*L)->next == NULL) {
printf("Linked list is empty");
return ERROR;
}
LinkList target = (*L)->next;
// Find the node above the node to be deleted
for (int i = 1; i < place && target; target = target->next, i++) {}
if(! target) {return ERROR;
}
LinkList temp = target->next; // Get the node to delete
target->next = temp->next; // Next points to next on the node to be deleted
free(temp); // Release the memory of the node to be deleted
return OK;
}
Copy the codeUnidirectional circular linked list
The difference between a one-way circular list and a single-linked list is that the next of the last node of a single-linked list points to NULL, whereas the next of the last node of a one-way circular list points to either a header (if set) or a primary node (if not set), as shown below:
In the single linked list, we introduce the header node to realize the add, delete, change and check. This section does not use the header node to realize the add, delete, change and check of the one-way circular linked list.
1. Initialization of a one-way circular linked list
When initializing a one-way circular linked list, different from a single linked list, each new node added to the list should point its next to the leading node. Here, no headers are added, and the code is as follows:
Status initLinkList(LinkList *L) {
LinkList temp = NULL;
printf("Enter the number you want to enter and press the space bar. Type 0 to end and type \n.");
LinkList r = NULL;
int item = 0;
while (1) {
scanf("%d", &item); // use scanf as input
if (item == 0) {
Type 0 to end the loop
break;
}
if (*L == NULL) {
// The list is empty
*L = (LinkList)malloc(* *sizeof**(LinkNode));
if(! (*L)) {return ERROR;
}
// then L is the primary node
(*L)->data = item;
(*L)->next = *L; // Unlike a singly linked list, you point to yourself
r = *L;
} else {
// The linked list is not empty
temp = (LinkList)malloc(* *sizeof**(LinkNode));
if(! temp) {return ERROR;
}
temp->data = item;
temp->next = *L; // Unlike singly linked lists, this one points to the initial node
r->next = temp;
r = temp; // Add a variable r to record the position of the last node. Otherwise, the last node must be found first}}return OK;
}
Copy the code2. Traversal of one-way circular linked lists
The traversal of a unidirectional cyclic linked list needs to consider two aspects:
- 1. Determine whether the linked list is empty, whether the circular linked list is empty, and whether the initial node of the linked list is empty. = NULL
- 2. Loop end condition: the traversal of one-way circular linked list is different from that of single linked list. It cannot simply judge whether the node is empty, but whether the next and the initial node are the same
The code looks like this:
void display(LinkList L) {
if (L == NULL) {
// There is no header, so we can check whether L is null
printf("Linked list is empty");
return;
}
LinkList temp = L;
// use the do while loop, otherwise the while loop must be called first temp = temp->next;
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp ! = L);printf("\n");
}
Copy the code3, unidirectional circular list insertion
Since no headers are used, we need to consider whether the inserted node is a primary node:
- Finally, headed by inserting node point: unlike singly linked lists, one-way circular linked list can’t directly to the new node next first finally, pointing to the original point, but to find the tail first node, and the new node next to the original song finally point next node (tail), end nodes of the next point to new, again to ensure after insert node list is still a circular linked list
- Insert node is not the primary node: find the node before the insert node target, point the next of the new node to target’s next, and then point the next of target to the new node
The process is shown in the figure below:
The code is divided into two types: the subscripts start from 0 and the subscripts start from 1, but the logic is basically the same as the above figure. The codes are as follows:
1. Subscripts start at 0
Status insertLinkList(LinkList *L, int place, ElemType e) {
LinkList target = NULL;
LinkList temp = NULL;
if (place == 0) {
// the first dollar points
// Create a new node, insert it successfully, otherwise return ERROR
// loop list, need to find the last node first
// Next of the new node points to the original node, next of the tail node points to the new node, and change the initial node to the new node
for(target = *L; target->next ! = *L; target = target->next) {}if (target == NULL) {
return ERROR;
}
temp = (LinkList)malloc(sizeof(LinkNode));
if(! temp) {returnERROR; } temp->data = e; temp->next = *L; target->next = temp; *L = temp; }else {
// non-header node
int i = 1;
for(target = (*L); target->next ! = *L && i < place; target = target->next, i++) {}if (target == NULL) {
return ERROR;
}
temp = (LinkList)malloc(sizeof(LinkNode));
if(! temp) {returnERROR; } temp->data = e; temp->next = target->next; target->next = temp; }return OK;
}
Copy the code2. Subscripts start at 1
Status insertLinkList1(LinkList *L, int place, ElemType e) {
LinkList target = NULL;
LinkList temp = NULL;
if (place == 1) {
// the first dollar points
// Create a new node, insert it successfully, otherwise return ERROR
// loop list, need to find the last node first
// Next of the new node points to the original node, next of the tail node points to the new node, and change the initial node to the new node
for(target = *L; target->next ! = *L; target = target->next) {}if (target == NULL) {
return ERROR;
}
temp = (LinkList)malloc(sizeof(LinkNode));
if(! temp) {returnERROR; } temp->data = e; temp->next = *L; target->next = temp; *L = temp; }else {
// non-header node
int i = 1;
for(target = (*L)->next; target->next ! = *L && i < place -1; target = target->next, i++) {}
if (target == NULL) {
return ERROR;
}
temp = (LinkList)malloc(sizeof(LinkNode));
if(! temp) {returnERROR; } temp->data = e; temp->next = target->next; target->next = temp; }return OK;
}
Copy the codeBy comparing the two parts of the code, it can be found that the subscript 0 or 1 of the leading element node at the insertion position has little influence on the code. In cases where the insertion position is not the primary node, the code to find the previous node location needs to be modified, and the rest of the logic does not need to be changed.
4, unidirectional circular list deletion
As with insertion, the deletion of a one-way circular list also takes into account both the leading node and the non-leading node:
- Primary node: first find the tail node, then point next of the tail node to next of the node to be deleted, then delete the node and release the memory
- Non-primary node: find the previous targe of the node to be deleted, point target’s next to next of the node to be deleted, then delete the node and free the memory.
The code looks like this (only if subscripts start at 1 are shown here) :
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp points to the first node of the list
temp = *L;
if (temp == NULL) return ERROR;
if (place == 1) {
// select *L from *L;
if ((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Target ->next = (*L)->next;
//2. If the new node is used as a header, the old header is released
for(target = *L; target->next ! = *L; target = target->next); temp = *L; *L = (*L)->next; target->next = *L;free(temp);
} else {
// If you delete other nodes -- other nodes
//1. Locate the target before deleting the target
//2. Make target->next point to the next node
//3. Release the temp node to be deleted
for (i=1,target = *L; target->next ! = *L && i ! = place- 1; target = target->next,i++) {}; temp = target->next; target->next = temp->next;free(temp);
}
return OK;
}
Copy the codeconclusion
This paper mainly summarizes the operation of one-way linked list, including single linked list and one-way cyclic linked list. In the process of exploration, a comparison was made on whether to reference headers or not. It can be found that in the case of not introducing headers, one more case needs to be considered. Of course, if you don’t care about this, you can also not introduce headers, which depends on personal habits.
Through the conclusion of this paper, we can find that the time complexity of single linked list delete and insert operation is O(1), and its query operation is O(n), but the problem of capacity does not need to be considered when opening up space, and memory management is carried out by manually releasing the memory. This article is mainly a summary of one-way linked lists. If there are any incorrect places, please correct them. The next article will be a summary of two-way linked lists.