数据结构&算法 链表
-
链表
链表是一系列数据结构,它们通过链接连接在一起。链接列表是包含项目的一系列链接。每个链接都包含到另一个链接的连接。链表是仅次于数组的第二大数据结构。以下是了解链接列表概念的重要术语。- Link —— 链表中的每个链接(Link)都可以存储一个称为元素的数据。
- Next —— 链表中的每个链接都包含一个指向下一个链接的链接,该链接称为Next。
- LinkedList —— 一个链表包含到第一个称为first的链接的连接链接。
-
链表表示
链接列表可以可视化为节点链,其中每个节点都指向下一个节点(Node)。根据上面的说明,以下是要考虑的重点。- 链表包含一个名为first的链接元素。
- 每个链接包含一个或多个数据字段和一个称为next的链接字段。
- 每个链接都使用其下一个链接与其下一个链接链接。
- 最后一个链接的链接为空,以标记列表的结尾。
-
链接列表的类型
以下是各种类型的链表。- 单向链表 - 项目导航仅向前。
- 双向链表 - 项目可以向前和向后导航。
- 循环链表 - 最后一项包含第一个元素的链接作为下一个,而第一个元素具有到最后一个元素的链接作为上一个。
-
基本操作
以下是列表支持的基本操作。- 插入 - 在列表的开头添加一个元素。
- 删除 - 删除列表开头的元素。
- 显示 - 显示完整列表。
- 搜索 - 使用给定的键搜索元素。
- 删除 - 使用给定的键删除元素。
-
插入操作
在链接列表中添加新节点是一项以上的活动。我们将在这里通过图表来学习。首先,使用相同的结构创建一个节点,并找到必须将其插入的位置。想象一下,我们要在A(LeftNode)和C(RightNode)之间插入节点B(NewNode)。然后将B.next指向C-它看起来应该像这样-现在,左侧的下一个节点应指向新节点。这会将新节点置于两者的中间。新列表应如下所示-如果将节点插入列表的开头,则应采取类似的步骤。在末尾插入时,列表的倒数第二个节点应指向新节点,而新节点将指向NULL。 -
删除操作
删除也是一个多步骤的过程。我们将以图片表示形式学习。首先,通过使用搜索算法找到要删除的目标节点。现在,目标节点的左(上一个)节点应指向目标节点的下一个节点-这将删除指向目标节点的链接。现在,使用以下代码,我们将删除目标节点指向的对象。我们需要使用已删除的节点。我们可以将其保留在内存中,否则我们可以简单地重新分配内存并完全擦除目标节点。 -
反转操作
此操作是彻底的。我们需要使最后一个节点由头节点指向,并反转整个链表。首先,我们遍历列表的末尾。它应该指向NULL。现在,我们将其指向其先前的节点-我们必须确保最后一个节点不是最后一个节点。因此,我们将有一些临时节点,看起来像头节点指向最后一个节点。现在,我们将使所有左侧节点一个接一个地指向其先前的节点。除头节点指向的节点(第一个节点)外,所有节点都应指向其前任节点,使其成为新的后继节点。第一个节点将指向NULL。我们将使用临时节点使头节点指向新的第一个节点。现在,链接列表已反转。 -