C语言实现单向链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

所谓单链表，是指数据接点是单向排列的。一个单链表结点，其结构类型分为两部分： 1、数据域：用来存储本身数据 2、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。

代码实现如下：

注意：

以下代码的实现包含了链表的头指针，而链表本身并没有首部节点，也就是头指针直接指向了第一个真正有数据的节点。如下图所示：

所谓头指针，就是指向第一个节点指针的指针，如果第一个节点是ListNode* list，那么实际应用中可以用&list的方式来标识头指针，说起来有点绕，看代码：

1.头文件 list.h

#include <stdio.h>  
#include <assert.h>  
#include <windows.h>  
#include <malloc.h>  

//定义数据类型，假设为int
typedef int DataType;  
//定义自引用结构体（结点）
typedef struct ListNode  
{  
    DataType data;  
    struct ListNode* next;  
}ListNode;  

ListNode* CreatNode(DataType x);//创建一个节点  
void PrintList(ListNode* plist);//遍历并打印链表  
void InsertNodeTail(ListNode** head,DataType x);//在链表最后的位置插入一个节点  
void DeleteNodeTail(ListNode** head);//删除链表最后一个节点  
void InsertNodeHead(ListNode** head,DataType x);//在链表最前面插入一个节点 
void DeleteNodeHead(ListNode** head);//删除链表最前面的一个节点  
ListNode* FindNode(ListNode* plist,DataType x);//查找一个节点  
void InsertNodePos(ListNode** head,ListNode* pos,DataType x);//在pos的前面插入一个节点  
void DeleteNodePos(ListNode** head,ListNode* pos);//删除指定的pos节点

2.函数实现 list.c

#include "list.h"

/**
 * 创建一个节点，注意不是创建链表
 * @DataType x 节点的数据
 * @return ListNode 返回该节点的指针
 */
ListNode* CreatNode(DataType x)//创建一个节点
{
    ListNode* Node = (ListNode *)malloc(sizeof(ListNode)) ;
    Node->data = x ;
    Node->next = NULL ;
    return Node;
}
/**
 * 遍历链表并打印输出数据
 * @ListNode *plist 需要遍历的链表的表头节点（第一个节点），注意不是头指针
 */
void PrintList(ListNode* plist)
{
    ListNode* cur = plist ;
    while(cur)
    {
        printf("%d->",cur->data);
        cur = cur->next ;
    }
    printf("NULL\n");
}
/**
 * 在链表最后的位置插入一个节点（尾插）
 * @ListNode ** head 需要遍历的链表的头指针，头指针指向了第一个节点
 * @DataType x 要插入的该节点的数据
 */
void InsertNodeTail(ListNode** head,DataType x)
{
    // 1 2 3 4
    //1.链表为空
    //2.一个
    //3.多个
    if(*head == NULL)
    {
        *head = CreatNode(x) ;
    }
    else if((*head)->next == NULL)
    {
        (*head)->next = CreatNode(x);
    }
    else
    {
        ListNode* cur = *head ;
        while( cur->next )
        {
            cur = cur->next ;
        }
        cur->next = CreatNode(x);
    }
}
/**
 * 删除链表最后一个节点
 * @ListNode ** head 需要遍历的链表的头指针
 */
void DeleteNodeTail(ListNode** head)
{
    //1.空链表
    //2.一个节点
    //3.多个节点
    if(*head == NULL)
    {
        return;
    }
    else if((*head)->next == NULL)
    {
        free(*head);
        *head = NULL;
    }
    else
    {
        ListNode* cur = *head;
        ListNode* pos = *head;
        while(cur->next)
        {
            pos = cur;
            cur = cur->next ;
        }
        free(cur);
        cur = NULL;
        pos->next = NULL;
    }
}
/**
 * 在链表最前面的位置插入一个节点（头插）
 * @ListNode ** head 需要遍历的链表的头指针
 * @DataType x 要插入的该节点的数据
 */
void InsertNodeHead(ListNode** head,DataType x)
{/*
    1.空链表
    2.非空*/
    if(*head == NULL)
    {
        *head = CreatNode(x);
    }
    else
    {
        ListNode* tmp = CreatNode(x);
        tmp->next = *head;
        *head = tmp;
    }
}
/**
 * 删除链表最前面一个节点
 * @ListNode ** head 需要遍历的链表的头指针
 */
void DeleteNodeHead(ListNode** head)
{
    /*1.空链表
    2.一个节点
    3.多个节点*/
    if(*head == NULL)
    {
        return;
    }
    else if((*head)->next == NULL )
    {
        DeleteNodeTail(head);
    }
    else
    {
        ListNode* next = (*head)->next ;
        free(*head);
        *head = next;
    }
}
/**
 * 查找一个数据为x的节点
 * @ListNode * plist 需要遍历的链表的第一个节点
 * @DataType x 要查找的该节点的数据
 * @return ListNode* 返回该节点的指针
 */
ListNode* FindNode(ListNode* plist,DataType x)//查找一个节点0 1 2 3 4 
{
    while(plist)
    {
        if(plist->data == x)
        {
            return plist;
        }
        plist = plist->next ;
    }
    return NULL;
}
                                                                         /**
 * 在pos节点的前面插入一个节点
 * @ListNode ** head 需要遍历的链表的头指针
 * ListNode* 某一个已存在的节点
 * @DataType x 要查找的该节点的数据
 */
void InsertNodePos(ListNode** head,ListNode* pos,DataType x)
{
    assert(head&&pos);
    /*1.如果pos是头结点，则是头插
    2.pos是其他节点*/
    if(pos == *head)
    {
        InsertNodeHead(head,x);
    }
    else
    {
        ListNode* tmp = NULL;
        ListNode* prev = *head;
        while(prev->next != pos)
        {
            prev = prev->next ;
        }
        tmp = CreatNode(x);
        prev->next = tmp;
        tmp->next = pos;
    }
}
/**
 * 删除某一个pos节点
 * @ListNode ** head 需要遍历的链表的头指针
 * ListNode* 某一个已存在的节点
 */
void DeleteNodePos(ListNode** head,ListNode* pos)//删除pos节点 
{
    assert(head&&pos);
    /*1.头删
    2.尾删
    3.中间删1 2 3 4  删除3*/
    if(pos == *head)
    {
        DeleteNodeHead(head);
    }
    else if(pos->next == NULL)
    {
        DeleteNodeTail(head);
    }
    else
    {
        ListNode* prev = *head ;
        while(prev->next != pos)
        {
            prev = prev->next ;
        }
        prev->next = pos->next ;
        free(pos);
        pos = NULL;
    }

}

3.测试函数 test.c

#include "list.h"

void test1()
{
    //声明链表的第一个节点，指向NULL，相当于创建了一个空链表
    ListNode* list = NULL;
//测试尾插
    InsertNodeTail(&list,0);
    InsertNodeTail(&list,1);
    InsertNodeTail(&list,2);
    InsertNodeTail(&list,3);
    InsertNodeTail(&list,4);
    PrintList(list);

//测试尾删
    DeleteNodeTail(&list);
    PrintList(list);
    DeleteNodeTail(&list);
    DeleteNodeTail(&list);
    DeleteNodeTail(&list);
    DeleteNodeTail(&list);
    DeleteNodeTail(&list);
    PrintList(list);
}

void test2()
{
    //声明链表的第一个节点，指向NULL，相当于创建了一个空链表
    ListNode* list = NULL;
//测试头插
    InsertNodeHead(&list,1);
    InsertNodeHead(&list,2);
    InsertNodeHead(&list,4);
    PrintList(list);
//测试头删
    DeleteNodeHead(&list);
    PrintList(list);     
    DeleteNodeHead(&list);
    DeleteNodeHead(&list);
    DeleteNodeHead(&list);
    DeleteNodeHead(&list);
    DeleteNodeHead(&list);     
    PrintList(list);
}

void test3()
{
    //声明链表的第一个节点，指向NULL，相当于创建了一个空链表
    ListNode* list = NULL;
    //声明链表的某个位置节点
    ListNode* pos;
    InsertNodeHead(&list,0);
    InsertNodeHead(&list,1);
    InsertNodeHead(&list,2);
    InsertNodeHead(&list,4);
    PrintList(list);
//测试查找函数
    pos = FindNode(list,2);
//测试在pos位置前面插入x
    Insert(&list,pos,3);
    PrintList(list);
//测试删除pos位置的节点
    pos = FindNode(list,4);
    DeleteNodePos(&list,pos);
    PrintList(list);//头删

    pos = FindNode(list,0);
    DeleteNodePos(&list,pos);
    PrintList(list);//尾删

    pos = FindNode(list,2);
    DeleteNodePos(&list,pos);
    PrintList(list);//中间删除
}

int main()
{
    test3();
    return 0;
}