链表相比于顺序表，优点事他能比较方便地插入和删除元素。但是链表不能随机存取。

定义一个单向链表

链表里的node相比于顺序表的的区别是，链表的会多一个domain来放指向下一个node的pointer。

struct linkedNode {
    int         value;
    linkedNode* next;
} 
typedef struct linkedNode  linkedNode;
typedef struct linkedNode* linkedList;

偷懒点可以写成

typedef struct linkedNode {
    int         value;
    linkedNode* next;
} linkedNode, * linkedList;

其中，
第5行的意思是，把这个结构体直接rename成linkedNode，这样就不用在后续代码里写一大坨有的没的。
第6行的linkedList是一个指向struct linkedNode的pointer。

因为一个链表是由各个node是通过next这个pointer来link在一起的，换句话说，只要有第一个node的pointer就能找到一整个表。
所以在表示一个单链表的时候，只要declare一个pointer指向这个单链表的第一个node就可以了。

综上所述，要declare一个新的单链表，只需要

linkedList  list;
// 或
linkedNode* list;
/* 两种写法二选一即可，在电脑看来，两个写法都是一样的。
 * 只不过在人的角度来看，前者强调的是一整个表，
 * 后者强调的是单单一个node。
 * 合适的地方用合适的名字，代码可读性up
*/ 

就可以了。

一些操作.h

因为书上经常malloc()导致我看得头昏眼花，所以我把他封装成一个function.

linkedNode* newNode() {
    return (linkedNode*) malloc(sizeof(linkedNode));
    //     ~~~~~~~~~~~~~  记得typecasting，不然翻车
}

还有这个，在某个node后面插入一个新node

bool insertAfter(linkedNode* p, int value) {
    if (p == NULL) { // 如果i的位置比整个表还要大
        return false;
    }
    else {
        linkedNode* newNode = newNode();
        newNode->value  = value;
        newNode->next   = p->next;
        p->next         = newNode;
        return true;
    }
}

---

不带头节点的单链表

初始化

初始化的方法，这时候表里面还没有东西

bool initList(linkedList &list) {
//                       ~~~~~ 注1
    list = NULL;
    return true;
}

要特意让这个list的地址里的数据变成NULL的原因是为了防止这块地址有用剩下的脏数据——换句话说就是为了防止上一个人拉完屎不冲厕所，我们不管怎么样，开始方便之前都先给他冲一下。

注1：注意传参的时候一定要是引用那个表，就是前面加个&。如果没有&的话，接下来的都是对这个list的复制品进行操作。

然后再需要创建一个新表的地方，比如说在main()里，就

linkedList list;
// 注意，linkedList实际上是一个pointer
initList(list);

判断这个单向链表是不是空的

只要看看这个头指针是不是null

bool isEmpty(linkedList list) {
    if (list == NULL) {
        return true;
    }
    else {
        return false;
    }
}

在第i个之后插入

没有头节点，要先判断它要插入的位置是不是第一个，然后分不同情况来处理。
这个写起来比较阴间。

bool insert(linkedList &list, int i, int value) {
    if (i <  1) {
        return false;
    }
    if (i == 1) {
        linkedNode* newNode = newNode();
        newNode->value  = value;
        newNode->next   = list;
        list            = newNode;
        // 把你鲨叻，我替你活下去
        return true;
    }
    else {
        linkedNode* p   = list;
        int count       = 1;
        while (p!=NULL && count < i-1) {
            p = p->next;
            count = count +1;
        }
        return insertAfter(p, value);
    }
}

---

带头节点的单链表

初始化

头节点自身不存储数据，他只是为了让一些操作变得方便一点点。
有头节点的不能让电脑自动分配，要手动malloc()

bool initList(linkedList &list) {
    list = newNode();
    list->next = NULL;
    // 空表，头节点没有后继节点
    return true;
}

然后它创建新表和上面一样。

linkedList list;
initList(list);

判断是不是空的表

上面说过它的特性，只要判断头节点的后继节点指针是不是null

bool isEmpty(linkedList list) {
    if (list->next == NULL) {
        return true;
    }
    else {
        return false;
    }
}

在第i个之后插入

比如说我现在想在第i个位置插入一个node。

bool insert(linkedList &list, int i, int value) {
    if (i < 1) {
        return false; // 插入位置不对，直接让它爬
    }
    linkedNode* current;  // 表示当前扫描到的node
    int count = 0;  // 表示p现在是第几个node
    current = L;          // 让p指向头节点
    while (current != NULL && count < i-1) { //一直扫到第i-1个node
        current = current->next;
        count = count +1;
    }
    return insertAfter(current, value);
}

最坏的时间复杂度是 O(n)。

删除第i个

扫描、unlink、free().
这种要传表头指针进来的。

bool delete(linkedList &list, int i) {
    if (i < 1) { //不解释了
        return false;
    }
    linkedNode* current = list;
    int count = 0;
    while (current != NULL && count < i-1) { //扫描
        current = current->next;
        count = count +1;
    }
    if (current == NULL OR current->next == NULL) {
        return false;
    }

    linkedList* toBeDelete = current->next;
    current->next = toBeDelete->next; // unlink
    free(toBeDelete); // free()

    return true;
    }
}

最差时间复杂度 O(n)

删除指定一个node，不给表头指针

穿上他的衣服，让他替你去死，你变成他活下去。

bool delete(linkedList* node) {
    // 你不能杀死一个死人
    if (node == NULL) {
        return false;
    }
    node->value = node->next->value;
    node->next  = node->next->next;
    return true;
}

…算了就这样吧，这块内存这样一搞是个事故物件那我就不要了 :-)

---

在指定某个node之前插入数据

如果它给了表头给你，就可以从0开始重新扫一遍来搞。如果没有给，就要狸猫换太子。

bool insertBefore(linkedNode* current, int value) {
    if (current == NULL) {
        return false;
    }
    else {
        linkedNode* newNode = newNode();
        newNode->next  = current->next;
        current->next  = newNode;
        newNode->value = current->value;
        current->value = value;
    }
}

按位序查找

其实上面已经有一些实现了按照位序查找了
以下方法实现了输入一个链表表头就返回第i个node

linkedNode* getElement(linkedList list, int i) {
    if (i < 0) {
        return NULL;
    }
    else {
        linkedNode* current = list;
        int count = 0;
        while (current != NULL AND count < i) {
            current = current->next;
            count = count +1;
        }
        return current;
    }
}

按值查找

linkedNode* locateElement(linkedList list, int value) {
    linkedNode* current = list->next;
    while(current != NULL AND current->value != value) {
        current = current->next;
    }
    return current;
}

求表的长度

int length(linkedList list) {
    int length = 0;
    linkedNode* current = list;
    while(current->next != NULL) {
        current = current->next;
        length = length +1;
    }
    return length;
}

---

2021年5月27号更新：
感谢猪肝大佬指出了两处英文单词拼写错误，现在已经更正
下次一定会注意 >///<