1. Introduction to linked list structure
We have learned the use of arrays in the previous chapters. The space of arrays is continuous and the size of arrays is constant. In many application scenarios of dynamic data storage, it is inconvenient to use; The linked list structure introduced in this article supports the dynamic addition and release of nodes, which is more suitable for the application scenario of storing dynamic data. Moreover, the space of the linked list is stored on the heap and can be dynamically allocated and released. In terms of efficiency, the space of array is continuous, and querying and reading data array are dominant; The advantage of linked list is that nodes can be dynamically added and deleted. Nodes at any position can be deleted.
characteristic:
-
The space of the array is continuous and can be accessed directly through the [] subscript.
-
The nodes of the linked list are discontinuous. You need to find the address of the previous node or the next node through the pointer of each node.
Each node of the linked list is a structure variable. There are one or two pointers in the node, which can save the addresses of the previous node and the next node, which is convenient to traverse the linked list and locate the position when deleting and inserting nodes.
2. Case: creation and use of one-way linked list
The following example is written in the form of function encapsulation, and each function is implemented by sub functions.
The functions realized are as follows:
- Initialize chain header
- Insert node function (insert at any position in the linked list and insert at the end of the linked list)
- Delete node function (delete anywhere in the linked list, delete at the end of the linked list)
- Traverse the linked list and output all the information in the linked list
#include <stdio.h>
#include <stdlib.h>
//Defines the structure of a linked list node
struct app
{
int a;
struct app *next; //Can save the address of the structure
};
struct app *list_head=NULL; //Head pointer of linked list
void list_print(struct app *head);
struct app *list_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_del(int a,struct app *head);
int main()
{
//1. Initialize chain header
list_head=list_HeadInit(list_head);
//2. Insert data at the end of the linked list
list_add(10,list_head);
list_add(11,list_head);
list_add(12,list_head);
list_add(13,list_head);
//3. Delete node
list_del(11,list_head);
//4. Output the data in the link node
list_print(list_head);
return 0;
}
/*
Function function: initialize the chain header -- apply for space for the chain header
*/
struct app *list_HeadInit(struct app *head)
{
if(head==NULL) //no space
{
//1. Application chain header space
head=malloc(sizeof(struct app));
//2. Initialize the chain header
head->next=NULL;
}
return head;
}
/*
Function function: insert data at the end of the linked list
int a Inserted data value
struct app *head Chain header
*/
void list_add(int a,struct app *head)
{
struct app *new_p=NULL;
struct app *next_p=head;
struct app *tmp_p; //Save the address of the previous node
//1. Apply for space and assign values to space members
new_p=malloc(sizeof(struct app));
new_p->a=a;
new_p->next=NULL;
//2. Find the end of the linked list
while(next_p!=NULL)
{
tmp_p=next_p;
next_p=next_p->next; //The pointer points to the next node
}
//3. Insert new node -- end of link
tmp_p->next=new_p;
}
/*
Function function: traverse all data in the output link
*/
void list_print(struct app *head)
{
struct app *next_p=head;
int cnt=0;
if(head!=NULL)
{
while(next_p->next!=NULL)
{
next_p=next_p->next;
printf("struct Node [%d]:a=%d\n",cnt++,next_p->a);
}
}
}
/*
Function function: delete linked list - delete according to the specified data
*/
void list_del(int a,struct app *head)
{
struct app *next_p=head;
struct app *tmp_p; //Save the address of the previous node
//1. Find the linked list to delete
if(next_p!=NULL)
{
while(next_p->next!=NULL)
{
tmp_p=next_p; //Save the address of the previous node
next_p=next_p->next; //Get the address of a valid node
if(next_p->a==a) //Determine whether to delete
{
tmp_p->next=next_p->next;
free(next_p);
}
}
}
}
3. Case: one-way circular linked list
The code is directly modified in case 2 above. The difference is that the tail node points to the head node instead of NULL.
#include <stdio.h>
#include <stdlib.h>
//Defines the structure of a linked list node
struct app
{
int a;
struct app *next; //Can save the address of the structure
};
struct app *list_head=NULL; //Head pointer of linked list
void list_print(struct app *head);
struct app *list_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_del(int a,struct app *head);
int main()
{
//1. Initialize chain header
list_head=list_HeadInit(list_head);
//2. Insert data at the end of the linked list
list_add(10,list_head);
list_add(11,list_head);
list_add(12,list_head);
list_add(13,list_head);
//3. Delete node
list_del(11,list_head);
//4. Output the data in the link node
list_print(list_head);
return 0;
}
/*
Function function: initialize the chain header -- apply for space for the chain header
*/
struct app *list_HeadInit(struct app *head)
{
if(head==NULL) //no space
{
//1. Application chain header space
head=malloc(sizeof(struct app));
//2. Initialize the chain header
head->next=head;
}
return head;
}
/*
Function function: insert data at the end of the linked list
int a Inserted data value
struct app *head Chain header
*/
void list_add(int a,struct app *head)
{
struct app *new_p=NULL;
struct app *next_p=head;
struct app *tmp_p; //Save the address of the previous node
//1. Apply for space and assign values to space members
new_p=malloc(sizeof(struct app));
new_p->a=a;
new_p->next=head;
//2. Find the end of the linked list
if(head!=NULL)
{
if(next_p->next==head) //Indicates the first insertion of a node
{
next_p->next=new_p;
//Head - < node 1 > --- head
}
else
{
while(next_p->next!=head)
{
next_p=next_p->next; //The pointer points to the next node
}
//3. Insert new node -- end of link
next_p->next=new_p;
}
}
}
/*
Function function: traverse all data in the output link
*/
void list_print(struct app *head)
{
struct app *next_p=head;
int cnt=0;
if(head!=NULL)
{
printf("Header address: %#x\n",next_p); / / header
printf("First node address:%#X \ n ", next_p - > next); / / next node address
printf("Second node address:%#X \ n ", next_p - > next - > next); / / next node address
printf("Third node address:%#x\n",next_p->next->next->next);
printf("Fourth node address:%#x\n",next_p->next->next->next->next);
while(next_p->next!=head)
{
next_p=next_p->next;
printf("struct Node [%d]:a=%d\n",cnt++,next_p->a);
}
}
}
/*
Function function: delete linked list - delete according to the specified data
*/
void list_del(int a,struct app *head)
{
struct app *next_p=head;
struct app *tmp_p; //Save the address of the previous node
//1. Find the linked list to delete
if(next_p!=NULL)
{
while(next_p->next!=head)
{
tmp_p=next_p; //Save the address of the previous node
next_p=next_p->next; //Get the address of a valid node
if(next_p->a==a) //Determine whether to delete
{
tmp_p->next=next_p->next;
free(next_p);
}
}
}
}
4. Case: create a two-way linked list loop to realize insertion, deletion and traversal
The bidirectional linked list adds a new pointer in each node to save the address of the previous node. In the current node, one uses two pointers, one saves the address of the previous node and the other saves the address of the next node.
#include <stdio.h>
#include <stdlib.h>
//Defines the structure of a linked list node
struct app
{
int a;
struct app *next; //Next node address
struct app *prev; //Previous node address
};
//Global variable declaration area
struct app *list_head=NULL; //Head pointer of linked list
//Function declaration
struct app *List_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_print(struct app *head);
void list_del(int a,struct app *head);
int main()
{
/*1. Initialize linked list*/
list_head=List_HeadInit(list_head);
/*2. Add linked list node*/
list_add(10,list_head);
list_add(11,list_head);
list_add(12,list_head);
list_add(13,list_head);
list_add(14,list_head);
/*3.Delete specified node*/
list_del(12,list_head);
/*4. Traverse and output all node information*/
list_print(list_head);
return 0;
}
/*
Function function: create chain header
*/
struct app *List_HeadInit(struct app *head)
{
if(head==NULL)
{
head=malloc(sizeof(struct app));
head->a=0;
head->next=head;
head->prev=head;
}
return head;
}
/*
Function function: add data - add data at the end of the linked list
*/
void list_add(int a,struct app *head)
{
struct app *next_p=head;
struct app *new_p=NULL;
/*1. Apply for a new node*/
new_p=malloc(sizeof(struct app));
new_p->a=a;
new_p->next=head;
/*2. Finish adding the new node*/
//Traversal linked list
while(next_p->next!=head)
{
next_p=next_p->next;
}
//Add new node
new_p->prev=next_p;
next_p->next=new_p;
//Modify the previous node address of the chain header
head->prev=new_p;
}
/*
Function function: output all data in the linked list
*/
void list_print(struct app *head)
{
struct app *next_p=head;
int cnt=0;
/*1. Forward traversal*/
while(next_p->next!=head)
{
next_p=next_p->next;
printf("node[%d]:%d\n",cnt++,next_p->a);
}
/*2. reverse traversal */
next_p=head;
while(next_p->prev!=head)
{
next_p=next_p->prev;
printf("node[%d]:%d\n",cnt--,next_p->a);
}
}
/*
Function function: delete the specified node in the linked list
*/
void list_del(int a,struct app *head)
{
struct app *next_p=head;
struct app *tmp_p=NULL;
while(next_p->next!=head)
{
tmp_p=next_p; //Save the address of the previous node
next_p=next_p->next;
if(next_p->a==a)
{
//Mode 1
tmp_p->next=tmp_p->next->next;
tmp_p->next->prev=tmp_p;
//Mode 2
//tmp_p->next=next_p->next;
//next_p->next->prev=tmp_p;
//printf("%d\n",tmp_p->a); //11
//printf("%d\n",tmp_p->next->a); //13
//printf("%d\n",next_p->next->prev->a); //11
free(next_p);
break;
}
}
}