catalogue

3: Find the number of elements in the single linked list

4: Insertion and deletion of single linked list and release of all nodes

# 1: Node creation

Create nodes through structures in c

Let's take the single linked list as an example and look at the following code. This is the structure type that creates a node

typedef struct node {//Structure creation int date;//Data domain struct Node* next;//Pointer field }Node,*Link;//Alias. One is the structure type and the other is the pointer to the structure type

We create a node through malloc to reference #include < malloc. H >

The return value of malloc function is void * universal pointer type. This pointer type cannot be operated and can be forcibly converted to any type

Since l1 is of Link type, it is converted to Link type

Link l1=(Link) malloc(sizeof(Node));//Create a node. The return value of malloc is void * and can be forcibly converted to any type

# 2: Traversal of linked list

It is easy to traverse the linked list by moving the pointer, but not p + +, because the linked list is logically continuous and physically discontinuous. Look at the following code. There is a header node here, and the next node of the header node stores data

void Display(Link l1) {//Traversal of single linked list Link p = l1->next; while (p) {//Determine whether p is empty printf("%d ", p->date); p = p->next; } }

# 3: Find the number of elements in the single linked list

This is still traversal

int Num(Link l1) {//Calculate from the initial node. If you calculate from the initial node, count=1 int count = 0; while (l1) {//Judge whether l1 is empty l1 = l1->next; count++; } return count; }

# 4: Insertion and deletion of single linked list and release of all nodes

### insert

The precursor is easier to use than the successor. Ouch

The pointer points to the previous node of the inserted node, that is, the precursor

int insertNode(Link l1, int n, int x) {//l1 is the head pointer of the linked list, n is the insertion position, and x is the inserted data int count = 0;//Record where the pointer went Link p = l1->next; while (p != NULL && count < n - 1) {//n is the insertion position. We need to move the pointer to the precursor position because the precursor ratio //Subsequent easy to use [0-n-1] is n-1 number p = p->next; count++; } if (p == NULL) {//The linked list is not long enough return 0; } else { Link node = (Link)malloc(sizeof(Node));//Node to insert node->date = x; node->next = p->next;//Insertion algorithm p->next = node; } return 1; }

### delete

Two pointers need to be scanned one after the other until the previous pointer is scanned to the node to be deleted. Before scanning, judge whether the linked list is not empty

Link my_delete(Link head, int n) { if (head == NULL || head->next == NULL) {//Judge whether the linked list passed in is an empty linked list return 0; } Link p = head->next;//Initializes two previous and subsequent pointers Link q = head; while (p) {//Prevention of cross-border if (p->date == n) {//If equal, delete q->next = p->next; free(p); return 1; } else {//The two pointers move forward q = p; p = p->next; } } return 0; }

### Release all nodes

void my_free(Link head) { while (head->next) {//Release if not empty Link p = head; head = head->next; free(p); } free(head);//Release header node }

# 5: Implementation of single linked list (each time a new node is created, the next field of the node must be set to empty)

### Head insertion

Suppose we have an array with n elements. We need to put the elements in a single linked list

The order of inserting elements by head interpolation is reversed

#include<stdio.h> #include<malloc.h> typedef struct node { int date; struct node* next; }Node,*Link; Link newList(int *arr, int n) { Link head = (Link)malloc(sizeof(Node)) ;//Create a header node and make the pointer field null head->next= NULL; for (int i = 0; i < n; i++) { Link node = (Link)malloc(sizeof(Node));//Each cycle creates a new node node->date = *arr++;//Put the elements in the array into the data field of the node node->next = head->next;//Set the pointer field of the node to null head->next = node;//The head node points to the new node } return head;//Return header node } int main() { int arr[5] = { 1,2,3,4,5 }; Link p=newList(arr, 5); while (p->next) { p = p->next; printf("%d ", p->date); } }

### Tail interpolation

Link newList2(int *arr, int n) { Link head = (Link)malloc(sizeof(Node));//When creating a header node, set its pointer and to null before creating a node head->next = NULL; Link rest = head;//At the beginning, the tail node and head receive you in one position for (int i = 0; i < n; i++) { Link node = (Link)malloc(sizeof(Node)); node->date = *arr++; rest->next = node;//Point the tail node pointer field to the new node rest = node;//Point the tail node to the new node } rest->next = NULL;//Set the pointer field of the tail node to null, otherwise a wild pointer will appear, pointing to the unknown field return head; }