如果用一个数组存储数据，数组在程序启动之前就必须定义完成int a[整数常数/常数表达式]。

用a存储数据就必须提前知道需要被存储的数据大小并保证a的空间足够。在实际项目中，需要多大的数组很难预计，只能把数组定义的很大，但如果存入的数据少就会造成空间严重的浪费。所以最好方式是有多少就分配多少，链式结构就能很好解决这个问题。

        链式结构既能表示先后关系，又能实时分配空间。不仅是分配，删除也会很方便的，只用改变和需要删除节点有关的指向就可以了，而数组需要后续数据往空处补。

        虽然链式结构在增删以及空间管理方面方便，但也有相应的局限，查找效率很低，需要从一个初始节点开始遍历直至找到待查节点；数组的优势也就是支持随机查找，通过下标可以直接访问该元素，时间复杂度是O(1)。

        了解完链式结构和数组的不同，还要知道他们的相同点。数组和链表都是线性结构，不能有分支也不能有很多根，还有：

        1.存在唯一一个被称为第一个元素的元素节点

        2.存在唯一一个被称为最后一个元素的元素节点

        3.除了第一个元素意外，剩余的每一个元素都有且仅有一个被称为它的前驱的节点

        4.除了最后一个元素以外，剩余的每一个元素都有且仅有一个被成为它的后继节点

        想存储一系列数据，我们就必须存储数据本身，并且要储存数据的逻辑先后关系。定义数组的时候并没有关心它的逻辑关系，但实际上它有一个隐藏的逻辑先后——下标。数组的逻辑先后是物理上的逻辑顺序，就比如int *p = a  p实际上就是a[0]，p+1就是a[1]，这种表达式能形成的原因就是数组地址是连续间隔差值相等的，也就是说每个存储单元是固定的，不可能单独创建一个存储单元插入，还有在删除某个存储单元数据时，只能删除数据然后把后续数据前移。

        

        链表的灵活度相较之下就很高了，首先是通过结构体进行数据存储，结构体包括存储的数据和指向后续节点的指针，从这就知道链表的先后顺序就只是逻辑上的，节点的地址是随机的。

     

typedef int MyDataType;

struct node
{
    MyDataType data;//数据域，类型任意
    struct node* next;//指针域，指向下一个节点，节点的类型和本结构体一样
    struct node* prev;//指针域，指向上一个节点，类型和本结构体一样
}；

这就是链表节点的定义，不过上面的结构体是双链表的类型，单链表取其中一个指针域就可以了。

一、接下来是对完整的无头结点单链表创建过程，以及输出和释放：

        1.先定义数据类型和定义结构体。

#ifndef __MYFORWARDLIST_H__
#define __MYFORWARDLIST_H__

#include <stdio.h>
#include <stdlib.h>

typedef int ForwadListDataType;

//节点数据类型
typedef struct ForwardListNode
{
    ForwadListDataType data;//数据域
    struct ForwardListNode* next;//指向下一个的指针，指针域
}ForwardListNode;

#endif

节点的类型就定义完了，为了方便理解，下面是图示
 

这里的p1,p2,p3都是ForwadListNode*类型。

        2.为了知道链表真的插入节点我们需要让它依次输出每个节点的data，我们需要一个遍历并输出data，在实际开发中不会有这种功能，这里只是为了测试。

#incldue "forwardlist.h"

void PrinyForwadList(ForwardListNode *first)
{
    ForwardListNode* ptr = first;
    while(ptr != NULL)
    {
        printf("%d ", ptr ->data);
        ptr = ptr ->next;
    }
    printf("\n");
}

        3.先通过CreateForwardListNode(const ForwardListDataType data)创建一个节点，并存储data，再通过ForwardList_push_front_node(ForwadListNode* first, ForwardListNode* ptr)把节点插入到链表的开头。

#inclde "fowardlist.h"

//通过数据创建节点功能
//static修饰全局，仅在本文件使用
static ForwardListNode* CreateForwardListNode(const ForwardListDataType data)
{
    ForwardListNode* ptr = (ForwardListNode*)calloc(1, sizeof(ForwardListNode));//申请空间，并初始化
    ptr ->data = data;
    return ptr;
}

//将节点ptr添加到first代表的链表前面，头插
//仅在本文件使用
static ForwardListNode* ForwardList_push_front_node(ForwardListNode* first, ForwardListNode* ptr)
{
    if(first == NULL)//如果链表不存在，ptr就是第一个节点
        return ptr;
    //链表存在，ptr插在第一个
    ptr ->next = first;
    return ptr;
}

        4.先在main.c进行编程测试，依次输出链表每个节点的数据。

#include "forwardlist.h"

int main()
{
    ForwardListNode* first = NULL;
    while(1)
    {
        int a;
        scanf("%d", &a);
        if(a <= 0)
        {
            break;
        }
        first = ForwardList_push_front(first, a);
    }
    PrintForwardList(first);
}

        5.对于用malloc和calloc这种要手动申请的空间，使用完之后也需要手动释放空间。

#include "forwardlist.h"

static ForwardListNode* ForwardList_deleteAll_node(ForwardListNode* first)
{
    if(first == NULL)
        return NULL;
    ForwardListNode* ptr = (ForwardListNode*)calloc(0, size(ForwardListNode));
    if(first ->next == NULL)
    {
        printf("free %d\n", first ->data);
        free(first);
        return first;
    }
    while(first != NULL)
    {
        ptr = first;
        first = first ->next;
        ptr ->next = NULL;
        printf("free %d\n", ptr ->data);
        free(ptr);
    }
    free(first);
    return first;
}

好了，接下来只需要在main.c里调用ForwardListNode*  ForwardList_deleteAll_node(ForwardListNode* first)就可以了

#include "forwardlist.h"

int main()
{
    //链表的输入..........
    
    ForwardList_deleteAll(first);
    return 0;
}

这样基础的无头结点单链表的基础功能就完成了。