linux C 数据结构之单链表

基础学习，只有一种数据类型的单链表

对链表的理解：

一种链式存储结构，通过指针指向下一个要存储的数据的地址，在内存中不要求链表中各个数据内存连续，与数组不同，链表由节点组成，通过指针链接。

对链表概念的理解：

头指针：头指针指向链表的第一个节点

头节点：头节点在定义头指针时产生

struct node{
    int data;
    struct node *pNext;
};
           

链表类型定义

data为链表该节点存储的数据

pNext指向下一个节点

对链表的操作包括：创建节点、在链头插入节点、在链尾插入节点、删除节点、遍历链表。

创建节点步骤：

1、申请一个节点大小的内存空间

2、检查空间是否申请成功

3、清理申请到的内存空间

4、填充该节点的数据

5、将节点中的指针初始化为NULL

struct node * creat_node(int data){
    struct node * p = (struct node *)malloc(sizeof(struct node));
    if(NULL == p){
        printf("malloc error !\n");
        return NULL;
    }
    bzero(p,sizeof(struct node));
    p->data = data;
    p->pNext= NULL;
    return p;
}
           

在链头插入节点步骤：

1、新节点指向原来的第一节点

2、头节点的指针指向新的节点

void insert_head(struct node*pH,struct node*new){
    new->pNext = pH->pNext;
    pH->pNext = new;
}
           

在链尾插入节点步骤：

1、找到链位节点（该节点的指针为NULL）

2、将链位节点指针指向新节点

void insert_tail(struct node*pH,struct node*new){
    struct node*p = pH;
    while(NULL != p->pNext){
        p = p->pNext;
    }
    p->pNext = new;
}
           

删除节点：

引用块内容

遍历链表步骤：

1、由头节点开始遍历并判断当前节点是否为尾节点

2、不是尾节点则取出数据并移动到下一个节点

3、是尾节点，取出数据并停止遍历

void list_foreach(struct node*pH){
    struct node *p = pH;
    printf("start____________________\n");
    while(NULL != p->pNext){
        p = p->pNext;
        printf("data = %d\n",p->data);
    }
    printf("data = %d\n",p->data);
    printf("end____________________\n");
}