由于写了快两个月的 C艹 代码，天天都是指针内存打交道，觉得有必要自己来实现下基础的数据结构了，个人感觉主要理解以下几点：
- 指针指向谁就把谁的地址赋给指针；
- 画图配合辅助指针理解；
- 辅助指针的移动；
- 基础概念：头结点（pHead）、前驱结点（pPrevious）、后继结点（pNext）、当前结点（pCurrent）；
链表的优点除了「插入删除不需要移动其他元素」之外，还在于它是一个局部化结构。就是说当你拿到链表的一个 node 之后，不需要太多其它数据，就可以完成插入，删除的操作。而其它的数据结构不行。比如说 array，你只拿到一个 item 是断不敢做插入删除的。
01-创建链表和辅助指针变量关系图.png
typedef struct Node {
int data;
struct Node *next;
}SList;
void SList_Create(SList **pHead) {
SList *pList = NULL, *pCurrent = NULL;
// 1.create Head
pList = (SList *)malloc(sizeof(SList));
pList->data = 0;
pList->next = NULL;
// add pointer to current
pCurrent = pList;
int input = 0;
printf("Enter -1 quit!\n");
scanf("%d", &input);
while (input != -1) {// 循环创建
// 2.alloc new node
SList *pMalloc = (SList *)malloc(sizeof(SList));
pMalloc->data = input;
pMalloc->next = NULL;
pCurrent->next = pMalloc;
// 3.move current
pCurrent = pMalloc;
printf("create node success!\n");
scanf("%d", &input);
}
*pHead = pList;
}
这里用二级指针的原因是，不想将链表 return 出来，就通过参数传递，如果一级指针的话，就错了，因为存在值拷贝，所以就用二级指针（用 n 级指针来修改 n-1 级指针的值）返回值可以用来处理异常，这里没写，抱歉有代码洁癖，哈哈。始终觉得 if else 的代码太 dirty
02-删除操作和赋值指针变量逻辑关系图.png
void SList_Destory(SList* pHead) {
SList *pCurrent = NULL, *pNext = NULL;
pCurrent = pHead;
while (pCurrent) {
pNext = pCurrent->next;
free(pCurrent);
printf("free data !\n");
pCurrent = pNext;
}
}
03-插入操作和辅助指针变量 逻辑关系图.png
/// inset a node's value is y after node value = 5 before
void SList_Insert(SList *pHead, int x, int y) {
SList *pPrevious = NULL, *pCurrent = NULL;
pPrevious = pHead;
pCurrent = pPrevious->next;
// 1.find dest
while (pCurrent) {
if (pCurrent->data == x) {
break;
}
pPrevious = pCurrent;
pCurrent = pPrevious->next;
}
// 2.malloc node
SList *pMalloc = (SList *)malloc(sizeof(SList));
pMalloc->data = y;
pMalloc->next = NULL;
// 3.insert list
pMalloc->next = pPrevious->next;//pCurrent
pPrevious->next = pMalloc;
}
04-删除操作 和 辅助指针变量 逻辑关系图.png
void SList_Delete(SList *pHead, int value) {
SList *pPrevious = NULL, *pCurrent = NULL;
pPrevious = pHead;
pCurrent = pPrevious->next;
// 1.find dest
while (pCurrent) {
if (pCurrent->data == value) {
break;
}
pPrevious = pCurrent;
pCurrent = pPrevious->next;
}
pPrevious->next = pCurrent->next;
free(pCurrent);
printf("delete a node success!\n");
}
