动态链表的创建

一、内存的两种访问方式

1、随机访问方式

对于数组来说，他的所有元素在内存中是连续存储的，因而很容易计算出每个元素的内存地址，从而可以直接访问数组中的任意一个元素。

2、顺序访问方式

对于链表来说，不同的结点在内存中存储的位置是随机的，因而无法计算出每个结点的内存地址，从而只能从第一个结点开始依次访问。

因此，需要将第一个结点的地址保存起来。

二、如何保存第一个结点的地址？

1、带头结点的链表

若是将第一个结点的地址存储到一个专门的结点的指针域中，那么这种链表称为带头结点的链表。

这个专门的结点称为头结点，头结点的数据域中不存储任何有效数据。

这种链表也有头指针，不过此时的头指针变量中存储的是头节点的地址。

看起来头结点似乎多余，实际上引入头结点能够简化链表的创建、插入和删除等操作。

为何要创建一个函数

原因：需要返回头指针的地址，便于后面遍历、删除等操作

时刻谨记这张图！

因为指针p一直表示末指针，所以创建一个新指针，利用之后，此刻就变成了末指针