链表

链表的初始化

链表的最基础初始化，可以使用C语言的结构体。

typedef struct Node {
    int value;
    struct Node *next;
}node, *list_node;

也可以使用c++中对象的定义

class node {
public:
    int value;
    node *next;

    void function() {

    }
};

往后的示例以C语言为主。

链表节点的插入

尾插法

在末尾插入新节点，返回最后节点的指针
C语言

list_node insert_to_foot(list_node operation, int value) {
    if(!operation) {
        printf("List Error!\n");
        exit(-1);
    }
    list_node to_node;
    to_node->value = value;
    operation->next = to_node;
    return to_node;
}

头插法

在头部插入新节点，返回新的头节点
C语言

list_node insert_to_head(list_node operation, int value) {
    if(!operation) {
        printf("list Error!\n");
        exit(-1);
    }
    list_node to_node;
    to_node->value = value;
    to_node->next = operation;
    return to_node;
}

链表节点的删除

当不存在头部节点时，对节点的删除操作较为复杂。首先，我们需要找到头节点，然后开始向下遍历，搜索到需要的节点

• 若头节点就是待删除的节点，则头节点指针下移，删除头节点。
• 若尾节点就是待删除的节点，则删除尾节点，前一节点的next指针赋空值。
• 其余的一般情况下，找到待删除节点的前一节点，让其指向待删除节点的下一节点，再删除指定节点。

存在头部节点时，可以省略对第一种情况的讨论。

链表相关功能

求尺寸或搜索

求尺寸需要从头节点开始遍历，而遍历可以通过迭代或递归实现
迭代

int size(list_node head) {
    int i;
    for(i = 1; head != NULL; head = head->next, ++i);
    return i;
}

递归

int size(list_node head) {
    if(head->next == NULL)
        return 1;
    else
        return 1 + size(head->next);
}

当需要搜索时，需要再参加相关参数
迭代

bool is_find(list_node head, int target) {
    for(; head != NULL; head = head->next)
        if(head->value = target)
            return true;
    return false;
}

递归

bool is_find(list_node head, int target) {
    if(head->value == target)
        return true;
    if(head->next == NULL)
        return false;
    return is_find(head->next, target);
}