绝对好理解的双链表建立以及常用操作（插入，删除，翻转等）讲解_双链表插入

        一个月没有更新了。上次讲了单链表的基础操作并且还简单介绍了一下指针的概念。简单回顾一下，单链表的两个结构体，一个是node，我们类比为房屋，里面储存房屋的各种信息，例如人口等，另一个结构体是list，我们类比为街道，里面储存了街道上第一个房屋和最后一个房屋的位置，即头尾指针，而街道内的每一个房屋都有一个路牌，它指向下一个房屋的位置，这就是next指针。

        那么接下来就是双链表的讲解，双链表就是在单链表next指针的基础上增加了一个prev指针，作用就是用来指向上一个node，有了双链表，c语言的用法会灵活许多，在后续讲解图论时大家会有明显的感受。

        首先给出双链表的两个核心结构体：

typedef struct node {
    struct node *prev; //前指针
    struct node *next; //后指针
    char *data;
} Node;

typedef struct dll {
    Node *tail; //头指针
    Node *head; //尾指针
} Dll;

        从本质上来讲，单双链表的意义上相同的，所以如果单链表能理解，双链表就特别容易理解 了，我用一个手画草图来演示：

         这样就非常直观了是不是？

        那么废话不多说，我们直接开始讲解在使用双链表时常用的几大操作。注意，具体操作细节都在注释内。

基础部分：

1. 街道创建（list的创建）

Dll *DLL_create() {
    Dll *new_list = malloc(sizeof(Dll));
    new_list->head = new_list->tail = NULL; //一定要记得初始化
    return new_list;
} 

2.房屋创建（node的创建）

//如果要在链表内储存字符串类型的信息，就必须用复制的方法传入信息
char *copyString(char *value) { 
    char *data = malloc(sizeof(char) * (strlen(value) + 1));
    strcpy(data, value);
    return data;
}


Node *create_new_house(char *value) {
    Node *new_house = malloc(sizeof(Node));
    new_house->next = NULL;
    new_house->prev = NULL; //同样不要忘记这里的初始化（类似于单列表中设置每个新的房子单指针是NULL）
    //再次强调，因为data是字符串，不能用直接传入的方法，而应该用复制的方法传入数据，故才有了以下再次使用malloc的过程
    new_house->data = copyString(value); //复制字符串
    return new_house;
}

3.插入新的node至链表的头/尾/中间

        首先也是我先用手画图帮大家理解一下，然后我们再看代码。

        首先无论是插入到哪里，我们都要先通过刚刚写出来的create_new_house函数创建一个全新的初始化后的node，然后：

        这是插入到双链表末端的示意图：

        大体思路就是先用新的node的prev指针指向链表的tail，在用tail的next指针指向这个新的node，最后吧tail的位置挪到这个新的node的位置即可。

         插入到开头也是同理：

        先用新的node的next指针指向链表的head，在用head的prev指针指向这个新的node，最后吧head的位置挪到这个新的node的位置即可。 

        接下来是代码展示：

//末尾插入链表
Dll *DLL_append(Dll *list, char *value) {
    if (list != NULL) {
        //需要check链表的头、尾和中间
        if (list->head == NULL) { //这是指目前链表内还没有任何node
            Node *new_house = create_new_house(value);
            new_house->data[strlen(value)] = '\0'; //以防不同电脑的系统差异，应该在字符串最后强制加一个空字符串
            list->head = new_house; 
            list->tail = new_house;
        } else {
            Node *need_insert_house = create_new_house(value);
            //重点！！！
            need_insert_house->prev = list->tail;
            list->tail->next = need_insert_house;
            list->tail = need_insert_house;
        }
    }
    return list;
}


//开头插入链表
Dll *DLL_prepend(Dll *list, char *value) {
    if (list != NULL) {
        if (list->head == NULL) {
            list->head = list->tail = create_new_house(value);
        } else {
            Node *new_house = create_new_house(value);
            new_house->next = list->head;
            list->head->prev = new_house;
            list->head = new_house;
        }
    }
    return list;
}

//寻找到目标字符串后在其前面插入新的链表，如果找不到目标就插入到最开头（类似于插到中间，大家可以自行简化）
void DLL_insertBefore(Dll *list, char *target, char *value) {
    Node *target_list = is_exist(list, target); //这里是判断目标node是否存在，进阶部分会讲解这个函数
    if (target_list == NULL) {
        DLL_prepend(list, value); //未找到，插入到最后
    } else {
        Node *new_list = create_new_house(value);
        if (target_list == list->head) { //要额外考虑目标是头指针的情况
            list->head = new_list;
            new_list->prev = target_list->prev;
            target_list->prev = new_list;
            new_list->next = target_list;
        } else { //这里就是目标node在中间的情况了（理解不了就根据代码画图！！！）
            target_list->prev->next = new_list; //注意，这四个的顺序不能错！
            new_list->next = target_list;
            new_list->prev = target_list->prev;
            target_list->prev = new_list;
        }
    }
}

4.删除头/尾的node

        如果已经掌握了插入的方法，那么删除就特别好理解了。但是这里有一个特殊情况要注意，就是一定要多加一个判断来判断链表内是否只有一个node，如果只有一个node，在free掉这个node后一定一定一定要记得重新初始化链表的头尾指针为NULL，不然后续的程序会报错。

        上代码（我这里的程序是删除并且返回被删除的内容，大家可以根据需求自行修改）：

//显示最后元素并删除
char *DLL_shrink(Dll *list) {
    char *result = NULL;
    if (list != NULL && list->head != NULL) {
        //判断是否只有一个的方法是判断head是否等于tail
        if (list->head == list->tail) {
            Node *delete_house = list->tail;
            result = copyString(delete_house->data);
            list->head = list->tail = NULL;//千万记得加不然会变成野指针
            free(delete_house);
            return result;
        } else {
            Node *delete_house = list->tail;
            delete_house->prev->next = delete_house->next; //意思是把tail的上一位的next设置为NULL
            list->tail = delete_house->prev; //把tail往前挪一位
            result = delete_house->data;
            free(delete_house);
            return result;
        }
    } else {
        return NULL;
    }
}

//显示开头元素并删除
char *DLLshift(Dll *list) {
    char *result = NULL;
    if (list != NULL && list->head != NULL) {
        //判断是否只有一个的方法是判断head是否等于tail
        if (list->head == list->tail) {
            Node *delete_house = list->tail;
            result = copyString(delete_house->data);
            list->head = list->tail = NULL;//记得初始化不然会报错，而且很难排查！
            free(delete_house);
            return result;
        } else {
            Node *delete_house = list->head;
            delete_house->next->prev = delete_house->prev; //意思是把原第一位设置为NULL
            list->head = delete_house->next; //head往后挪一位
            result = delete_house->data;
            free(delete_house);
            return result;
        }
    } else {
        return NULL;
    }
}

进阶部分 ：

1.复制链表

        中心思想是创建一个新的list，然后找到被复制链表的头指针，在循环下不断调用末尾插入函数插入被复制链表的node内容，完成复制。

Dll *DLL_copy(Dll *list) {
    Dll *new_list = NULL;
    if (list != NULL) {
        new_list = DLL_create();
        Node *find_last = list->head;
        while (find_last != NULL) {
            DLL_append(new_list, find_last->data);
            find_last = find_last->next;
        }
    }
    return new_list;
}

2.翻转链表

        把链表内容整个翻转。在写的时候一定要注意分析node个数的奇偶。主要思路是tail指针不停指向下一个，prev不停指向上一个，在奇数个node时，head和tail会相遇；如果是偶数个那么head->next ==  tail 和 tail->prev == head这两种情况会相等，相遇就是函数的循环终止条件，在终止前不停交换头尾数据即可。

Dll *DLL_reverse(Dll *list) {
    if (list != NULL && list->head != NULL) {
        Node *head = list->head;
        Node *tail = list->tail;
        while (true) { 
            //针对奇数
            if (head == tail) {
                break;
            }
            char *exchange = head->data;
            head->data = tail->data;
            tail->data = exchange;
            //针对偶数
            if (head->next == tail) {
                break;
            }
            head = head->next;
            tail = tail->prev;
        }
    }
    return list;
}

3.判断链表是否有按顺序排列

        这里以字符串举例所以要用到strcmp函数。以下三个函数特别易懂，就不多做解释了。直接看代码吧。    

bool DLLisOrdered(Dll *list) {
    bool result = true;
    if (list != NULL && list->head != NULL) {
        Node *first_element = list->head;
        while (first_element != NULL && first_element->next != NULL) {
            if (strcmp(first_element->data, first_element->next->data) > 0{
                return false;
            }
            first_element = first_element->next;
        }
    }
    return result;
}

4.用于判断目标node是否存在

Node *is_exist(Dll *list, char *target) {
    Node *final_list = NULL;
    if (list != NULL && list->head != NULL) {
        Node *find_target = list->head;
        while (find_target != NULL) {
            if (strcmp(find_target->data, target) == 0) {
                final_list = find_target;
                break;
            }
            find_target = find_target->next;
        }
    }
    return final_list;
}

5.找到目标字符串后将其内容替换

void DLL_replace(Dll *list, char *target, char *value) {
    if (list != NULL && list->head != NULL) {
        Node *find_target = list->head;
        while (find_target != NULL) {
            if (strcmp(find_target->data, target) == 0) {
                find_target->data = copyString(value);
                break;
            }
            find_target = find_target->next;
        }
    }
}

高级部分：

        如果到这里都看懂了，其实链表也就掌握的差不多了，当然这只是C语言的，C++会更复杂大家可以查阅其他资料。

        剩下还有两个链表方法想和大家分享，其实也不是特别高级，只是略微比前面复杂一点点。

1.链表内容排序

        排序的各种方法相信大家都耳熟能详了，这里选用的是冒泡排序。

Dll *DLL_sort(Dll *list) {
    //这个是记录node数量的函数，太简单就不单独写了
    size_t length = DLL_length(list); 
    Node *pre_list = list->head; //使用快慢指针
    Node *cur_list = pre_list->next; 
    //以下为冒泡排序的算法内容，这个就不多做解释了
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - i - 1; j++) {
            if (strcmp(cur_list->data, pre_list->data) < 0) {
                char *exchange = pre_list->data;
                pre_list->data = cur_list->data;
                cur_list->data = exchange;
            }
            if (cur_list->next != NULL)
                cur_list = cur_list->next;
        }
        if (pre_list->next != NULL) { //这一步的目的是为了归位
            pre_list = pre_list->next;
            cur_list = pre_list->next;
        }
    }
    return list;
}

2.有序的不重复的插入链表内容

        这个是对之前的链表插入函数的改良，用这个函数时当你插入node时会一边插入一边自动排序。这个函数在图论中会用到。同时在图论里我还会补充插入子链表的知识点，有兴趣的可以关注一下我更新图论以及后续字符串匹配的知识点！

void list_append_by_order(list l, string item) {
        //这个contain就相当于之前的exist函数，用于避免重复的情况
    if (l != NULL && list_contains(l, item) == false){
        if (l->head == NULL) {
            l->head = l->tail = create_node(item);
            l->length++;
        } else if (strcmp(item, l->head->data) < 0) { //比第一个数小的情况
            list_push(l, item);
            l->length++;
        } else if (strcmp(item, l->tail->data) > 0) { //比最后一个数大的情况
            Node newNode = create_node(item);
            newNode->prev = l->tail;
            l->tail->next = newNode;
            l->tail = newNode;
            l->length++;
        } else { //在中间，但这里不考虑有重复元素
            Node temp = l->head;
            while (temp != NULL && temp->next != NULL) {
                if (strcmp(item, temp->data) > 0 && strcmp(item, temp->next->data) < 0) {
                    Node newNode = create_node(item);
                    newNode->next = temp->next;
                    newNode->prev = temp;
                    temp->next->prev = newNode;
                    temp->next = newNode;
                    l->length++;
                    break;
                }
            }
        }
    }
}

        谢谢浏览！编程小白会继续努力给大家分享的！！！