catalogue  catalogue 

Sequence table  Single linked list (without additional header node) 
preface
 In the previous section, we implemented the basic operations of the sequence table. In this section, we will learn about the single linked list (not the leading node), and realize some basic operations and precautions of the single linked list.
1. Definition of single linked list

Single linked list is the simplest linked list representation in the linked list, also known as linear linked list. The linked list is discontinuous. The relationship between nodes is represented by pointers. A node contains two fields:
Data field: generally represented by data, which stores a data element
Pointer field: store a pointer to the starting storage address of the next node, which plays the role of linking two nodes 
Structure of single linked list
Head: head pointer, pointing to the first node
datan: tail node, no successor, and next points to NULL
If head=NULL, the linked list is empty.
Relationship between each node:
First node and head pointer: a1=head;
The first and second nodes: A2 = A1  > next;
...
The last node: a (n) = a (n1)  > next, a (n)  > next = null
2. Characteristics of single linked list
 The length is easy to expand
 The logical order may not be consistent with the physical order
 Data can be stored continuously or discontinuously
 Each node has a pointer field, which consumes a lot of storage space
3. Basic operation of single linked list
1. Header file
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool. h> / / bool header file typedef int SLTDataType;//Rename to facilitate changing the data type typedef struct SListNode { SLTDataType data; //Data domain struct SListNode* next; //Pointer field }SLTNode;
2. Initialization
 Initialization, open up space for the header pointer, and set it to null after successful development.
void SListInit(SLTNode** phead) { assert(phead); *phead = (SLTNode*)malloc(sizeof(SLTNode)); if (*phead == NULL) { perror("SListInit"); return; } (*phead) = NULL; }
3. Print
 Traverse according to the structure of the single linked list. Remember not to traverse with the head pointer. Rename the head pointer to p for traversal, which is highly readable
//ergodic void SListPrint(SLTNode* phead) { SLTNode* p = phead; while (p) { printf("%d>", p>data);//print data p = p>next;//Point to the next node and know that the node is NULL } printf("NULL\n"); }
4. Create a new node
 malloc opens up memory to node. If the development fails, exit. If the development succeeds, set node  > data to x and node  > next to null
//Create node SLTNode* BuySListNode(SLTDataType x) { SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); if (node == NULL) { perror("BuySListNode"); exit(1); } node>data = x; node>next = NULL; return node; }
5. Tail insertion
 When it is an empty table, it is equivalent to inserting a node at the head of the linked list. The pointer needs to be modified: newnode  > next = * pphead* pphead = newnode;
 In case of non empty table, insert a new node newnode after the next node of current, and the pointer needs to be modified:
newnode>next = tail>next; tail>next = newnode;  Here, the BuySListNode function is used to create a new node, so only write current  > next = newnode; Readers can change according to their own implementation methods
void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); if (*pphead == NULL)//If the linked list is NULL, the first node address is given to the head node { SLTNode* newnode = BuySListNode(x);//Create a new node *pphead = newnode;//Give the new node address to the head node } else { SLTNode* tail = *pphead; //When a node exists while (tail>next)//Here, you can judge whether the next node is empty. You cannot judge whether the node is empty. Otherwise, you will directly find the end. If the end is NULL, the insertion will fail { tail = tail>next; } SLTNode* newnode = BuySListNode(x);//Call the function to create a new node tail>next = newnode; } }
6. Tail deletion
 When there is only one node, save the initial node with tail, and modify the pointer: tail = *pphead; free(tail); tail=NULL;
 When there are multiple nodes, save the precursor node with prev, and tail is the successor node. Traverse the linked list, find the tail node, and modify the pointer: prev = tail; tail = tail>next; free(tail); prev>next = NULL;
void SListPopBack(SLTNode** pphead) { assert(pphead); //Violent way assert(*pphead);//Check whether the linked list is empty //Gentle way /*if (*pphead == NULL) { return; }*/ SLTNode* prev = NULL; SLTNode* tail = *pphead; if (tail>next == NULL) { free(tail); tail = NULL; } else { while (tail>next != NULL) { prev = tail; tail = tail>next; } free(tail); prev>next = NULL; } }
7. Head insert
 As the name suggests, the header is inserted before the first node to become the first node. Modify the pointer: newnode  > next = head; head = newnode;
void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); newnode>next = *pphead;//Point to the first node *pphead = newnode;//The newnode address is given to pphead to become the first node }
8. Header deletion
1. Header deletion: delete the first node, make the header pointer point to the second node, and modify the pointer: next = head  > next; head = next;
void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* nextnode = (*pphead)>next; *pphead = nextnode; free(*pphead); *pphead = NULL; }
9. Insert
 A single linked list is usually inserted into a node after the pos position
 Header, modify the direction: newnode  > next = head; head = newnode;
 It is neither the first node nor the last node. Modify the direction: newnode  > next = current  > next; current>next = newnode;
 The last node is modified to point to: newnode  > next = current  > next; current>next = newnode;
//Insert after pos position void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySListNode(x); newnode>next = pos>next; pos>next = newnode; }
10. Delete
 Delete at the first node and modify the direction: del = head; head = head>next;
 Delete in the middle or tail, and modify to: del = current  > next; current>next = del>next;
void SListEraseAfter(SLTNode* pos) { assert(pos); assert(pos>next); SLTNode* nextnode = pos>next; pos>next = pos>next>next; free(nextnode); nextnode = NULL; }
11. Search
 Find a node with a value equal to x one by one, find and return the node, otherwise return NULL, and modify the pointer: cur = cur  > next;
SLTNode* SListFind(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* cur = *pphead; while (cur) { if (cur>data == x) { return cur; } else { cur = cur>next; } } return NULL; }
12. Destroy
 Release one node by one and modify the pointer: next = cur  > next; free(cur); cur = next;
void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur>next; free(cur); cur = next; } *pphead = NULL; }
13. Get the number of linked list nodes
 There is a node, size+1, modify pointer: cur = cur  > next;
size_t SListSize(SLTNode* phead) { size_t size = 0; SLTNode* cur = phead; while (cur) { size++; cur = cur>next; } return size; }
4. Precautions for single linked list
matters needing attention:
 Try not to operate with the head pointer. You can use type renaming to prevent the head pointer from being found and the linked list from being lost. It is very troublesome to not find the head pointer. Each operation involves the head node, such as head plug deletion, traversal, reversing the linked list, etc. the head pointer is required. The purpose of this is to enhance readability
 When traversing the linked list, check whether the tail of the linked list is empty
 When inserting and deleting a node, you need to find the node before the insertion point or deletion point
 When inserting nodes, you need to pay attention to malloc
 To delete a node, you need to use free to release the opened memory to prevent memory leakage (often forgotten)
5. Expand
Questions about insertion and deletion:
 Why not insert the node before the pos position: the single linked list is oneway. It is relatively easy to find the successor node of a node. On the contrary, it is more troublesome to choose to find the successor node of a node.
 Why not delete the node at the pos location: like the first question, deleting the node at the pos location also needs to find the precursor node at the pos location. It is troublesome to let the precursor node point to the next node at the pos location to delete the node at the pos location.
Solution: the following circular double linked list can solve this problem
6. Source code
 If you need the source code, click the following link to view it:
gitee: https://gitee.com/deng_yuniubi/datastructure.
GitHub: https://github.com/yuxuanniu6/DataStruct.