数据结构和算法链表

链表是一系列数据结构,通过链接连接在一起。

链接列表是包含项目的一系列链接。每个链接包含与另一个链接的连接。链表是数组后第二常用的数据结构。以下是理解Linked List概念的重要术语。

  • 链接- 链表的每个链接都可以存储一个称为元素的数据。
  • 下一步- 链表的每个链接都包含指向下一个名为Next的链接的链接。
  • LinkedList- 链接列表包含指向名为First的第一个链接的连接链接。

链表清单表示

链表可以显示为节点链,其中每个节点指向下一个节点。

链接列表 如上图所示,以下是需要考虑的重点。

  • 链接列表包含一个名为first的链接元素。
  • 每个链路都带有一个数据字段和一个名为next的链接字段。
  • 使用下一个链接将每个链接与其下一个链接链接。
  • 最后一个链接带有一个null链接以标记列表的结尾。

链表的类型

以下是各种类型的链表。

  • 简单链接列表- 项目导航仅限前进。
  • 双重链接列表- 项目可以向前和向后导航。
  • 循环链接列表- 最后一项包含第一个元素的链接作为next,第一个元素具有前一个元素的链接。

基本操作

以下是列表支持的基本操作。

  • 插入- 在列表的开头添加元素。
  • 删除- 删除列表开头的元素。
  • 显示- 显示完整列表。
  • 搜索- 使用给定键搜索元素。
  • 删除- 使用给定键删除元素。

插入操作

在链接列表中添加新节点是一个以上的步骤活动。我们将在这里用图表来学习。首先,使用相同的结构创建一个节点,并找到它必须插入的位置。

链接列表插入 想象一下,我们在A(LeftNode)和C(RightNode)之间插入节点B(NewNode)。然后将B.next指向C -


NewNode.next −> RightNode;

It应该是这样的 -

链接列表插入 现在,左侧的下一个节点应指向新节点。


LeftNode.next −> NewNode;

链接列表插入 这将把新节点放在两个中间。新列表应如下所示 -

链接列表插入 如果在列表的开头插入节点,则应采取类似步骤。在末尾插入时,列表的倒数第二个节点应指向新节点,新节点将指向NULL。

删除操作

删除也是一个不止一步的过程。我们将学习图画表达。首先,使用sear找到要删除的目标节点清算法。

链表删除 目标节点的左(上一个)节点现在应该指向目标节点的下一个节点 -


LeftNode.next −> TargetNode.next;

链接列表删除 这将删除指向目标节点的链接。现在,使用以下代码,我们将删除目标节点指向的内容。


TargetNode.next −> NULL;

链接列表删除 我们需要使用已删除的节点。我们可以将其保留在内存中,否则我们可以简单地释放内存并完全擦除目标节点。

链接列表删除 反向操作

这项操作是彻底的。我们需要让头节点指向最后一个节点并反转整个链表。

链接列表反向操作 首先,我们遍历到列表的末尾。它应该指向NULL。现在,我们将指出它以前的节点 -

链接列表反向操作 我们必须确保最后一个节点不是丢失的节点。所以我们将有一些临时节点,它看起来像指向最后一个节点的头节点。现在,我们将使所有左侧节点逐一指向其先前的节点。

链接列表反向操作 除了头节点指向的节点(第一个节点)之外,所有节点都应指向它们的前任,使它们成为新的后继节点。第一个节点将指向NULL。

链接列表反向操作 我们将使用temp节点使头节点指向新的第一个节点。

链接列表反向操作 链接列表现在已反转。要查看C编程语言中的链表实现,请单击此处。