The concept of linked list and the depth analysis of single linked list

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.

Published 9 original articles, won praise 7, visited 3204
Private letter follow

Added by seran128 on Sat, 08 Feb 2020 11:59:00 +0200