链表

链表是C语言中一个基本的数据结构，但是对于一些C语言初学者来说，会被一些外界说法干扰，导致内心对链表有一些恐惧，甚至产生了畏难心理。

实际上来说，编程世界的概念是从现实世界中抽象而来，换而言之，对于链表来说，也有对应的一种现实世界中的场景与之对应。那我们不妨从现实世界中的场景来理解链表。

我们举个例子，假设一群学生在操作排队，后一个学生牵着前一个学生的衣服，假设前一个学生只知道后一个学生的信息，这就是单项链表，前一个学生即知道他的前一个学生的信息和他后一个学生的信息，那么这就是双向链表。除了有学生这个元素来描述学生自身的信息外，还应该有一个元素来描述这个队伍的信息，那么用于描述学生信息的称为子节点，描述队伍信息的称为根节点。

单项链表

链表的操作通常有初始化链表，增删，排序。

初始化链表：初始化根节点。描述队伍相关信息，比如说描述这个队伍的名字，队伍的班级之类的。

1void InitList(struct list* list)
2{
3    list->name = "abc";
4    list->next = NULL;
5}

增：链表中增加节点。在队伍中新增学生，可以分为在末端增加或者在指定位置增加。

在末端中断的逻辑是：先找到尾节点，将尾节点的next更新为新学生（新节点）。需要考虑根节点中的next没有数据的情况。

 1在链表尾部插入新学生
 2逻辑：遍历找到尾节点，尾节点的next=null，将尾节点的next更新尾新学生（新节点）。需要考虑链表中没有节点的情况。
 3void addPerson(struct list* list, struct person* new_person)
 4{
 5    assert(list != null, "the list is null");
 6    /* 如果list中没有节点 */
 7    if(list->next == null){
 8        list->next = new_person；
 9        return;
10    }
11    struct person* last_person = list->next;
12    /* 查找尾节点 */
13    while(last_person->next != null){
14        last_person = last_person->next；
15    }
16    /* 赋值 */
17    last_person->next = new_person;
18}

删：链表中删除节点。在队伍中删除学生。

 1逻辑：先找到将要删除学生的前一个节点
 2pre_node:  要删除学生的前一个学生
 3node: 要删除的学生
 4next_node: 要删除学生的后一个学生。
 5pre_node->next = node->next;
 6这样就完成了pre_node的后一个学生是next_node。
 7需要注意要删除的节点是第一个节点的情况。
 8void delPerson(struct list* list, struct person* new_person)
 9{
10    assert(list != null, "the list is null");
11    assert(list->next != null, "the list have no member");
12    struct person* pre_person = list->next;
13    while(pre_person != new_person || pre_person ->next != new_person)
14            pre_person = pre_person ->next;
15}
16pre_person->next = new_person->next;

上面的是链表的常规操作，但是在实际应用上，这种用法太死板，限制节点的类型，毫无通用性可言。

那么我们需要更加具有通用性一点的链表，这样能统一初始化，增删，排序等链表函数。

通用链表

我们把这种链表形式称之为通用链表，使用统一的函数对链表进行操作。

现在先定义一个struct node_t 的节点链表，具体实现为下

1struct node_t {
2    struct node_t *next;
3};

那么可以把节点链表套娃进用户节点中，比如

1struct person{
2    char* name;
3    int age;
4    struct node_t next;
5}

或者

1struct dog{
2    char* name;
3    int age;
4    struct node_t node;
5}

根节点同理

1struct link{
2    char* name;
3    char *class;
4    struct node_t head;
5}

那么链表连接结构如下

这样似乎已经构造了一个类型为struct node_t的链表，我们可以对该链表进行初始化，增删，排序等操作。

我们可以轻而易举的获取到每个节点的信息，但实际上我们对node_t 毫无兴趣，真正需要的是用户节点中的有效信息，那么需要通过结构体中的node_t反推用户结构体的地址。

这里需要引入容器概念。回到上面举的例子，person里含有node，person就是node的”容器”或者说”container”。

dog里含有node，dog就是node的”容器”或者说”container”。

核心在于怎么根据node找到container。已知next的地址，需要获取struct person的地址，那么我们只需要node-offset。offset就是age和name的大小，虽然我们知道为8，但是需要一个通用的办法进行计算。

现在我们假设person的地址为0，(struct person *(0)→next)就是已知的偏移量。

1struct person p1 = (struct person*)(char *)next - (unsigned int)&((struct peroson *)0→node)
2

可以通过测试程序来验证

     1#include <stdio.h>
 2
 3struct node_t {
 4    struct node_t *next;
 5};
 6
 7struct person{
 8    int a;
 9    int age;
10    struct node_t node;
11};
12
13int main()
14{
15   /*  Write C code in this online editor and run it. */
16   printf("Hello, World! n");
17   struct person p1 = {0};
18
19   printf("node addr %p n", &(p1.node));
20   printf("person addr %p n", &p1);
21   printf("offset addr %d n", &((struct person *)0)->node);
22   return 0;
23}
24
25---------输出结果----------------------
26Hello, World! 
27node addr 0x7fffed4573a8 
28person addr 0x7fffed4573a0 
29offset addr 8

双向链表

双向链表，顾名思义就是在节点中可以指向前一个节点，那么结构体就为

1struct node_t {
2    struct node_t *next;
3    struct node_t *pre;
4};

整个链表的形状为

根节点的pre指向最后一个节点，最后一个节点的next指向根节点，这样首尾相连，形成一个双向环形链表。

在尾部添加一个新节点

11、通过根节点的pre,找到node2尾节点
2
32、在last后面新增一个节点
4    new_node->next = node2->next
5    node2->next = new_node
6    new_node->pre = node2
7    root_node->pre = new_node

在链表中删除某一项

11、根据要删除的节点，找到其前后的节点
2struct node* left_node = delete_node->pre; // 实际就是节点1
3struct node* right_node = delete_node->next; // 实际就是节点3
4
52、删除该节点
6left_node->next = delete->next;
7right->pre = delete->pre;

在指定节点后面加入新节点

 11、根据指定节点(cur_node)的位置找到其左右的节点
 2struct node_t* left_node = cur_node->pre; // cur_node为节点2，left_node为节点1
 3struct node_t* right_node = right_node->pre; // cur_node为节点2，right_node为节点3
 4
 52、插入新节点
 6
 7cur_node->next = new_node;
 8new_node->pre = cure_node;
 9new_node->next = right_node;
10right_node->pre = new_node