Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
preface
Today, I learned the linked list in the linear list at school. The teacher explained it in place and made it easy to understand. Learning always needs to take notes, and a good memory is better than bad writing. Don’t spray if you don’t like it… Ha, ha, ha
Once a day to prevent decadence
1. Let’s look at linked lists
1.1 Linked lists there are single linked lists, bidirectional linked lists, circular linked lists and so on, no matter what the linked list will be created first, to create a linked list we need to know several key steps.
Graph TD step 1 create a node -> step 2 create a node -> Step 3 connect step 1 to step 2Malloc (sizeof) allocates the required amount of memory and returns a pointer to it. Example: (LinkList)malloc(sizeof(Node)) typedef keyword, which you can use to get a new name for a type example: typedef int ElemType struct The keyword is used to create a structure example: typedef struct Node { ElemType data; struct Node *next; }Node,*LinkList; The memory allocated by calloc, malloc, or realloc before free(void * PTR) is freedCopy the code1.2 Establish a single linked list
Let’s start with a picture:
Take their relationship as a linked list, xiao Hong holds Xiao Ming’s hand, Xiao Ming holds Xiao Wang’s hand, Xiao Wang holds Xiao Li’s hand, xiao Li’s last one she only likes herself, their hand in hand is the connection (can be understood as pointer field), her own secret is the data of her node. Just use the teacher’s drawing
1.3 So let’s start with the head-plug method.
First a picture, then a story.
Malloc has given birth to beautiful Beauty, and she has a secret: “I only like themselves,” one day matchmaker noticed her, and to record the location of her home, looking for a man who likes her for her, the day the malloc wang, she gave birth to a handsome guy, he is the secret of the “I like xiao li”, familiar matchmaker and find him, found him like of the person is just the girl he had just record, then tell him, Guy just remember the location of the small beautiful home, matchmaker at this time to record the location of the wang family covers, the position of the small beautiful malloc in a good mood and gave birth to a, xiao Ming, xiao Ming is a boy, he is the secret of the “I like wang,” one day matchmaker saw his fine eyes, want to give he introduced object, found that he just like he just record a: xiao wang, Matchmaker know their love is not able to resist, so he gave xiao Ming wang’s address and xiao Ming to remember the address of wang, and he in hand, matchmaker now remember, xiao Ming address malloc not the kui is a good man, she gave birth to, although not a viviparous four, but it do indirect gave birth to a four, is such a beautiful and easy, Very sexy xiao Hong and her secret: “I like Xiao Ming” was born, the matchmaker received an invitation to find a boyfriend for Xiao Hong, the matchmaker found that what she liked was just their records of Xiao Ming, so the address of Xiao Ming told Xiao Hong, xiao Hong and Xiao Ming smoothly hand in hand, at this time the address of Xiao Hong was remembered by the matchmaker. Ha ha ha ha ha ha ha ha ha matchmaker is the Head node, as long as you know her recorded address, you can go through her matchmaking experience.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
struct Node *next;
}link;
link * creatLink(int * arc, int length) {
int i;
// In the initial state, the header pointer H has no node, so inserting the first element is equivalent to creating node H
link * H =(link*)malloc(sizeof(link));
H->data = arc[0];
H->next = NULL;// Because the first node of the header is the last node of the linked list, so
// If more than one element is inserted with the header method, it can be added before the first node H
for (i = 1; i<length; i++) {
link * a = (link*)malloc(sizeof(link));
a->data = arc[i];
// When inserting an element, first link the list after the insertion position to the new node
a->next = H;
// then link the header pointer H
H = a;
}
return H;
}
// Implement a header list with a header
link * HcreatLink(int * arc, int length) {
int i;
// create a header, H, whose list header pointer is also H
link * H = (link*)malloc(sizeof(link));
H->data = 0;P = H->next; p = H->next;
H->next = NULL;
// Create a linked list using the header method
for (i = 0; i<length; i++) {
link * a = (link*)malloc(sizeof(link));
a->data = arc[i];
// First connect the list after the insertion position to the new node A
a->next = H->next;
// Insert the new node A after the first node
H->next = a;
}
return H;
}
void display(link *p) { // The output function of the list, traversing the list
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int a[3] = { 1.2.3};
// create a list of headless nodes using the header method
link * H = creatLink(a, 3);
display(H);
// create a list of nodes with headers
link * head = HcreatLink(a, 3);
display(head);
// Release it after use
free(H);
free(head);
return 0;
}
Copy the code
1.4 Now try the tail interpolation method again to create
The tail insertion is not very different from the head insertion, which is the first insertion every time, and the tail insertion is the last insertion every time. The tail insertion method requires
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
struct Node *next;
}link;
link * creatLink(int * arc, int length) {
int i;
// In the initial state, the header pointer H has no node, so inserting the first element is equivalent to creating node H
link * H =(link*)malloc(sizeof(link));
H->data = arc[0];
H->next = NULL;
// If more than one element is inserted with the header method, it can be added before the first node H
for (i = 1; i<length; i++) {
link * a = (link*)malloc(sizeof(link));
a->data = arc[i];
// When inserting an element, first link the list after the insertion position to the new node
a->next = H;
// then link the header pointer H
H = a;
}
return H;
}
link * creattail(int * arc, int length) {// Here we use the tail insertion method to create the linked list
int i;
link * q ; //q is used to mark the position of the last node, and then q is connected to the next new node
link * H =(link*)malloc(sizeof(link));// create the first node
H->data = arc[0];
H->next = NULL;
q = H; // remember the first node
for (i = 1; i<length; i++) {
link * a = (link*)malloc(sizeof(link));// Create new node
q->next = a; // The last node is connected to the new node, so that each new node is created at the last
a->data = arc[i]; // Assign a value to the newly created node
a->next = NULL; // Since the newly created node is the last one, its pointer field is NULL
q = a; //q now marks the newly created node as the last node, so that the newly created node can join q
}
return H;Return the first node
}
// Implement a header list with a header
//link * HcreatLink(int * arc, int length) {
// int i;
// // creates a header, H, whose list header pointer is also H
// link * H = (link*)malloc(sizeof(link));
// H->data = 0;
// H->next = NULL;
// // use the header method to create a linked list
// for (i = 0; i
// link * a = (link*)malloc(sizeof(link));
// a->data = arc[i];
// // first link the list after the insertion position to the new node A
// a->next = H->next;
// // insert the new node A after the first node
// H->next = a;
/ /}
// return H;
/ /}
void display(link *p) { // The output function of the list, traversing the list
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int a[3] = { 1.2.3};
// create a list of headless nodes using the header method
link * H = creatLink(a, 3);
display(H);
// // use the header method to create a linked list of headed nodes
// link * head = HcreatLink(a, 3);
// display(head);
// Use the tail interpolation method
link * tail = creattail(a, 3);
display(tail);
// Release it after use
free(H);
free(tail);
//free(head);
return 0;
}
Copy the code
Because every time we insert a head, we’re going to go through the first node, so the value of a is going to be in reverse order whereas every time we insert a tail, it’s going to be in order.
1.5 Node insertion and deletion
Let’s take a look at insertion first. In the previous picture, we learned about Xiao Hong and their love story. Now their love is in trouble, their harmonious life is disturbed by a girl, and someone cheates between them.
Xiao Ming liked the matchmaker, xiao Ming held hands with the matchmaker, the matchmaker liked Xiao Wang, so the matchmaker held hands with Xiao Wang. (Ha, ha, ha, it’s a good story to take seriously, but in human terms: we need to find the location where we want to insert the last node, and then connect the last node to the node where we want to insert the next node, and we’re done.) Without further ado, code:
void insert(int arc,link *p) {// Suppose we want to insert 4 after arc
link * a = (link*)malloc(sizeof(link));// Create the node to insert
a->data = 4; // Insert the value 4 to assign
a->next = NULL;
int i=1;
while(p! =NULL&&i! =arc) { i++; p = p->next;// Walk down until you find the value of arc
}
if(p==NULL)/ / not found
{
printf("Insert failed not found.");
}
else{/ / found
a->next =p->next;// The pointer field of the node we want to insert is connected to the next node of the pointer field of the current node
p->next = a; // Then connect the current node to our insert node}}// Call this function to insert
Copy the codeHere’s how it works:
1.5.1 Deleting a Node
The idea of deleting a node is to find the location of the node to be deleted, and then mark the previous node to be deleted in advance, which is connected to the current next node, and then release the current node to achieve the deletion. On a graph:
void delete1(int arc,link *p) {// Suppose we want the node of the arc position
int i=1;
link * q; // It is used to mark the node above the current deleted node
while(p! =NULL&&i! =arc) { i++; q = p;// Remember the last node
p = p->next;// Walk down until you find the value of arc
}
if(p==NULL)/ / not found
{
printf("Deletion failed not found");
}
else{/ / found
q ->next = p->next; // The last node is connected to the next node
free(p);// Release the current node}}Copy the code
2. Creation of circular linked lists
A circular list, as the name implies, is a loop, connected end to end, and in human language, the last tail points to the head to connect end to end, and the middle is a single linked list. The last picture gives you an idea:
link * creatcycle (int * arc, int length) {// Here we use the tail insertion method to create the linked list
int i;
link * q ; //q is used to mark the position of the last node, and then q is connected to the next new node
link * H =(link*)malloc(sizeof(link));// create the first node
H->data = arc[0];
H->next = NULL;
q = H; // remember the first node
for (i = 1; i<length; i++) {
link * a = (link*)malloc(sizeof(link));// Create new node
q->next = a; // The last node is connected to the new node, so that each new node is created at the last
a->data = arc[i]; // Assign a value to the newly created node
a->next = NULL; // Since the newly created node is the last one, its pointer field is NULL
q = a; //q now marks the newly created node as the last node, so that the newly created node can join q
}
q ->next = H; // The last node points to the head node to form a loop.
return H;Return the first node
}
void displaycycle(link *p,int a) { // Because it is a circular list, no matter which node it is, it can traverse the entire list
int i=0;
while (i<a) {
i++;
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
{
int a[3] = { 1.2.3};
link * cycle = creatcycle(a, 3);
displaycycle(cycle,5);
// This is the main function call
}
Copy the codeEffect display:
Conclusion:
, this article is the knowledge of the blogger in the school class the day before yesterday, the blogger sorting, analysis, writing a their own learning notes, convenient and self review, and share with everyone learning together, if there are any errors, please advice in time, this article is about the only singly linked lists and circular linked list, behind the blogger learned knowledge will more timely, hope you like them, don’t like do not spray, Creation is not easy, everyone likes, attention, comments, favorites. (In addition, the story told by the blogger is pure fiction, if offensive, please include).
