单向不带头非循环链表

• 什么是链表
• 最简单链表的增删查改

什么是链表

链表： 通过指针将一系列离散的数据关联起来的数据整体叫链表

链表逻辑关系图示：

插入一点题外话： 这个链表就像楼房一样 数据就是每一层的房间，这个指针就像楼梯 这样一比喻 就能明白什么时候需要到楼顶，什么时候不需要到楼顶。

最简单链表的增删查改

1. 链表的创建
   链表的本质还是结构体，和线性表相比 线性表是连续的 因为 线性表是通过开辟一个连续的空间来存放的 链表的本质是通过指针将离散的结构体链在一起，所以叫链表。

typedef int SLTdataType;typedef struct SListNode{SLTdataType data;       // 使用typedef可以方便更改数据类型struct SListNode* next; // 存放指向下一个结构体的指针变量}SListNode;

这里的指针一定要注意 指针时结构体类型的 他是指向下一个结构体的。

1. 链表的打印
   先上代码

void SListprint(SListNode* ps){assert(ps);//如果是空没有打印的必要SListNode* cue = ps;while (cue !=NULL){printf("%d ", cue->data);}printf("\\n");}

原理解读

每进行一次

cue = cue->next;

cue指针就会获取下一个结构体的地址。

cue！=NULL与cue->next!=NULL的区别

cue不为空表示cue所指向的结构体不为空
cue->不为空表示cue->所指向的下一个结构体不为空
打印 需要遍历所有。所以使用cue！=NULL
这里需要爬完每一层楼 爬完每一层楼不就到楼顶了嘛。不就是cue->NULL嘛

1. 链表的结点申请

```cSListNode* BuySListNode(SLTDataType x){SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));// malloc开辟空间assert(newnode);//防止空指针出现newnode->data = x;newnode->next = NULL;// 不知道他将要插入哪里 所以置空return newnode;}

1. 链表的尾插

链表的尾插 两步操作

1. 找到链表的尾巴
2. 将新的结构体链接到尾巴上

void SListPushBack(SListNode* ps,SLTDataType x){SListNode* newnode = BuySListNode(x);SListNode* tail = ps;while (tail->next != NULL){tail = tail->next; //爬楼梯只需要爬到最高层// 而不是楼顶 否则新来的无处可以上去}tail->next = newnode;}

这个代码有一个问题 如果是链表是空的 ps指向的空 这个代码就处理不了 所以应多加一种情况

void SListPushBack(SListNode* ps, SLTDataType x){SListNode* newnode = BuySListNode(x);SListNode* tail = ps;if (ps == NULL){ps = newnode;}else{while (tail->next != NULL){tail = tail->next; //爬楼梯只需要爬到最高层// 而不是楼顶 否则新来的无处可以上去}tail->next = newnode;}}

这个代码还有一个隐藏的问题 ps虽然是指针 但也是变量 出函数失效。
所以应该传二级指针

void SListPushBack(SListNode** ps, SLTDataType x){SListNode* newnode = BuySListNode(x);SListNode* tail = *ps;if (*ps == NULL){*ps = newnode;}else{while (tail->next != NULL){tail = tail->next; //爬楼梯只需要爬到最高层// 而不是楼顶 否则新来的无处可以上去}tail->next = newnode;}}

1. 头插
   头插不就是修地下室嘛

头插也是两步：

1. 第一步 给第一层修个去地下室楼梯
   2. 第二步 把第一个改到地下室

void SListPsuhFront(SListNode** ps, SLTDataType x){SListNode* newnode=BuySListNode(x);newnode->next = *ps;*ps = newnode;}

1. 链表的尾删

尾删两步

1. 将楼梯置空
2. 将最高层移除

void SListPopBack(SListNode** ps){assert(ps);//空指针 直接报错SListNode* tail = *ps;if (tail->next == NULL){*ps = NULL; //一层楼直接平地}else{SListNode* value = NULL;while (tail->next != NULL){value = tail; // 先爬到要删的最高层tail = tail->next;}value->next = NULL;// 楼梯炸了free(tail);}}

1. 链表的头删

void SListPopFront(SListNode** ps){assert(ps);SListNode* head = *ps;if (head->next == NULL){*ps = NULL;free(*ps);}else{*ps=head->next;free(head);}}