# The concept of linked list and the depth analysis of single 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
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)
}

/************************************************/

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
return -1;
}

/************************************************/
int main(void)
{
printf("------------------Traverse before delete-------------\n");