💟 About the author: Hello, I'm Ceylan_, You can call me CC ❣️
📝 Personal homepage: Ceylan_ Blog
🏆 Blogger information: ordinary freshmen have extraordinary dreams
Column
⚡ I hope you can give me more support 😘 Progress together~ ❤️
🌈 If helpful, please pay attention ➕ give the thumbs-up ➕ Collection, if I can't, I'll try harder 💪
🌺 Definition of linked list
The chained storage of linear table is also called single chained table, which is characterized by using a group of arbitrary storage units to store the data elements of linear table. In order to represent the logical relationship between each data element ai and its subsequent data element ai+1, a1 needs to store information pointing to its subsequent content (generally the address of the subsequent content) in addition to its own information. These two parts of information constitute the storage image of data element ai, which is called node.
The node types in the single linked list are described as follows:
typedef struct LNode //Define single linked list node type
{
ElemType data; //data elements
struct LNode *next; //Point to next address
}LNode, *LinkList;🌺 Storage mode of linked list
The access of the whole linked list must start from the pointer, and the head pointer points to the storage location of the first node of the linked list. At the same time, since the last element has no direct successor, the pointer of the last node of the single linked list is NULL
Let's think about it. If we use a linked list to store [Ceylan], what is its logical state?
First, there should be a header pointer L, which points to the first element 'C'. Through the information of the node where 'C' is located, you can access the location of the next node 'e', and so on, you can find the whole [Ceylan]
🌺 Initialization of single linked list
The initialization of a single linked list is to create a new empty single linked list.
🔺 Implementation principle
one ️⃣ Generate a new node as the head node, and point to the head node with the head pointer L
two ️⃣ The header node points to null
💬 Code demonstration
Status InilList(LinkList &L)
{//Build an empty linked list L
L=new LNode; //Generate a new node as the head node, and point to the head node with the head pointer L
L->next=NULL; //The header node points to null
return OK;
}🌺 Establishing single linked list by head interpolation
🔺 Implementation principle
one ️⃣ Create an empty table and generate a new node
two ️⃣ Store the data in the data field of the new node
three ️⃣ Insert the new node into the header of the current linked list, that is, after the header node
💬 Code demonstration
void CreateList_H(LinkList &L,int n)
{
L=new LNode;
L->next=NULL; //First, create an empty linked list of the leading node
for(int i=0;i<n;i++)
{
p=new LNode; //Generate new node * p
cin>>p->data; //Enter the data of the p node
p->next=L->next;L->next=p; //Insert the new node * p after the head node
}
} ❗ ⅶ note:
Because each insertion is at the head of the linked list, you should input data in reverse order. The input order is opposite to the logical order in the linear table.
🌺 Establishing single linked list by tail interpolation
🔺 Implementation principle
one ️⃣ Create an empty table and generate a new node
two ️⃣ Store the data in the data field of the new node
three ️⃣ Insert the new node into the tail of the current linked list
💬 Code demonstration
void CreateList_R(LinkList &L,int n)
{
L=new LNode; //First, create an empty linked list of the leading node
r=L; //The tail pointer points to the head node
for(int i=0;i<n;i++)
{
p=new LNode; //Generate new node * p
cin>>p->data; //Enter the data of the p node
p->next=NULL;r->next=p; //Insert the new node * p after the tail node * r
r=p
}
} 🌺 Find node value by sequence number
🔺 Implementation principle
one ️⃣ Start from the first node and search down one by one along the pointer next until the # i # node is found,
two ️⃣ If not found, return the last pointer field NULL
💬 Code demonstration
LNode *GetElem(LinkList L,int i)
{
int j=1; //Count, initially 1
LNode *p=L->next; //The head node pointer is assigned to p
if(i==0)
return L; //If i is 0, the header pointer is returned
if(i<1)
return NULL; //NULL if i is invalid
while(p&&j<i) //Start from the first element to the i-th node
{
p=p->next;
j++;
}
return p; //Pointer of node i
} 🌺 Find nodes by value
🔺 Implementation principle
one ️⃣ Starting from the first node, the pointer next searches down the values one by one until a matching value is found
two ️⃣ If no NULL field is found, the last pointer is returned
💬 Code demonstration
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p=L->next;
while(p!=NULL&&p->data!=e) //Start from the first node to find the node with data field e
{
p=p->next;
}
return p; //Return the node pointer after finding it, otherwise return NULL
} 🌺 Insert Knot
Insert the new node with the value of x into the ith position of the single linked list.
🔺 Implementation principle
one ️⃣ Call the search function by sequence number to find the i-1 node, assuming that the returned node is * p
two ️⃣ Make the pointer field of the new node * s point to the subsequent nodes of * p
three ️⃣ Make the pointer field of node * p point to the newly inserted node * s
💬 Code demonstration
p=GetElem(L,i-1) //Find the precursor node at the insertion position s->next=p->next; //The pointer field of the new node * s points to the subsequent nodes of * p p->next=s; //Make the pointer field of node * p point to the newly inserted node * s
🌺 Delete Vertex
Delete the ith node of the single linked list.
🔺 Implementation principle
one ️⃣ Call the search function by sequence number to find the ith node, assuming that the returned node is * p
two ️⃣ Point the * p pointer field next to the lower node
p=GetElem(L,i-1) //Find and delete the precursor node at the location q=p->next; //Make q point to the deleted node p->next=q->next; //Disconnect * q node from the chain free(q); //Release the storage space of the node
🌺 Daily golden sentence
On the road of life, we never retreat from the whole body, enjoy the success and get something for nothing. If you don't work hard, you'll be out.
I am not talented. If there are mistakes, you are welcome to correct them in the comment area. Please pay attention if it is helpful ➕ give the thumbs-up ➕ If I can't, I'll try again 💪💪💪
