C++11 数据结构2 线性表的链式存储，实现，测试

线性表的链式存储 --单链表

前面我们写的线性表的顺序存储(动态数组)的案例，最大的缺点是插入和删除时需要移动大量元素，这显然需要耗费时间，能不能想办法解决呢？链表。

链表为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。

线性表的链式存储结构中，每个节点中只包含一个指针域，这样的链表叫单链表。

一单链表中任意一个节点的数据模型

通过一组任意的存储单元来存储线性表中的数据元素。每给元素存放元素自身的信息外，还需要存放一个指向其后继的指针，其中data为数据域，存放数据元素；next为指针域，存放后继指针，next的后继指针中的内容也是和当前节点一样的数据模型

LNode

typedef struct LNode{    //定义单链表结点类型
    int data;            //数据域
    struct LNode *next;  //指针域
}LNode;

其中 int data; 是数据域，当然这里只是用int 类型进行演示。实际代码中可以有很多的类型。链表的示意图如下

传统链表问题的提出

当我们的数据域变化的时候怎么弄呢？

现在数据域只有一个 int data，当我们还要添加 string name ， char * othername的时候，怎么办？

也就是说：我们的数据域是千变万化的，因此传统链表不适用。

Linux内核链式链表

因此 Linux 的内核大神，想到了一个方法

让数据域和指针域分离，让业务域包含一个链式节点，，这个节点也只有一个指向同样的链式节点。

让数据域包裹指针域

typedef struct LNode{    //定义单链表结点类型
    struct LNode *next;  //指针域
}LNode;

typedef struct Teacher{
    int age;
    string name;
    char *othername;
    LNode pnext;
}

企业级链式链表

上述Linux 链式链表的每次都要求 pnext 对于整个struct 的偏移，

于是企业在开发过程中，就改了一版，让链表节点在业务节点的最开始

typedef struct LNode{    //定义单链表结点类型
    struct LNode *next;  //指针域
}LNode;

typedef struct Teacher{
    LNode pnext;
    int age;
    string name;
    char *othername;
}