Single linked list general operation
/ * * * * * * * * * * * * * * * * * * * * * singly linked lists the normal operation of * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
LinkList CreateHeadListH(a); // create a singly linked list with a header
LinkList CreateHeadListT(a); // Create a singly linked list
int ListEmpty(a); // single linked list null
int ListLength(a); // Find the length of a single list
void Travel(a); // Iterate over the singly linked list
int InsertNode(a); // Insert node
int DeleteNode(a); // Delete the node
ElemType GetElem(a); // check by address
int GetLocate(a); // query by value
int RemoveRepeat(a); // Remove duplicate values
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
Copy the code
Define a single linked list structure
A singly linked list is composed of links of multiple nodes, each of which contains two fields, a data field and a link field (address field).
- Data fields
dataUsed to store specific data. - The address field
nextThe location used to store the next node.
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
typedef int ElemType; // Single-linked lists store the data types of elements
// Define a single list structure
typedef struct Node(a){
ElemType data; // Single linked list node data field
struct Node *next; // single list node address field (pointing to the next node)
}*LinkList, Node;
Copy the code
Construct a single linked list
Head insertion method to achieve
/* * header method to create a single list (head node) * datas receive array, used to assign list node data * len datas array length, easy traversal */
LinkList CreateHeadListH(ElemType *datas, int len){
// Create a header
LinkList head, new_node;
head = (LinkList)malloc(sizeof(Node));
// head -> data = len; // The list length can be stored in the header data field
head -> next = NULL;
// Assign new nodes and use header linking
for(int i=0; i<len; i++){ new_node = (LinkList)malloc(sizeof(Node));
new_node -> data = datas[i];
new_node -> next = head -> next;
head -> next = new_node;
}
return head;
}
Copy the codeIn the head insertion method, nodes are inserted into the head of a single linked list.
Tail insertion method to achieve
/* * The end method creates a single list (head node) * datas receive array, used to assign the list node data * len datas array length, easy traversal */
LinkList CreateHeadListT(ElemType *datas, int len){
// Create a header
LinkList head, p, new_node;
head = (LinkList)malloc(sizeof(Node));
head -> next = NULL;
p = head;
// Assign new nodes and connect them with a tail method
for(int i=0; i<len; i++){ new_node = (LinkList)malloc(sizeof(Node));
new_node -> data = datas[i];
new_node -> next = NULL;
p -> next = new_node;
p = new_node;
}
return head;
}
Copy the codeTail-insertion method is used to construct a single linked list by inserting nodes into the end of the list.
Single linked list of head and tail plug method in detail
In order not to make this article too long, for more details on single-linked list header and tail interpolation, please see my other blog post on single-linked list header and tail interpolation
Single linked list nulls
/* * single linked list empty * list receive single linked list */
int ListEmpty(LinkList list){
return (list= =NULL || list -> next == NULL);
}
Copy the code
Calculate the length of a single linked list
/* * Computes the length of a single list * list receives a single list */
int ListLength(LinkList list){
LinkList p = list;
int len = 0;
if(ListEmpty(list)) {return len;
}
p = p -> next;
while(p ! =NULL){
len ++;
p = p -> next;
}
return len;
}
Copy the code
Iterate over a single linked list
/* * traverses the single list * list single list */
void Travel(LinkList list){
LinkList p = list;
if(! ListEmpty(list)) {// the list is traversed only when it is not empty
p = p -> next; // Because the head node is singly linked list, we need to go first
while(p ! =NULL) {printf("%d\t", p -> data);
p = p -> next;
}
printf("\n"); }}Copy the code
Single chain list head, tail insertion method construction effect
int main(int argc, char const *argv[])
{
int datas[] = {2.4.6.8.10};
// Dynamically calculates the length of the datAS array
// Array length = total size of array/size of each element in array
int len = sizeof(datas) / sizeof(datas[0]);
printf("Head Insertion method to construct single linked list \n");
LinkList list_h = CreateHeadListH(datas, len);
printf("ListEmpty():%d\n", ListEmpty(list_h)); / / found empty
printf("ListLength():%d\n", ListLength(list_h)); / / for long
printf("Travel():");
Travel(list_h); / / traverse
printf("Single linked list \n constructed by tail Insertion method \n");
LinkList list_t = CreateHeadListT(datas, len);
printf("ListEmpty():%d\n", ListEmpty(list_t));
printf("ListLength():%d\n", ListLength(list_t));
printf("Travel():");
Travel(list_t);
return 0;
}
Copy the codeBecause arrays store elements at contiguous addresses, they can be dynamically calculated to facilitate traversal.
The input result is as follows:
ListEmpty(); ListEmpty();0
ListLength():5
Travel():10 8 6 4 2ListEmpty():0
ListLength():5
Travel():2 4 6 8 10Please press any key to continue..Copy the code
Single-linked lists specify where to insert nodes
Code implementation
* list * data * data of the node to be inserted * pos node insertion position (logical position (1,2,3...)) ) * /
int InsertNode(LinkList list, ElemType data, int pos){
LinkList p = list, new_node;
if(ListEmpty(list)) {printf("Empty single linked list \n");
return FALSE;
}
// Determine whether the insertion position is reasonable
if(pos <= 0 || pos > ListLength(list) + 1) {printf("Improper insertion position \n");
return FALSE;
}
// Find the node before the insertion position
for(int i = 0; i < pos - 1&& p ! =NULL; i++){
p = p -> next;
}
// Prepare a new node
new_node = (LinkList)malloc(sizeof(Node));
new_node -> data = data;
// p -> next -> p -> next
new_node -> next = p -> next;
p -> next = new_node;
return TRUE;
}
Copy the code
Detailed illustrations
Assume that the original single-linked list is: head –> 2 –> 6, and the value of the node to be inserted is 4 and the insertion position is 2.
You just need to find the node before the insertion, because the address field of the node before the insertion holds the node before the insertion.
The node found is new_code1 and new_code1 -> next is new_code2.
So we just have to
new_code3 -> next = new_code1 -> next;
new_code1 -> next = new_code3;
Copy the codeLet the address field of the node to be inserted point to the node at the insertion position
Then make the address field of the node before the insertion point to the node to be inserted.
1, 2 and 3 represent the single linked list node positions
(1), (2), and (3) represent the sequence of insert operations
Note: do not make the address field of the node before the insertion point to the node to be inserted, and then make the address field of the node to be inserted point to the node at the insertion position
new_code1 -> next = new_code3;
New_code1 -> next = new_code3; now_code3 -> next = new_code3
new_code3 -> next = new_code1 -> next;
Copy the code
Single-linked list specifies the location where nodes are deleted
Code implementation
/* * list * *val is used to store the data of the deleted node * pos node deleted position (logical position (1,2,3...)) ) * /
int DeleteNode(LinkList list, ElemType *val, int pos){
LinkList p = list, r;
if(ListEmpty(list)) {printf("Empty single linked list \n");
return FALSE;
}
// Determine whether the deletion position is reasonable
if(pos <= 0 || pos > ListLength(list)) {printf("Delete location unreasonable \n");
return FALSE;
}
// Find the previous position of the node to be deleted
for(int i = 0; i < pos - 1&& p ! =NULL; i++){
p = p -> next;
}
r = p -> next; // Record the node to be deleted
*val = r -> data; // Use the pointer to return the data of the deleted node
p -> next = r -> next; // re-link the list
free(r); // Release the resources of the deleted node
return TRUE;
}
Copy the code
Detailed illustrations
Assume the original singly linked list is head –> 2 –> 4 –> 6, delete the second node.
Again, it’s just like inserting and you just need to find the node before the node that you want to delete.
The node found is new_code1, and new_code1 -> next is node new_code2, which is the node to delete.
r = new_code1 - > next;
new_code1 -> next = r -> next; // new_code1 -> next = new_code2 -> next;
free(r);
Copy the codeLet’s make r equal to the node we’re deleting,
r = new_code1 - > next; --> r = new_code2;
Then make the address field of the node before the deletion point to the node after the deletion.
new_code1 -> next = r -> next; R -> next = new_code2
↓↓
new_code1 -> next = new_code2 -> next; // new_code2 -> next equals new_code3
↓↓
new_code1 -> next = new_code3;
Copy the codeDelete node space free(r)
Delete the single linked list after the second position node: head –> 2 –> 6
According to the site
* list * pos node position (logical position (1,2,3...)) ) * /
ElemType GetElem(LinkList list.int pos){
LinkList p = list;
if(ListEmpty(list)) {printf("Empty single linked list \n");
return FALSE;
}
if(pos <= 0 || pos > ListLength(list)) {printf("Unreasonable position \n");
return FALSE;
}
for(int i = 0; i < pos && p ! =NULL; i++){
p = p -> next;
}
return p -> data;
}
Copy the code
According to the values for the address
/* * Finds the location of the node based on the specified value * (returns the location of the first node found if multiple values are the same, or 0 if none is found) * list single linked list * data The value to find */
int GetLocate(LinkList list, ElemType data){
LinkList p = list;
int pos = 0;
if(ListEmpty(list)) {return FALSE;
}
p = p -> next;
while(p ! =NULL){
pos ++;
if(p -> data == data){
return pos;
}
p = p -> next;
}
return FALSE;
}
Copy the code
Single linked list deweighting
/* * Remove duplicate values from a single list (only one duplicate value is retained) * list Single list * Return value: 1 is returned if a single list is de-duplicated, otherwise 0 */ is returned
int RemoveRepeat(LinkList list){
LinkList p = list, q, r;
int flag = 0;
if(ListEmpty(list)) {return FALSE;
}
p = p -> next;
while(p ! =NULL){
q = p;
while(q ! =NULL&& q -> next ! =NULL) {if(p -> data == q -> next -> data){
r = q -> next; // Record nodes with the same value
q -> next = r -> next;
free(r);
flag = 1;
}else{
q = q -> next;
}
}
p = p -> next;
}
return flag;
}
Copy the codeThe idea is to compare each node in the singleton with a node that has not been compared before, and delete one node when it encounters the same one.
For example, the single-linked list sequence is 2 4 2 8 8 6 6 8 12
So let's take the first node2Compare it to other nodes in a single linked list2 4 2 8 8 6 6 8 12↑ ↓↓ If it encounters the same one, delete it2 4 8 8 6 6 8 12
2It's heavier than finishing a round2And then use the second node4Compare it to any other node in a singly linked list that hasn't been compared2 4 8 8 6 6 8 12Write left left2 4 8 8 6 6 8 12
4It's heavier than finishing a round4And then use the third node8Compare it to any other node in a singly linked list that hasn't been compared2 4 8 8 6 6 8 12Write left left2 4 8 6 6 12Cycle on2 4 8 6 6 12Write left left2 4 8 6 12The last step2 4 8 6 12Write left left2 4 8 6 12
Copy the codeLook at the de-weight effect
Single list ListLength():9
Travel():2 4 2 8 8 6 6 8 12ListLength():5
Travel():2 4 8 6 12
Copy the code
The source code
The source code has been uploaded to GitHub data-structure-of-C, welcome to visit.
✍ code word is not easy, the long journey always feeling, praise again go line, also hope you heroes support ❤️