logo图片
数据结构与算法

链表

链表是一系列数据结构,它们通过链接连接在一起。
链接列表是包含项目的链接序列。每个链接都包含与另一个链接的连接。链表是仅次于数组的第二大数据结构。以下是理解链表概念的重要术语。
Link-链表的每个链接都可以存储一个称为元素的数据。 Next-链表的每个链接都包含一个指向名为 Next 的下一个链接的链接。 LinkedList-链接列表包含指向名为 First 的第一个链接的连接链接。

链表表示

链表可以可视化为一个节点链,其中每个节点都指向下一个节点。
链接列表
根据上图,以下是需要考虑的重点。
Linked List 包含一个名为 first 的链接元素。 每个链接都带有一个数据字段和一个名为 next 的链接字段。 每个链接都使用其下一个链接与其下一个链接相链接。 最后一个链接带有一个为空的链接以标记列表的结尾。

链表的类型

以下是各种类型的链表。
单向链表-项目导航仅向前。 双向链表-项目可以向前和向后导航。 循环链表-最后一项包含第一个元素的链接作为下一个,第一个元素具有到最后一个元素的链接作为前一个。

基本操作

以下是列表支持的基本操作。
插入-在列表的开头添加一个元素。 删除-删除列表开头的元素。 显示-显示完整列表。 搜索-使用给定键搜索元素。 删除-使用给定键删除元素。

插入操作

在链表中添加新节点是一项不止一步的活动。我们将在这里通过图表来了解这一点。首先,使用相同的结构创建一个节点,并找到它必须插入的位置。
链接列表插入
假设我们在 A (LeftNode) 和 C (RightNode) 之间插入一个节点 B (NewNode)。然后点 B.next 到 C-
NewNode.next −> RightNode;
它应该看起来像这样-
链接列表插入
现在,左边的下一个节点应该指向新节点。
LeftNode.next −> NewNode;
链接列表插入
这会将新节点放在两者的中间。新列表应如下所示-
链接列表插入
如果节点被插入到列表的开头,则应该采取类似的步骤。在最后插入时,列表的倒数第二个节点应指向新节点,新节点将指向 NULL。

删除操作

删除也是一个不止一步的过程。我们将通过图形表示来学习。首先,通过搜索算法找到要移除的目标节点。
链接列表删除
目标节点的左(前一个)节点现在应该指向目标节点的下一个节点-
LeftNode.next −> TargetNode.next;
链接列表删除
这将删除指向目标节点的链接。现在,使用以下代码,我们将删除目标节点指向的内容。
TargetNode.next −> null;
链接列表删除
我们需要使用已删除的节点。我们可以将其保存在内存中,否则我们可以简单地释放内存并彻底清除目标节点。
链接列表删除

逆向操作

这个操作很彻底。我们需要让最后一个节点被头节点指向,并反转整个链表。
链表逆向操作
首先,我们遍历到列表的末尾。它应该指向 NULL。现在,我们让它指向它的前一个节点-
链表逆向操作
我们必须确保最后一个节点不是最后一个节点。所以我们会有一些临时节点,它看起来像指向最后一个节点的头节点。现在,我们将所有左侧节点一个一个指向它们之前的节点。
链表逆向操作
除了头节点指向的节点(第一个节点)外,所有节点都应该指向它们的前任,使它们成为新的后继。第一个节点将指向 NULL。
链表逆向操作
我们将使用临时节点使头节点指向新的第一个节点。
链表逆向操作
链表现在反转了。要查看 C 编程语言中的链表实现,请单击此处。
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4