单链表头插法尾插法解析

在上次实验课之后，有同学问我头插法和尾插法到底是干什么的有什么用处，因为到饭点了，赶着吃饭 难以描述的原因，说晚点解释，一拖拖了几天。人的本质就是鸽子精，而我是老鸽子精

原代码传送

头插法

头插法就是从头插入(没问题啊) ：从头节点插入新节点，头节点的next不断更新指向插入元素地址，然后想要保存整条链就只要新元素等于头节点的next就行（保存了原来插入的元素）。（代码如下图）

在遍历的时候从最后插入的元素向第一个插入的元素访问，效果和栈类似，先进后出，可以用做链栈，在C++的stl库中封装的stack头文件效果和这个类似。

void GeateHeadList(List*& L, int a[], int n)
{
    List* p;
    for (int i = 0; i < n; i++) {
        p = (List*)malloc(sizeof(List));
        p->data = a[i];
        p->next = L->next;
        L->next = p;
    }
}

尾插法

尾插法就是从链的尾端插入元素，上一个元素的next指向新插入元素的地址，头节点始终指向第一个插入的元素，所以在遍历的时候也是从第一个插入的元素开始查询（一定要记得的在插入完最后一个元素后它的next一定要制空“NULL”），访问起来就像排队吃饭，先到先得，插队该打，可以用来写链队 。（代码如下图）

在C++的stl库中封装的queue头文件中queue类型（queue头文件中还有多种类型队列）效果和这个类似。

（pre始终指向L的最后一个元素的位置）

void GeateTailList(List*& L, int a[], int n)
{
    List *p, *pre = L;
    for (int i = 0; i < n; i++) {
        p = (List*)malloc(sizeof(List));
        p->data = a[i];
        pre->next = p;
        pre = p;
    }
    pre->next = NULL;
}