数据结构：单链表的头插/尾插及头删/尾删操作

//结构体 struct node { int data;//要处理的数据是 int 类型的数据 struct node *pnext;//指向下一个节点 }

数据插入到链表：

1.头插法

step1.创建了一个新节点并且给值
step2.新节点指向原先首节点
p_new->pnext=phead->pnext
step3.将头节点指向新节点
phead->pnext=p_new;

#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
typedef struct node {
    data_t data;
    struct node *pnext;
}node_t;

node_t *create_linklist(void) {
    node_t *head = malloc(sizeof(node_t));//在堆上开空间不用传参不会自动销毁
    if(head == NULL) {
        printf("malloc fail");
        return NULL;
    }
    head->pnext = NULL;//头节点指针域为空
    return head;
}

void linklist_insert_head(node_t *phead, data_t data) //插入一个新的节点
{
    node_t *p_new = malloc(sizeof(node_t)); //创建新节点
    if(phead == NULL) //开空间可能失败
    {
        printf("malloc fail");
        return;
    }
    p_new->data = data; //传入数据
    p_new->pnext = NULL; //指针域给空（可写可不写）
    //连接链表
    p_new->pnext = phead->pnext; //插入，指向头节点所指的指针域
    phead->pnext = p_new; //头节点指向新节点
}

int is_empty(node_t *phead) //判断链表是否为空
{
    return phead->pnext == NULL;
}

int length(node_t *phead)
{
    if(is_empty(phead) == 1)
    {
        return 0;
    }
    int i = 0;
    node_t *p = phead->pnext;
    while(p!=NULL)
    {
        i++;
        p = p->pnext;
    }
    return i;
}

void linklist_print(node_t *phead) //打印链表
{
    if(is_empty(phead) == 1)
    {
        printf("empty linklist\n");
        return;
    }
    node_t *p = phead->pnext; //头节点之后的节点指针域
    while(p!=NULL)
    {
        printf("%d ",p->data); //打印数据域
        p = p->pnext; //指向链表下一个指针域
    }
    putchar('\n');
}

int main()
{
    node_t *phead = create_linklist();
    linklist_insert_head(phead,4);
    linklist_insert_head(phead,3);
    linklist_insert_head(phead,2);
    linklist_insert_head(phead,1);
    linklist_print(phead);
    int i = length(phead);
    printf("i = %d ",i);
    return 0;
}

查----遍历---打印

遍历打印逐个节点访问：

step1.指针遍历 p ； p->pnext != NULL //后面还有节点继续往后

2.尾插法

stepl.创建了一个新节点并且给值
p_new->pnext=NULL;
step2.找到尾节点 p 初始位置就从头节点开始判断 p 的指针域是否为 NULL
p->pnext != NULL
step3.链接
p->pnext=p_new

void linklist_insert_tail(node_t *phead, data_t data) {
    node_t *p_new = malloc(sizeof(node_t));
    if(p_new == NULL) //判断链表是不是空
    {
        printf("%smalloc fail\n", __func__);
        return;
    }
    p_new->data = data;
    p_new->pnext = NULL;//必须有
    node_t *p = phead;
    while(p->pnext != NULL)
    {
        p = p->pnext;
    }
    p->pnext = p_new; //连接
}

找值：从头遍历

node_t *linklist_find_key(node_t *phead, data_t key) {
    if(is_empty(phead) == 1)
    {
        return NULL;
    }
    node_t *p = phead->pnext;
    while(p != NULL)
    {
        if(p->data == key)
        {
            return p;
        }
        p = p->pnext;
    }
    return NULL;
}

3.删除：头删，尾删

头删

//判断链表是否为空
step1.有一个指针变量指向首节点 phead->pnext
step2.让头节点指向 p->pnext
step3.释放 p 所在的节点 free(p);

void linklist_delete_head(node_t *phead) {
    if(is_empty(phead) == 1)
    {
        return;
    }
    node_t *p = phead->pnext;
    phead->pnext = p->pnext;
    free(p);
}

尾删

//判断链表为空--空直接返回
s1.找到尾节点前一个节点
//统一操作逻辑 p 的初值得从 phead 开始
p->pnext->pnext == NULL
s2.释放尾节点 free(p->pnext)
s3.将前一个节点，设置为新的尾节点 p->pnext=NULL

void linklist_delete_tail(node_t *phead) {
    if(is_empty(phead) == 1)
    {
        printf("empty linklist\n");
        return;
    }
    node_t *p = phead;
    while(p->pnext->pnext != NULL)
    {
        p = p->pnext;
    }
    free(p->pnext);
    p->pnext = NULL;
}