Tip: after the article is written, the directory can be generated automatically. Please refer to the help document on the right for how to generate it
preface
Recently, I learned about the single linked list and did some exercises related to the linked list. Next, I will make a summary of the single linked list in C
1, What is a single linked list
As shown in the figure above, this is a simple single chain to express intention. (ppt production is a little rotten)
First of all, before answering what is a single linked list, let's briefly talk about what is a linked list. Linked list is a kind of data structure, and the array learned before is also a kind of data. Linked list and array are the two simplest data structures.
The single linked list, as its name suggests, is a one-way linked list. As shown in the above diagram, each block is a node of the linked list. Each node generally contains at least two variables, val and next. val refers to the value (1, 2 and 3 in the above figure), and next is the structure pointer variable, which points to the latter node. The most special nodes in a single linked list are the head node and the tail node. The head node refers to the front node. Why is the head node special? Because the directivity of the single linked list is one-way, that is, if we want to traverse all nodes, we need to traverse from the beginning. The tail node is a node pointing to a NULL null node. The tail node in the figure above is a 3 node. Note that it is not a NULL node!
2, Code implementation of single linked list
1. Definition of linked list
The IDE used here is codebooks
The code is as follows (example)
//Header file
#include<stdio. h> / / standard I / O header file
#include<stdlib. h> / / contains the system functions commonly used in C
// Macro definition related variables
#define TYPE struct ListNode / / macro defines the structure variable name
//Define linked list and create structure
struct ListNode
{
int val;
// Declare the structure pointer variable, pointing to the structure - linked list
struct ListNode* next;
};
2. Implementation of linked list
1) static implementation, (main function) code entry
int main(void)
{
TYPE *head, *t; //Declaration header node
struct ListNode a, b, c; //Declare three linked list nodes
/* 1. A.B Then A is the object or structure
2. A->B Then A is the pointer, -> indicates member extraction, that is, element variables in the structure, such as val and next used here
*/
a.val = 1; //Corresponding member assignment
a.next = &b; //Label node pointing
b.val = 2;
b.next = &c;
c.val = 3;
c.next = NULL;
head = &a; //Head node position
t = head;
while(t != NULL)
{
printf("%d\n",t->val);
t = t->next;
}
return 0;
}
2) dynamic implementation
Dynamic memory allocation header file needs to be introduced
#include<malloc. h> / / dynamically allocate memory function header file
The definition of linked list declaration is the same as above
Create linked list function
TYPE* creat(void)
{
TYPE* head;
//Declare two nodes
TYPE* a, *b;
//Declare the number of nodes variable and initialize to 0
int number = 0;
//Dynamically allocate node memory space and open up nodes
a = b = (TYPE*)malloc(sizeof(struct ListNode));
printf("input: val = \n");
scanf("%d", &a->val);
head = NULL;
//When 77 is entered, the cycle ends
while(a->val != 77)
{
++ number;
//When the number of nodes is 1, the header pointer points to the first node information
if(number == 1)
{
head = a;
}
else
{
//When the number of nodes is greater than 1, save the current node information with next
b->next = a;
}
//Save current node information
b = a;
a = (TYPE*)malloc(sizeof(struct ListNode));
scanf("%d",&a->val);
}
//After the loop ends, the tail node is assigned NULL
b->next = NULL;
//Return head node
return (head);
}Loop output main function
int main(void)
{
TYPE *kk;
//Assign kk to head
kk = creat();
//The default linked list is not empty
if(kk != NULL)
{
//Cycle to print the val value of the linked list until the node is empty
do{
printf("\n val=%d\n", kk->val);
kk = kk->next;
}while(kk != NULL);
}
return 0;
}
Output results
The definition of the creat e() function refers to https://blog.csdn.net/xiaoxiaodawei/article/details/104807198
The dalao's explanation of the single linked list is far better than mine. If you need it, you might as well have a look.
3, Related exercises and problem solutions
I think learning programming is inseparable from brushing questions. The following questions are from leetcode website
1. Delete node in linked list
Write a function so that it can delete a given (non end) node in a linked list. The only parameter passed into the function is the node to be deleted.
For example, a linked list = [4,5,1,9], as shown in the following figure
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: given the second node with a value of {5} in your linked list, after calling your function, the linked list should be 4 - > 1 - > 9
Link: https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
The template of the topic is as follows
**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void deleteNode(struct ListNode* node) {
}This question does not give the head node of the linked list, but the specific node to be deleted. What should I do at this time?
It's very simple. Just make the next node of this node equal to it and change its direction to the next node
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void deleteNode(struct ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}2. Delete the penultimate node
Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.
Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]
Title Link https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
Topic template
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
}1) method 1: traverse to get the length, and then traverse again to delete the node.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int getlength(struct ListNode* head){
int len = 0;
while(head){
len++;
head = head->next;
}return len;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* newLN = malloc(sizeof(struct ListNode));
newLN->val = 0; newLN->next = head;
int len = getlength(head);
struct ListNode* cur = newLN;
for(int i = 1; i < len - n + 1; ++i){
cur = cur->next;
}
cur->next = cur->next->next;
struct ListNode* ans = newLN->next;
free(newLN);
return ans;
}
2) method 2: stack implementation
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct Stack{
struct ListNode* val;
struct Stack* next;
};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* dummy = malloc(sizeof(struct ListNode));
dummy->val = 0, dummy->next = head;
struct Stack* stk = NULL;
struct ListNode* cur = dummy;
while(cur){
struct Stack* tmp = malloc(sizeof(struct Stack));
tmp->val = cur, tmp->next = stk;
stk = tmp;
cur = cur->next;
}
for(int i=0; i<n; ++i){
struct Stack* tmp = stk->next;
free(stk);
stk = tmp;
}
struct ListNode* prev = stk->val;
prev->next = prev->next->next;
struct ListNode* ans = dummy->next;
free(dummy);
return ans;
}3. Reverse linked list
Define a function, input the head node of a linked list, invert the linked list and output the head node of the inverted linked list.
Example:
Input: 1 - > 2 - > 3 - > 4 - > 5 - > null
Output: 5 - > 4 - > 3 - > 2 - > 1 - > null
Title Link: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
}1) iterative implementation
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
// The pre declaration node is NULL and NULL initially
struct ListNode* prev = NULL;
// Declaration node, initially the given header node
struct ListNode* curr = head;
// Loop when the node is not null
while(curr)
{
// Declare the node and initialize it as the next node of curr
struct ListNode* next = curr -> next;
// Assign the previous node to the next node of curr (current node)
curr -> next = prev;
// The previous node is assigned as the current node
prev = curr;
// curr (current node) is assigned to the original next node
curr = next;
}
// Return to the previous node, which is the last non empty node of the original linked list
return prev;
}
2) recursive implementation
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
if(head == NULL || head -> next == NULL)
{
return head;
}
// Declare a new head node and initialize recursively. Finally, the new head node becomes the original last node
struct ListNode* newHead = reverseList(head -> next);
// Assign node k+1+1 to k
head -> next -> next = head;
// Assign k+1 to null
head -> next = NULL;
//Return to new header node
return newHead;
}summary
In fact, a single linked list can be understood as a data field. Each node has corresponding data information and can only point to the latter node. The tail node of a limited single linked list will point to NULL