单向链表是数据结构中的一种，它由节点组成，每个节点包含两个部分：数据域和指针域。数据域用于存储节点的值，指针域则用于指向下一个节点。单向链表的特点是只能从头节点开始遍历到尾节点，不能反向遍历。

1 单向链表的节点定义

typedef struct node
{int data; //数据域 用来存放数据 整型struct node * next; //指针域 用来存放下一个节点的首地址
}link_node_t;

2.创建一个空的链表 

//1.创建一个空的链表(本质上只有一个头节点链表,将头节点的首地址返回)
link_node_t* createEmptyLinklist()
{//创建一个空的头节点link_node_t* p = malloc(sizeof(link_node_t));if(p == NULL){printf("createEmptyLinklist malloc failed!!\n");return NULL;//表达申请失败}//申请空间,就是为了装东西p->next = NULL;//指针域初始化为NULL,数据域不用初始化,因为头节点数据域无效//将头节点的首地址返回return p;
}

3.遍历有头链表的有效元素

void showLinklist(link_node_t* p)
{while(p->next != NULL){p = p->next;printf("%d ",p->data);}printf("\n");
}

4.求链表的长度  

int getLengthLinklist(link_node_t* p)
{int len = 0;//统计长度while(p->next != NULL){p = p->next;len++;//打印一次,就计数一次}return len;
}

5.判断链表是否为空,空返回1，未空返回0

//6. 判断链表是否为空 空返回1,未空返回0
int isEmptyLinklist(link_node_t* p)
{//p指向头节点//p->next代表头节点的指针域,头节点的指针域为空,说明后面什么没有了return p->next == NULL ? 1 : 0;
}

6.向链表的指定位置插入数据

int insertIntoLinklist(link_node_t* p, int post, int x)
{int i;//0.容错判断if(post < 1 || post > getLengthLinklist(p)+1){printf("insertIntoLinklist failed!!\n");return -1;}//1.创建一个新的节点,保存插入的数据xlink_node_t* pnew = malloc(sizeof(link_node_t));if(pnew == NULL){printf("pnew malloc failed!!\n");return -1;}//申请空间,就是为了装东西,立刻装东西pnew->data = x;pnew->next = NULL;//准备开始插入//2.将头指针指向(移动)插入位置的前一个位置for(i = 0; i < post-1; i++)p = p->next;//3.将新节点插入链表(先连后面,再连前面)pnew->next = p->next;//连后面p->next = pnew;//连前面return 0;
}

int deleteFromLinklist(link_node_t* p, int post)
{//0.容错判断if(post < 1 || post > getLengthLinklist(p) || isEmptyLinklist(p)){printf("deleteFromLinklist failed!!\n");return -1;}//1. 将头指针移动到删除位置的前一个位置int i;for(i = 0; i < post-1; i++)p = p->next;//2.定义了指针变量4个字节,指向被删除节点link_node_t* pdel = p->next;//3.跨过被删除节点p->next = pdel->next;//4. 释放被删除节点free(pdel)pdel = NULL;return 0;
}

void clearLinklist(link_node_t* p)
{//砍头思想:每次删除的是头节点的下一个节点while(p->next != NULL)//只要链表不为空,就执行删除操作 p->next == NULL循环结束,此时是空的表{//1. 将头指针移动到删除位置的前一个位置//第一步可以省略不写,因为每次删除的是头节点的下一个节点,//那么头节点就是每次被删除节点的前一个位置//2.定义了指针变量4个字节,指向被删除节点link_node_t* pdel = p->next;//3.跨过被删除节点p->next = pdel->next;//4. 释放被删除节点free(pdel);pdel = NULL;}
}

int searchDataLinklist(link_node_t* p, int x)
{int post = 0;while(p->next != NULL){p = p->next;post++;//用来记录第几个if(p->data == x)return post;//返回值是第几个}return -1;//不存在
}