1. 什么是单链表
通过指针串联起来的内存空间，其内是结构体类型，包含存入数值与下一节点的地址，NULL是链表结束的标志（倘若结构体内存入的地址地址是NULL，则表示这是链表最后一个元素）
- 创造一个结构体类型
typedef struct SlistNode { SLTDATATYPE data; struct SlistNode* next; }SlistNode;//为使用方便起见,对结构体类型进行重命名 //我们要把SlistNode类型的结构体，以单链表的存储方式，存入内存空间
2.头插
通常情况（大多数人能想到的情况）链表内以及存在多个元素，我们要在第一个元素之前插入一个新元素
我们知道，链表是依靠指针串联起来的，但第一个指针是没有元素的指针可以指向的，所以我们创建一个
SlistNode* plist,让他指向第一个元素
在2元素前插入一个新元素1，我们需要让1的next指向2，plist指向1，因此代码如下
SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = *pphead;//pphead接收的是plist的地址 newnode->data = x; *pphead = newnode;
如果空间内没有元素呢？上述代码是否还适用？答案是否定的。因为空间内没有元素，插入的元素为第一个元素，所以该元素的next应该置为空，不指向任何空间。plist应该指向该元素。因而代码如下。
if (*pphead == NULL)//表示plist尚未指向任何空间，即链表为空 { SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = NULL; newnode->data = x; *pphead = newnode; }
上述两种情况能否串联起来呢？
当链表为空时，插入第一个元素，将data置为x，next置为NULL，plist指向这块空间
现在我们要插入第二个元素，让2的next存放1的地址，即将next置为plist的值，然后让plist指向2的空间
因此上述两种情况的代码是可以衔接的，最终代码如下
void PushFront(SlistNode** pphead,SLTDATATYPE x) { if (*pphead == NULL) { SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = NULL; newnode->data = x; *pphead = newnode; } else { SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = *pphead; newnode->data = x; *pphead = newnode; } }
需要注意的是，由于我们创造了一个函数来实现功能，要改变plist的值，必须通过传地址的方式。
SlistNode* plist=NULL; PushFront(plist,1) void PushFront(SlistNode* pphead,SLTDATATYPE x) { pphead=0x112233;//这并不能改变plist存储的值，因为pphead仅仅是plist内存储的值的一份临时拷贝 } SlistNode* plist=NULL; PushFront(&plist,1) void PushFront(SlistNode** pphead,SLTDATATYPE x) { *pphead=0x112233;//这可以改变plist的值，因为pphead接受的是plist的地址，pphead可以通过解引用改变值 //*pphead和plist是等价的 }
3. 尾插
假设空间内已有多个元素
尾插的第一步就是找尾，我们知道链表结束的标志是NULL。因此找到了NULL就找到了尾，其后我们要在尾后插入一个新元素，因此我们需要将原尾的next置为新元素的地址，新元素的next置为NULL，代码如下
SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = NULL; newnode->data = x; SlistNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode;
现在来考虑空间内没有元素的情况，因为空间内没有元素，因此插入的元素是第一个，我们需要把它的next置为NULL，使plist指向它，代码如下
if (*pphead == NULL) { SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = NULL; newnode->data = x; *pphead = newnode;
上述两种情况的代码也是能够相链接的，最终代码如下
void PushBack(SlistNode** pphead,SLTDATATYPE x) { if (*pphead == NULL) { SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = NULL; newnode->data = x; *pphead = newnode; } else { SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode)); if (newnode == NULL) { perror(""); return; } newnode->next = NULL; newnode->data = x; SlistNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode;
4. 头删
把第一个元素删除，让plist指向下一个元素。注意传地址修改
代码如下
void PopFront(SlistNode** pphead) { assert(*pphead);//没有元素是不能删的 { SlistNode* first = *pphead; *pphead = first->next; free(first); first == NULL; } }
5. 尾删
假设空间有多个元素存在
尾删先找尾，将尾的空间释放掉，再将尾前一个元素的next置为NULL
SlistNode* tail = *pphead; while (tail->next->next != NULL)//注意 { tail = tail->next; } free(tail->next); tail->next = NULL;
如果只剩下一个元素了，上述代码显然就不适用了，因为while (tail->next->next != NULL)至少需要2个元素才能判断
因此当只剩下一个元素时，代码如下
if (tail->next == NULL) { free(tail); tail == NULL; *pphead == NULL; }
完整的单链表头插头删尾插尾删链接
