Concept of linked list:

The introduction of linked list is to solve the dilemma of inserting and deleting arrays. It can be seen as a dynamically expanded (real-time enlarged / reduced) array. The linked list is composed of multiple nodes connected with each other, and the connection is realized by the pointer. The node is not a point, but a section, including the effective data area and pointer. The effective data office is used to store data, and the pointer is used to point to the next node as a whole.

Single chain table analysis:

For linked list (including single linked list and double linked list), it is important to understand the concept and learn how to use and implement the principle. Focus on the insertion, traversal and deletion of linked list.

Example of single chain table implementation:

#include <stdio.h> #include <strings.h> #include <stdlib.h> /***********Used to build a node in a linked list************/ // Building a linked list of nodes struct node { int data; // Effective data struct node *pNext; // Pointer to the next node }; /***************************************************/ /****************Used to create a node in a linked list*************/ // Return value: pointer to the first address of a newly created node in our function //Data is the data stored in the node struct node * create_node(int data) { struct node *p = (struct node *)malloc(sizeof(struct node)); if (NULL == p) { printf("malloc error.\n"); return NULL; } // Clean up the heap memory applied to memset(p, 0,sizeof(struct node)); // Filled node p->data = data; p->pNext = NULL; return p; } /************************************************/ /********************To implement the tail insertion of linked list nodes***************/ void insert_tail(struct node *pH, struct node *new) { // Idea: traverse backward from the head pointer to the original last node. It turns out that pNext in the last node is NULL. Now we just need to change it to new. When added, the new node becomes the last. // Calculate the total number of (cnt) nodes after adding new nodes, and then write this number into the head node //pH is the head pointer, and new is the overall head address of the new node int cnt = 0; // Insert in two steps // First, find the last node in the list struct node *p = pH; while (NULL != p->pNext) { p = p->pNext; // One node back cnt++; } // Second, insert the new node at the end of the last node p->pNext = new; pH->data = cnt + 1; //Represents the data area in the head node (that is, the place where the number of nodes is stored) } /************************************************/ /********************To implement the head insertion of linked list nodes***************/ void insert_head(struct node *pH, struct node *new) { // Step 1: the next of the new node points to the original first node new->pNext = pH->pNext; // Step 2: the next of the header node points to the address of the new node pH->pNext = new; // Step 3: add 1 to the count in the header node pH->data += 1; } /************************************************/ /********************To realize the traversal of linked list***************/ // Traverse single chain table, pH is the head pointer to single chain table, and the traversed node data is printed out void traversing_list(struct node*pH) { //PH - > data / / the data of the header node is not the normal data of the linked list. Do not include it struct node *p = pH; // After the head pointer is the head node printf("-----------Start traversal-----------\n"); while (NULL != p->pNext) //P - > pnext indicates whether the skip over node (i.e. the first valid node) is the last node { p = p->pNext; // Go to the next node, which is loop increment printf("node data: %d.\n", p->data); } printf("-------------Traversal completion-------------\n"); } /************************************************/ /********************Used to delete nodes from the linked list***************/ // Delete the node from the pH of the list. The data of the node to be deleted is the data in the data area int delete_node(struct node*pH, int data) { // Find the node to be deleted and search by traversing the linked list struct node *p = pH; // Used to point to the current node struct node *pPrev = NULL; // Used to point to the previous node of the current node while (NULL != p->pNext) // Is it the last node { pPrev = p; // Save p before going to the next node p = p->pNext; // Go to the next node, which is loop increment // Judge whether this node is the one we are looking for if (p->data == data) { // Node found, handle this node // There are two cases: one is to find a common node, the other is to find a tail node /*The difficulty of deleting a node lies in that it accesses each node in turn through the traversal of the linked list. After finding the node, p points to the node. However, to delete the node, the key is to operate the previous node, but at this time, there is no pointer to the previous node, so it cannot be operated. The solution is to add a pointer to the previous node of the current node (pPrev)*/ if (NULL == p->pNext) { // Tail node pPrev->pNext = NULL; // The previous node of the original tail node becomes a new tail node free(p); // Release the memory of the original tail node } else { // Common node pPrev->pNext = p->pNext; // The previous node of the node to be deleted is connected with its next node, so the node to be deleted is picked out free(p); } // Exit the program after processing return 0; } } // We haven't found it here, which means there is no node we want in the linked list printf("This node was not found.\n"); return -1; } /************************************************/ int main(void) { struct node *pHeader = create_node(0); //Create a head node insert_head(pHeader, create_node(11)); insert_head(pHeader, create_node(22)); insert_head(pHeader, create_node(33)) printf("------------------Traverse before delete-------------\n"); traversing_list(pHeader); delete_node(pHeader, 22); printf("------------------Traverse after deletion-------------\n"); traversing_list(pHeader) return 0; }

Note: the main function of the program is to create a linked list with three nodes by means of head insertion, then traverse the linked list, delete one node in the linked list, and then traverse.

For the single chain table, as long as you can master the content of this program, because the program includes the head pointer, head node, node creation, node head insertion, node tail insertion, chain table traversal, chain table node deletion key content.