【数据结构】单链表详解（超详细）

单链表是我们学习数据结构时必不可少的部分，但也由于指针的参与变得更加复杂，这篇文章学习完之后可以更好地理解与掌握链表结构

注意：

数据结构中，不在乎菜单的创建，注重的是功能的实现；菜单的创建会影响我们的调试

目录 结构体的创建：动态申请节点：打印：尾插：头插：尾删：头删：链表查找：链表插入某节点：链表删除某节点：

结构体的创建：

这里要注意typedef的灵活使用，可以更方便的使用与修改结构体，不必牵一发而动全身

typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; 动态申请节点：

在我们前插或者尾插时，需要一个新的结点，故我们需要一个申请节点的函数帮助我们，同时我们需要返回这个地址，否则将会内存泄漏

SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } 打印：

打印可以很好的帮助我们检查我们写的程序有无错误

void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } 尾插：

单链表尾差与顺序表尾差完全不一样，要知道，单链表在创建头结点时：SListNode* ps = NULL;
我们发现，创建的头结点是一个指针，而我们尾插时如果是第一个元素，就会改变ps的值，而改变一个指针的值需要传入指针的地址，故：

void SListPushBack(SListNode** pplist, SLTDateType x) //传入二级指针，可以改变ps的值 { SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* cur= *pplist; while (cur->next != NULL) { cur = cur->next; } cur->next = newnode; } } 头插：

与尾插同理，需要二级指针

void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; } 尾删： void SListPopBack(SListNode** pplist) { assert(*pplist); SListNode* cur = *pplist; if (cur->next == NULL) { *pplist = NULL; } else { while (cur->next->next != NULL) { cur = cur->next; } free(cur->next); cur->next = NULL; } } 头删： void SListPopFront(SListNode** pplist) { assert(*pplist); SListNode* cur = (*pplist)->next; free(*pplist); *pplist = cur; } 链表查找： SListNode* SListFind(SListNode* plist, SLTDateType x) { assert(plist); SListNode* cur = plist; while (cur->next) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }

(插入,删除）与查找通常是配套使用

链表插入某节点：

单链表插入时只能向后插入，因为单链表只能找到后边的节点却无法找到前边的节点，故链表的形态多种多样，适用各种场景

void SListInsertAfter(SListNode* pos, SLTDateType x) { SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; } 链表删除某节点： void SListEraseAfter(SListNode* pos) { assert(pos->next); SListNode* cur = pos; SListNode* tmp = pos->next; cur->next = cur->next->next; free(tmp); }

欢迎讨论，有问题可以及时找我沟通，每天25h高强度冲浪