数据结构与算法：单链表-阿里云开发者社区

链表的定义和结构

链表是一种在计算机科学中常用的数据结构，用于存储元素的集合。它与数组相比，链表的元素不是在内存中连续存储的。链表由一系列节点组成，每个节点至少包含两个部分：一个是存储的数据，另一个是指向列表中下一个节点的指针（或引用）。通过这种方式，链表中的节点被串联起来

在顺序表中，我们的数据存储在数组中，每个数据在内存中连续存储，意味着可以通过索引直接访问任何元素

我们对顺序表进行数据的插入，物理空间不变，数据依次挪动。

链表中，我们每个节点的地址没有关联，是随机的，但是每个节点都有一个**指针，**让这个指针指向下一个节点的地址

我们设phead指针指向第一个地址，第一个节点的指针指向第二个节点的地址，最后一个节点的指针指向空

如果我们想在2 3节点中间插入新的数据a，并不需要挪动任何数据，只需要将2的指针指向a的地址，a的指针指向3的地址

若要删除3的数据，我们只需将2的指针指向4，并将3的空间释放掉即可

单链表的创建

1. typedef int SLNDataType;
2. 
3. typedef struct SListNode
4. {
5.  SLNDataType val;
6.  struct SListNode* next;
7. }SLNode;

其中typedef int SLNDataType;在顺序表中我们进行了讲述，为类型抽象

typedef struct SListNode
{
  SLNDataType val;
  struct SListNode* next;
}SLNode;
val

用于存储节点中的数据。数据类型由 SLNDataType 定义，当前是 int 类型，表示每个节点可以存储一个整数。

next 是一个指向下一个 SListNode 结构体的指针。它用于链接链表中的节点，使得可以从一个节点遍历到下一个节点。如果 next 为 NULL，则表示当前节点是链表的末尾。

链表的打印

我们定义了一个函数，它的作用是打印出一个单链表的所有节点值

void SLTPrint(SLNode* phead)
{
  SLNode* cur = phead;
  while (cur != NULL)
  {
  printf("%d->", cur->val);
  cur = cur->next;
  }
  printf("NULL");
  printf("\n");
}

我们来解析这个函数：

首先，函数内部定义了一个指针 cur 并将它初始化为指向链表的头节点 phead。这个指针用于遍历链表。

接着，函数进入一个 while 循环，条件是 cur != NULL，即只要 cur 指向的节点不是 NULL，循环就继续执行。这确保了函数能够遍历链表直到最后一个节点。

在循环体内，使用 printf 函数打印当前节点 cur 存储的整数值 cur->val，后面跟着一个箭头 ->，指示链表中的节点是如何连接的。

然后，cur 被更新为指向下一个节点 cur->next，准备打印下一个节点的值。这个步骤使得遍历可以继续进行。

一旦遍历完成（即 cur 为 NULL），循环结束。此时打印 “NULL” 来表示链表的结束

在后续我们会展示出来

创造节点

我们定义一个函数 CreatNode，用于创建一个新的链表节点 SLNode；

SLNode* CreatNode(SLNDataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  exit(-1);
  }
  newnode->val = x; 
  newnode->next = NULL;
  return newnode;
}

CreatNode 函数的目的是为了构造一个新的链表节点，并将其初始化。它接收一个参数 x，类型为 SLNDataType，这是链表节点存储数据的类型。函数的返回类型是 SLNode*，即新创建的链表节点的指针。我们来解析这个函数

通过调用 malloc(sizeof(SLNode)) 分配足够的内存来存储一个 SLNode 结构体实- 例。malloc 函数尝试分配指定大小的内存空间，并返回指向这块内存的指针。如果分配成功，这个指针指向的是新分配的内存；如果失败，则返回 NULL。

**初始化节点：**为新节点的 val 成员赋值参数 x，这表示节点存储的数据。将 next 成员设置为 NULL，表示新节点当前没有指向下一个节点

返回新节点：函数返回新创建的节点的指针，允许调用者将该节点添加到链表中的适当位置。

这个 CreatNode 函数用于创建并初始化链表的新节点。通过接收一个数据作为参数，并返回指向新分配和初始化的节点的指针，它为链表构造、数据插入等提供了基础。

单链表的尾插和头插

尾插

首先进行思考，我们能否这样定义函数？

void SLTPushBack(SLNode* pphead, SLNDataType x);

如果链表不为空，我们可以如下找到尾部

SLNode* newnode = CreatNode(x);
SLNode* tail = pphead;
while (tail->next != NULL) {
  tail = tail->next;
}
tail->next = newnode;

这里并没有对头指针进行任何的修改

如果链表为空，意味着我们需要将头指针指向空改为指向newnode，

我们想对一个数值通过函数修改，需要指针，那么对一个指针进行修改，则需要二级指针

所以函数定义如下：

void SLTPushBack(SLNode** pphead, SLNDataType x) {
  SLNode* newnode = CreatNode(x);
  if (*pphead == NULL) {
  *pphead = newnode;
  }
  else 
  {
  SLNode* tail = *pphead;
  while (tail->next != NULL) {
    tail = tail->next;
  }
  tail->next = newnode;
  }
}

这里，如果链表为空，插入新节点，则头指针发生了改变

我们再test文件中进行测试，创建并初始化头指针plist

尾插三次，插入1 2 3并打印，结果如下

头插

头插我们会改变头指针，也需要二级指针

1. void SLTPushFront(SLNode** pphead, SLNDataType x)
2. {
3. 
4.  SLNode* newnode = CreatNode(x);
5.  newnode->next = *pphead;
6.  *pphead = newnode;
7. }
8.

我们用pphead接收plist

newnode的指针next指向d1，即plist（*pphead）newnode->next = *pphead;，再让plist（*pphead）指向newnode。*pphead = newnode;

在这里，链表为空也无所谓，newnode指向NULL，plist指向newnode

测试如下

单链表的尾删和头删

尾删

void SLTPopBack(SLNode** pphead) 
{
  if (*pphead == NULL) {
  return; 
  }
  if ((*pphead)->next == NULL) {
  free(*pphead);
  *pphead = NULL;
  return;
  }
  SLNode* prev = *pphead;
  while (prev->next->next != NULL) { 
  prev = prev->next;
  }
  free(prev->next); 
  prev->next = NULL;
}

如果头指针指向 NULL，即链表没有节点，函数将直接返回，因为没有节点可以删除。

if ((*pphead)->next == NULL) {：这一行检查链表是否只有一个节点。它通过检查头节点的 next 指针是否为 NULL 来实现。如果是这种情况，说明链表中只有一个节点。free(*pphead);：如果链表只有一个节点，这行代码释放这个节点占用的内存。

pphead = NULL;：由于最后一个节点已被删除，链表现在为空。因此，需要将头指针设置为 NULL。

如果有多个节点，这个 while 循环遍历链表，直到 prev 指向倒数第二个节点。条件 prev->next->next != NULL 确保了 prev 停在倒数第二个节点，因为倒数第二个节点的下一个节点（即最后一个节点）的 next 指针是 NULL。 free(prev->next);：释放最后一个节点占用的内存。此时，prev->next 指向最后一个节点。

prev->next = NULL;：将倒数第二个节点的 next 指针设置为 NULL，从而移除对最后一个节点的引用，更新链表的末尾

1. void SLTPopFront(SLNode** pphead) {
2.  if (*pphead == NULL) {
3.   return; 
4.  }
5.  SLNode* temp = *pphead;
6.  *pphead = (*pphead)->next;
7.  free(temp);
8. }

如果链表为空，直接返回，如果不为空，temp和*pphead现在指向同一块空间，我们让头指针指向第二个节点，现在只有temp指向第一个节点，释放第一个节点的空间

测试代码

寻找某个节点

SLNode* SLTFind(SLNode* phead, SLNDataType x) 
{
  SLNode* current = phead; 
  while (current != NULL) {
  if (current->val == x) {
    return current; 
  }
  current = current->next; 
  }
  return NULL; 
}

初始化一个名为 current 的指针，用于遍历链表

在循环体内，if (current->val == x) 检查当前节点的值是否为目标值 x,若当前节点的值不是目标值，则通过 current = current->next; 将 current 更新为下一个节点的指针，继续遍历链表。

在指定位置后面插入节点

void SLTInsertAfter(SLNode* pos, SLNDataType x) {
  if (pos == NULL) {
  return;
  }
  SLNode* newnode =CreatNode(x);
  newnode->next = pos->next; 
  pos->next = newnode; 
}

首先检查pos是否为NULL，如果是，则不进行插入

若不为空，则让newnode指向pos原来指向的节点，pos指向newnode完成插入

测试如下，我们已经有了三个数据1 2 3，在2后面插入4

首先找到2节点的地址，再传入insert函数中即可

在指定位置前面插入节点

要在指定位置之前插入一个新节点，情况就稍微复杂一点，因为单向链表的节点只包含指向下一个节点的指针，没有指向前一个节点的指针。这意味着，要实现这一功能，你需要找到目标位置的前一个节点，然后在这个节点之后插入新节点。以下是实现这一功能的方法

void SLTInsertBefore(SLNode** phead, SLNode* pos, SLNDataType x) {
  if (*phead == NULL || pos == NULL || *phead == pos) {
  SLNode* newnode = CreatNode(x);
  if (*phead == pos) {
    newnode->next = *phead;
    *phead = newnode;
  }
  else {
    free(newnode); 
  }
  return;
  }
  SLNode* current = *phead;
  while (current->next != NULL && current->next != pos) {
  current = current->next;
  }
  if (current->next != pos) {
  return;
  }
  SLNode* newnode = CreatNode(x);
  newnode->next = pos;
  current->next = newnode;
}

首先检查链表是否为空，或者目标位置是否是链表的第一个节点

如果是第一个节点，则意味着头插

如果pos为NULL，表示在空链表中插入，或者pos不在链表中

将创建的newnode释放掉

if (*phead == NULL || pos == NULL || *phead == pos) {
  SLNode* newnode = CreatNode(x);
  if (*phead == pos) {
    newnode->next = *phead;
    *phead = newnode;
  }
  else {
    free(newnode); 
  }
  return;
  }

寻找pos前的节点

SLNode* current = *phead;
while (current->next != NULL && current->next != pos) {
  current = current->next;
}

如果没有找到pos，则不执行插入

if (current->next != pos) {
        return;
    }

在pos前插入新节点

SLNode* newnode = CreatNode(x);
  newnode->next = pos;
  current->next = newnode;
}

测试代码如下：在1 2 3的2前面插入4

首先找到2节点的地址再传入插入函数

在指定位置后面删除节点

void SLTEraseAfter(SLNode* pos) {
    if (pos == NULL || pos->next == NULL) {
        return;
    }
    SLNode* temp = pos->next;
    pos->next = temp->next;
    free(temp);
}

首先检查pos是否为空或pos之后没有节点，因为如果 pos 是 NULL，则没有任何节点可操作；如果 pos->next 是 NULL，则 pos 是链表中的最后一个节点，没有节点需要被删除。

将**待删除的节点（pos->next）**的地址存储在一个临时变量中。

更新 pos->next 指针，使其指向待删除节点的下一个节点。

释放待删除节点的内存，以防止内存泄漏。

测试代码如下，删除1 2 3中2后面的数据

在指定位置前面删除节点

在单向链表中删除某个指定位置pos之前的节点比删除其之后的节点稍微复杂，因为链表的单向性质意味着不能直接访问前驱节点。为了删除给定pos之前的一个节点，我们首先需要找到这个节点的前两个节点（即要删除的节点的前驱节点和要删除的节点）。然后，通过调整前驱节点的next指针，绕过要删除的节点，最后释放要删除的节点的内存。

1. void SLTEraseBefore(SLNode** phead, SLNode* pos) {
2. 
3.  if (*phead == NULL || pos == NULL || *phead == pos) return;
4. 
5.  if ((*phead)->next == pos) {
6.   SLNode* temp = *phead;
7.   *phead = (*phead)->next; 
8.   free(temp);
9.   return;
10.   }
11.   SLNode* prev = NULL;
12.   SLNode* current = *phead;
13.   while (current != NULL && current->next != pos) {
14.   prev = current;
15.   current = current->next;
16.   }
17.   if (current == NULL || current->next != pos) return;
18.   if (prev != NULL) {
19.   prev->next = current->next;
20.   free(current);
21.   }
22. }

如果链表为空，pos为空，或pos是链表的第一个节点，无法删除前一个节点

if (*phead == NULL || pos == NULL || *phead == pos) return;
1
if ((*phead)->next == pos) {
  SLNode* temp = *phead;
  *phead = (*phead)->next; // 移动头指针
  free(temp);
  return;
  }

这段代码的目的是处理一个特殊的情况：当我们想要删除位于给定pos节点之前的节点，且该pos恰好是链表的第二个节点时。下面分步解释这个代码块的含义和作用：

条件检查 (if ((*phead)->next == pos)): 这个条件检查链表的头节点（*phead）的下一个节点是否就是我们的目标位置pos。如果是，这意味着我们需要删除链表的第一个节点（即头节点），因为我们想要删除的是位于pos之前的节点，且pos是链表的第二个节点。

删除头节点:

SLNode* temp = *phead;：首先，我们将头节点（要删除的节点）的地址保存在临时变量temp中，以便之后能够安全地释放该节点占用的内存。

*phead = (*phead)->next;：接着，我们将头指针（*phead）向前移动到下一个节点，这实际上是在更新链表的头节点为原头节点的下一个节点。简单来说，我们就是把头指针指向了链表的第二个节点，从而在逻辑上“删除”了原来的第一个节点（头节点）。

释放内存 (free(temp);: 最后，使用free(temp);来释放原头节点占用的内存。

SLNode* prev = NULL;
  SLNode* current = *phead;
  while (current != NULL && current->next != pos) {
  prev = current;
  current = current->next;
  }

找到pos之前的节点

if (current == NULL || current->next != pos) return;
1
无法找到有效的pos位置，pos不在列表中，则返回
if (prev != NULL) {
  prev->next = current->next;
  free(current);
}

删除current的节点，即pos之前的节点；

测试代码如下，删除1 2 3中2前面的节点

本节内容到此结束，感谢大家观看！

数据结构与算法：单链表

链表的定义和结构

若要删除3的数据，我们只需将2的指针指向4，并将3的空间释放掉即可

创造节点

热门文章

最新文章

相关课程

相关电子书

相关实验场景