深入浅出链表

目录

1.链表的基本概念及结构

1.1基本概念

1.2结构

2.链表的分类

3.链表的实现（循环链表增删查改实现）

1.动态申请节点（结点）​编辑

2.单链表打印

3.单链表尾插

4.单链表头插

5.单链表尾删

6.单链表头删

7.单链表查找

8.在指定位置之前插入数据

9.在指定位置之后插入数据

10.删除pos节点

11.删除pos之后的节点

12.销毁链表

---

1.链表的基本概念及结构

        链表是一种常见的基础数据结构，它由一系列节点（Node）组成，每个节点包含数据和到下一个节点的引用（指针）。以下是链表的基本概念及其结构：

1.1基本概念

1. 节点（Node）：链表的基本单元，每个节点包含两部分，一部分是存储数据的域（称为数据域），另一部分是存储下一个节点地址的域（称为指针域或链接域）。

2. 头节点（Head）：链表的第一个节点，通常用于表示整个链表。

3. 尾节点（Tail）：链表的最后一个节点，其指针域通常指向NULL，表示链表的结束。

4. 链表的长度：链表中节点的数量。

5. 链表的遍历：按照节点间的链接顺序访问链表中的每个节点。

6. 动态性：链表的大小不是固定的，可以在运行时动态地增加或减少节点。

1.2结构

        在C语言中，链表节点通常使用结构体（struct）来定义。以下是链表节点的一个基本结构：

链表的结构就像是火车一样一节一节的连在一起。

但是每个节点的地址并不像顺序表一样是连续的，而是随机存储的，因此每个节点才需要下一个节点的地址来找到下一节点。

2.链表的分类

1. 单向链表（Singly Linked List）:

   • 每个节点包含一个数据域和一个指向下一个节点的指针。
   • 遍历链表只能从头节点开始，并且只能向一个方向进行。

2. 双向链表（Doubly Linked List）:

   • 每个节点包含一个数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。
   • 可以从两个方向遍历链表。

3. 循环链表（Circular Linked List）:

   • 单向链表的变种，最后一个节点的指针指向头节点，形成一个环。
   • 可以从任意节点开始遍历整个链表。

4. 双向循环链表（Doubly Circular Linked List）:

   • 双向链表的变种，头节点的前一个指针指向最后一个节点，最后一个节点的下一个指针指向头节点，形成一个环。
   • 可以从任意节点开始，向前或向后遍历整个链表。

3.链表的实现（循环链表增删查改实现）

1.动态申请节点（结点）

• SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));：使用malloc函数动态分配一个SLTNode大小的内存块，并将其强制转换为SLTNode*类型的指针。sizeof(SLTNode)获取SLTNode结构体的大小。

• if (newnode == NULL)：检查malloc是否成功分配了内存。如果newnode是NULL，说明内存分配失败。

• perror("malloc fail!");：如果内存分配失败，使用perror函数打印错误消息。

• exit(1);：如果内存分配失败，终止程序执行，返回错误代码1。

• newnode->data = x;：将传入的参数x赋值给新节点的数据域。

• newnode->next = NULL;：将新节点的指针域初始化为NULL，表示当前节点后面没有其他节点。

• return newnode;：返回新创建的节点。

2.单链表打印

3.单链表尾插

• assert(pphead);：使用assert宏来确保传入的头节点指针的指针不是NULL。如果pphead是NULL，程序将终止执行。

• SLTNode* newnode = SLTBuyNode(x);：调用之前定义的SLTBuyNode函数来创建一个新的节点，并将数据x存储在新节点的数据域。

• if (*pphead == NULL)：检查链表是否为空。如果链表为空（即头节点指针为NULL），则将新节点设置为头节点。

• else：如果链表不为空，则需要找到链表的最后一个节点。

• SLTNode* ptail = *pphead;：初始化一个指针ptail，指向头节点。

• while (ptail->next)：遍历链表，直到找到最后一个节点（即节点的next指针为NULL）。

• ptail = ptail->next;：在循环中，将ptail移动到下一个节点。

• ptail->next = newnode;：当找到最后一个节点时，将其next指针指向新创建的节点，从而将新节点添加到链表的末尾。

4.单链表头插

• assert(pphead);：使用assert宏来确保传入的pphead不是NULL。如果pphead是NULL，程序将在这里终止。

• SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据x存储在新节点的数据域中。

• newnode->next = *pphead;：将新节点的next指针指向原来的头节点。这一步是为了将新节点插入到链表的头部。

• *pphead = newnode;：更新头节点指针，使其指向新创建的节点。这样，新节点就成为了链表的新头部。

5.单链表尾删

这个接口的实现一开始先要判断链表是否为单节点链表，如果是则直接释放头节点，不是则进行相应的操作。

• assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。

• if ((*pphead)->next == NULL)：检查链表是否只有一个节点。如果是，直接释放这个节点，并将头节点指针设置为NULL。

• else：如果链表有多个节点，需要遍历链表找到最后一个节点。

• while (ptail->next)：遍历链表直到ptail指向最后一个节点。

• free(ptail);：释放最后一个节点的内存。

• ptail = NULL;：将ptail指针设置为NULL，防止野指针。

• prev->next = NULL;：将倒数第二个节点的next指针设置为NULL，断开与已删除节点的连接。

6.单链表头删

这里的(*pphead)->next不能写成*pphead->next 因为->预算符优先级是高于*的。

• assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。

• SLTNode* next = (*pphead)->next;：保存头节点的下一个节点指针。这是因为一旦释放头节点，我们就无法访问链表的其余部分。

• free(*pphead);：释放头节点的内存。

• *pphead = next;：更新头节点指针，使其指向原来的第二个节点（现在成为新的头节点）。

7.单链表查找

• assert(phead);：使用assert宏来确保传入的phead不是NULL。如果phead是NULL，程序将在这里终止。

• SLTNode* plist = phead;：初始化一个指针plist，使其指向头节点。

• while (plist)：开始循环，当plist不为NULL时继续执行。

• if (plist->data == x)：检查当前节点的数据是否与要查找的值x匹配。

• return plist;：如果找到匹配的节点，返回该节点。

• plist = plist->next;：如果没有找到匹配的节点，移动plist到下一个节点。

• return NULL;：如果在链表中没有找到匹配的节点，返回NULL。

8.在指定位置之前插入数据

9.在指定位置之后插入数据

• assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。

• assert(pos);：使用assert宏来确保传入的pos不是NULL。如果pos是NULL，程序将在这里终止。

• SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据x存储在新节点的数据域中。

• if (pos == *pphead)：检查插入的位置是否是头节点。如果是，使用SLTPushFront函数在头节点位置插入新节点。

• else：如果插入的位置不是头节点，需要找到pos的前一个节点。

• SLTNode* prev = *pphead;：初始化prev指针指向头节点。

• while (prev->next != pos)：遍历链表直到找到pos的前一个节点。

• newnode->next = pos;：将新节点的next指针指向pos。

• prev->next = newnode;：将pos的前一个节点的next指针指向新节点。

10.删除pos节点

• assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。

• assert(pos);：使用assert宏来确保传入的pos不是NULL。如果pos是NULL，程序将在这里终止。

• if (pos == *pphead)：检查要删除的节点是否是头节点。如果是，使用SLTPopFront函数执行头删操作。

• else：如果要删除的节点不是头节点，需要找到该节点的前一个节点。

• SLTNode* prev = *pphead;：初始化prev指针指向头节点。

• while (prev->next != pos)：遍历链表直到找到pos的前一个节点。

• prev->next = pos->next;：将pos的前一个节点的next指针指向pos的下一个节点，完成删除操作。

• free(pos);：释放pos节点的内存。

• pos = NULL;：将pos指针设置为NULL，防止野指针。

11.删除pos之后的节点

• assert(pos);：使用assert宏来确保传入的pos不是NULL。如果pos是NULL，程序将在这里终止。

• SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据x存储在新节点的数据域中。

• newnode->next = pos->next;：将新节点的next指针指向pos的下一个节点，这样新节点就位于pos的后面。

• pos->next = newnode;：将pos的next指针指向新节点，完成新节点的插入操作。

12.销毁链表

• assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。

• SLTNode* pcur = *pphead;：初始化一个指针pcur，使其指向头节点。

• while (pcur)：开始循环，当pcur不为NULL时继续执行。

• SLTNode* next = pcur->next;：保存pcur的下一个节点的指针，因为pcur将被释放。

• free(pcur);：释放pcur节点的内存。

• pcur = next;：移动pcur指针到下一个节点。

• *pphead = NULL;：循环结束后，将头指针设置为NULL，表示链表已被销毁。