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

数据结构】单链表详解（超详细）"/>

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

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

注意：

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

目录

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

结构体的创建：

这里要注意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高强度冲浪