（5）iOS程序猿算法学习——链表

由于写了快两个月的 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");
}