1. Single linked list ： Single linked list is a data structure with linked access , A set of storage units with arbitrary addresses is used to store the data elements in the linear table .
2. Head pointer ： Is not a pointer to a header node , Refers to the pointer to the head node , Whether the linked list is empty or not , None of the header pointers are null .
3. Head node ： The node placed before the first node （“ Zero node ”）, The data field can not store things , You can also store linked list information （ Such as linked list length ）.

Single linked list logical structure diagram （ Baidu ）：

<> The basic operation is as follows ：

<> Storage structure of single linked list
typedef struct Node // Storage structure of single linked list ,Node Is the structure type name ,"stuct Node" Is the data type , as ：int It is also a data type {
int data; struct Node* next; }Node, * LinkList;
int InitLinkedList(LinkList* L) // initialization , Formal parameter L Is a secondary pointer { *L = (Node*)malloc(sizeof(Node
)); // Head node application address if (*L == NULL) { printf(" Failed to apply for space \n"); exit(0); } head = *L;
// The header pointer points to the header node tail = *L; // The tail pointer points to the tail node , Only initialized 1 Nodes , It is both a head node and a tail node (*L)->data = 0;
// The header node data field may not store data , The length of the linked list is stored here (*L)->next = NULL; // Initially empty linked list , That is, the head node pointer points to null return 1; }
LinkList Head_CreatList(LinkList* L) // Creating single linked list by head interpolation , After creation, the order of elements is opposite to that of input . Tail interpolation { int x;
// Newly inserted node value printf(" Enter the value of the element to be inserted \n"); scanf("%d", &x); while (x != 9999)
// input 9999 When, it means the end { LinkList s = (Node*)malloc(sizeof(Node)); // Create a new node s->data = x;
// Enter the value of the node s->next = (*L)->next; (*L)->next = s; (*L)->data++; // Single linked list length plus one printf(
" Insert successful \n"); printf(" Enter the value of the element to be inserted ( input 9999 End insert )\n"); scanf("%d", &x); } return *L;
LinkList Tail_CreatList(LinkList* L) // Creating single linked list by tail interpolation , Formal parameter L Is a secondary pointer { int x; // Newly inserted node value
printf(" Enter the value of the element to be inserted \n"); scanf("%d", &x); while (x != 9999) // input 999 When, it means the end {
LinkList s= (Node*)malloc(sizeof(Node)); // Create a new node s->data = x; // Enter the value of the node tail->
next= s; tail = s; // The tail pointer points to the new tail node (*L)->data++; // Single linked list length plus one printf(" Insert successful \n"); printf
(" Enter the value of the element to be inserted ( input 9999 End insert )\n"); scanf("%d", &x); } tail->next = NULL; // The pointer field of the tail node is set to null
<> Return bit sequence i Node value of GetElem(LinkList L, int i)
int GetElem(LinkList L, int i) // Return bit sequence i Node value of , The header node does not store data , Deemed location 0 { int j = 1;
// Slave bit order 1 Start looking , Skip over node LinkList p = L->next; // The header node pointer is assigned to p,p Point to No 1 Nodes . The first node is the second node 0 Nodes if (i == 0
) return L->data; //i be equal to 0 Is to return the value of the header node , Existing single linked list length , Other information can also be stored if (i < 1 || i>
LinkListLength(L)) // Illegal search location return -9999; // return -9999 Indicates that the query bit order is illegal while (p && j < i)
// Find the second node from the first node i Nodes ,P by NULL or j>=i Exit on { p = p->next; j++; } return p->data; }
<> By value e Find node bit order LocateElem(LinkList L, int e)
int LocateElem(LinkList L, int e) // By value e Find node bit order { int k = 1; LinkList p = L->next
; //p Point to the first node , Not a header node while (p && p->data != e) { p = p->next; k++; } if (p)
<> The first i Inserts the specified element at a location eLinkListInsert(LinkList* L, int i, int e)
int LinkListInsert(LinkList* L, int i, int e) // The first i Inserts the specified element at a location e { int j = 1;
LinkList p, s; p = *L; while (p && j < i) // Looking for the first i-1 Nodes { p = p->next; j++; } if (
!p || j > i) return 0; // Illegal insertion position s = (Node*)malloc(sizeof(Node)); // Dynamically allocate memory s->
data= e; s->next = p->next; p->next = s; (*L)->data++; // Single linked list length plus one return 1; }
<> Delete bit order is i Node of LinkListDelete(LinkList* L, int i, int* e)
int LinkListDelete(LinkList* L, int i, int* e) // Delete bit order is i Node of , Combined use e Returns its element value {
LinkList p, q; //p The precursor pointing to the deleted node ,q Point to deleted node int j = 1; // Start from the first node p = *L; //p Point to head node
while (p->next && j < i) // Traversal search i-1 Nodes { p = p->next; j++; } if (!(p->next))
// if p->next=NULL, At this time, the length of the linked list may be less than i return 0; q = p->next; //q Point to the deleted node p->next = q->next
; // take *q Disconnect from linked list *e = q->data; // take q The data in the node is transmitted to e free(q); // Free memory (*L)->data--;
// The length of the single linked list is reduced by one return *e; }
//p Point to the first node , Not a header node , The head node is regarded as the second node 0 Nodes while (p) { q = p->next; //q point p Next node of free(p);
// release p; After completion, the first node is q p = q; // Give Way p Point to the first node , Repeat the above operation } (*L)->next = NULL; // Head node pointer assignment NULL
//free(*L); // The following two steps will destroy the single linked list //head = NULL; (*L)->data = 0; // Set the length of the single linked list to 0 return 0; }
->next) // if p=NULL, Then the traversal is complete { p = p->next; k++; } return k; }
int ListTraverse(LinkList L) // Traversal access to the entire table L { Node* p; for (p = L->next; p != NULL;
p= p->next) printf("%-5d", p->data); return 0; }
**

<> All modules are tested together Compiling environment ：vc 6.0:

**
#include <stdio.h> #include <stdlib.h> typedef struct Node
// Storage structure of single linked list ,Node Is the structure type name ,"stuct Node" Is the data type , as ：int It is also a data type { int data; struct Node*
next; }Node, * LinkList; // there Node yes "stuct Node" Variable of type , It can be compared with the one above - Structure type name - Duplicate name . struct
Node* head = NULL; // Head pointer struct Node* tail = NULL; // Tail pointer , Prepare for tail insertion int
; // Creating single linked list by head interpolation , After creation, the order of elements is opposite to that of input . Tail interpolation LinkList Tail_CreatList(LinkList* L);
// Creating single linked list by tail interpolation , Formal parameter L Is a secondary pointer int GetElem(LinkList L, int i); // Return bit sequence i Node value of , The header node does not store data , Deemed location 0
int i, int e); // The first i Inserts the specified element at a location e int LinkListDelete(LinkList* L, int i, int* e);
// Delete bit order is i Node of , Combined use e Returns its element value int LinkListClear(LinkList* L); // Empty single linked list int
int main() { LinkList L = NULL; int i, e; //i Is bit order ,e Is the element value if (InitLinkedList(&L))
printf(" Initialization succeeded \n"); //Head_CreatList(&L); // Header insertion initialization Tail_CreatList(&L); // Tail interpolation initialization
ListTraverse(L); // Traversal output printf("\n Enter the sequence number to find \n"); scanf("%d", &i); printf(
" The checked node value is %d\n", GetElem(L, i)); // Find the element value corresponding to the bit order printf("\n Enter the value of the element you want to find \n"); scanf("%d",
&e); if (LocateElem(L, e)) printf(" The bit order of the checked node is %d\n", LocateElem(L, e)); // Find the bit order corresponding to the element value
else printf(" Query failed \n"); printf(" Enter the bit order to be inserted i And values e\n"); scanf("%d%d", &i, &e); if (
LinkListInsert(&L, i, e)) // insert { printf(" Insert successful , Current element is \n"); ListTraverse(L); } else
printf(" Insert failed \n"); printf("\n Enter the bit order to be deleted \n"); scanf("%d", &i); LinkListDelete(&L, i
, &e); printf(" The deleted node element value is ：%d\n", e); printf(" After deletion \n"); ListTraverse(L); // Traversal output
printf("\n Current length %d\n", L->data); // I store the length of the linked list in the value field of the head node , You can also call functions LinkListLength(L)
LinkListClear(&L); printf(" Length after emptying is %d\n", LinkListLength(L)); return 0; } int
InitLinkedList(LinkList* L) // initialization , Formal parameter L Is a secondary pointer { *L = (Node*)malloc(sizeof(Node));
// Head node application address if (*L == NULL) { printf(" Failed to apply for space \n"); exit(0); } head = *L; // The header pointer points to the header node
tail= *L; // The tail pointer points to the tail node , Only initialized 1 Nodes , It is both a head node and a tail node (*L)->data = 0;
// The header node data field may not store data , The length of the linked list is stored here (*L)->next = NULL; // Initially empty linked list , That is, the head node pointer points to null return 1; }
LinkListHead_CreatList(LinkList* L) // Creating single linked list by head interpolation , After creation, the order of elements is opposite to that of input . Tail interpolation { int x;
// Newly inserted node value printf(" Enter the value of the element to be inserted \n"); scanf("%d", &x); while (x != 9999)
// input 999 When, it means the end { LinkList s = (Node*)malloc(sizeof(Node)); // Create a new node s->data = x;
// Enter the value of the node s->next = (*L)->next; (*L)->next = s; (*L)->data++; // Single linked list length plus one printf(
" Insert successful \n"); printf(" Enter the value of the element to be inserted ( input 9999 End insert )\n"); scanf("%d", &x); } return *L;
// Return single linked list address } LinkList Tail_CreatList(LinkList* L) // Creating single linked list by tail interpolation , Formal parameter L Is a secondary pointer { int x;
// Newly inserted node value printf(" Enter the value of the element to be inserted \n"); scanf("%d", &x); while (x != 9999)
// input 999 When, it means the end { LinkList s = (Node*)malloc(sizeof(Node)); // Create a new node s->data = x;
// Enter the value of the node tail->next = s; tail = s; // The tail pointer points to the new tail node (*L)->data++; // Single linked list length plus one printf(
" Insert successful \n"); printf(" Enter the value of the element to be inserted ( input 9999 End insert )\n"); scanf("%d", &x); } tail->next =
NULL; // The pointer field of the tail node is set to null return *L; // Return single linked list address } int GetElem(LinkList L, int i)
// Return bit sequence i Node value of , The header node does not store data , Deemed location 0 { int j = 1; // Slave bit order 1 Start looking , Skip over node LinkList p = L->next;
// The header node pointer is assigned to p,p Point to No 1 Nodes . The first node is the second node 0 Nodes if (i == 0) return L->data;
//i be equal to 0 Is to return the value of the header node , Existing single linked list length , Other information can also be stored if (i < 1 || i> LinkListLength(L)) // Illegal search location
return -9999; // return -9999 Indicates that the query bit order is illegal while (p && j < i)
// Find the second node from the first node i Nodes ,P by NULL or j>=i Exit on { p = p->next; j++; } return p->data; } int
LocateElem(LinkList L, int e) // By value e Find node bit order { int k = 1; LinkList p = L->next;
//p Point to the first node , Not a header node while (p && p->data != e) { p = p->next; k++; } if (p)
LinkList* L, int i, int e) // The first i Inserts the specified element at a location e { int j = 1; LinkList p, s; p = *L;
while (p && j < i) // Looking for the first i-1 Nodes { p = p->next; j++; } if (!p || j > i) return 0;
// Illegal insertion position s = (Node*)malloc(sizeof(Node)); // Dynamically allocate memory s->data = e; s->next = p->
next; p->next = s; (*L)->data++; // Single linked list length plus one return 1; } int LinkListDelete(
LinkList* L, int i, int* e) // Delete bit order is i Node of , Combined use e Returns its element value { LinkList p, q;
//p The precursor pointing to the deleted node ,q Point to deleted node int j = 1; // Start from the first node p = *L; //p Point to head node while (p->next &&
j< i) // Traversal search i-1 Nodes { p = p->next; j++; } if (!(p->next))
// if p->next=NULL, At this time, the length of the linked list may be less than i return 0; q = p->next; //q Point to the deleted node p->next = q->next
; // take *q Disconnect from linked list *e = q->data; // take q The data in the node is transmitted to e free(q); // Free memory (*L)->data--;