链接列表教程:–动态数据存储入门

披露: 您的支持有助于保持网站的正常运行!我们会为此页面上推荐的某些服务收取推荐费.


当必须构造不同的数据集并为程序组织线性信息时,链接列表可能是一个有价值的工具。它们通常用作阵列的替代品,因为它们具有使用它们的某些好处.

链表的核心是一个简单的数据结构,其中包含一系列节点。每个节点都有自己的数据,以及指向另一个节点的指针。实际上,通常会教他们,以使学生适应指针.

在下面,您将了解什么是链表,它们为什么有价值,以及如何创建它们。我们还将提供一些其他资源,以帮助您进一步接受教育.

什么是链接列表?

简而言之,链接列表是数据的有序集合。它用于线性数据结构,是最容易实现的动态数据结构之一。每个数据元素称为一个节点,并包含一个值和一个指向列表中下一个节点的指针。如果指针具有NULL值,则该节点是列表中的最后一个节点.

为了帮助理解这一概念,下面是计算机技术之外的示例:

假设您要根据输入速度为办公室中的每个人评分。您的清单将从Ann开始,因为每个人都知道她是最快的-您可以听到来自她隔间的声音。有人告诉她,第二快的人是史蒂夫。史蒂夫(Steve)知道他的打字速度接近安(Ann)的打字速度,但还不如安。他还知道凯伦(Karen)几乎和他一样快,但不尽然。该列表然后可以这种方式继续。每位成员都拥有独特的信息,并附有指标,指出谁是第二快的打字员.

由于节点之间存在相互独立的关系(指针关系除外),因此添加,删除和移动它们非常容易.

链接列表的类型

有几种不同类型的链表。单个链表,双链表,多链表和循环链表。我们将在下面更详细地探讨每一个。使用链接列表,您可以执行插入,删除和遍历操作.

1.单链表

单个链接列表是数据对象的集合,这些数据对象通过某些引用从一个对象到下一个对象链接在一起。这些对象通常称为节点。每个节点将至少包含一个数据字段和对下一个节点的引用。单个链接列表可通过第一个节点访问,并且可以遍历列表的末尾.

2.双链表

双链表在每个节点上都有两个引用。引用指向下一个节点和上一个节点。通过这种结构,您可以双向访问数据集,它可以为您提供更大的灵活性和速度,因为您可以双向浏览列表.

3.多链表

多链接列表是常规链接列表,具有来自某个节点的多个其他列表。新列表可以采用此处提到的任何样式。这种列表样式有助于对按用户姓名和年龄细分的列表进行排序。或者,其他样式的数据集,其中每个数据点都有进一步的分类.

4.通报链表

链表的最终类型称为循环链表。而不是最后一个节点具有NULL命令,它将引用回到列表的开头。列表的结构类似于上面的选项.

为什么链接列表很重要

链接列表由于其动态性质而很有用。从计算的角度来看,它仅在需要时才分配内存。因此,如果您的应用程序需要经常调整大小,删除,插入和更新数据,那么链表将是理想的选择.

链表通常用于实现图形,堆栈,队列和其他类似程序。使用链接列表,您可以在列表中的任何位置插入项目。另外,您无需事先知道最终列表的大小。您可以根据需要增大或减小尺寸.

易于插入和删除是链表的主要优点。例如,您可以使用数组,但是数组仅允许您添加和删除序列中的最后一个对象,而无需移动一堆数据来创建开放的插槽。链接列表可轻松进行顺序的数据集操作,而不会给内存资源造成巨大压力.

大多数计算机科学程序会继续教会学生如何实现链接列表,作为对您可能希望在实际程序中使用的动态数据结构的坚实介绍。另外,即使您永远不会使用链表,它也会为您提供足够的知识以使用指针。您肯定会在许多现实生活中的程序中使用指针.

链表的缺点

链接列表非常适合创建易于修改的列表。但是,它们并不是每个程序的完美解决方案,如下所示:

  1. 链接列表不提供随机访问点。为了到达列表中的某个项目,您必须迭代列表中的每个项目,直到该点为止.
  2. 由于动态内存分配和指针都需要代码才能起作用,因此代码可能会有点复杂.
  3. 链表的总开销可能高于数组,因为链表是动态分配的.

综上所述,知道如何使用链表将帮助您掌握指针的使用,并更好地理解整个动态数据集.

链接列表教程

您将在下面了解如何创建和实施基本的链接列表。我们将首先创建一个链接列表及其节点,然后说明如何删除和插入新节点.

创建节点结构

链表包含多个节点,因此我们需要创建一个定义节点的结构。这将需要包括至少一个用于数据的变量和一个指向下一个节点的指针。为了我们的目的,我们将坚持使用打字速度示例,并使用此人的姓名和速度以及我们的数据。在C语言中,数据将按以下结构定义:

结构节点{
字符串名称[32];
整数速度
struct节点* next;
}

这里重要的是下一个指针,它使我们能够遍历列表.

创建链接列表

现在,我们需要创建一个列表,它实际上只是在创建第一个节点。因此,我们定义了它,为单个节点分配了足够的内存,并将下一个指针设置为NULL,这样我们就知道列表的结尾了。您还设置了指向它的起始指针,因为这是链接列表的起点.

然后,您可以填写该节点的信息:员工的姓名和他们的打字速度.

插入节点

创建基本列表后,我们现在就可以开始向列表中添加元素了。因此,假设您从Karen开始,他的打字速度为每分钟58个单词。接下来,您要以63的速度输入Steve。您将为其创建一个节点并填写数据。然后,您将搜索链接列表,但是在这种情况下,将只有一个元素。您会注意到,史蒂夫的打字速度更快,因此您可以将他的下一个指针设置为凯伦的指针。由于Karen的指针也是头指针,因此您需要将头指向Steve的节点.

现在,您有了从Steve的节点开始的链接列表。接下来将指向Karen的节点。 Karen的节点将指向NULL,表示她的节点是列表中的最后一个节点.

如果以打字速度在Karen和Steve之间雇用了一名雇员,则将为他们创建一个节点。但随后,史蒂夫的下一个将指向新员工,而新员工的下一个将指向凯伦的.

另一方面,如果雇用员工的打字速度小于Karen的打字速度,则会再次为他们创建一个节点。但是Karen的下一个将指向新员工,而新的下一个将指向NULL.

删除节点

从链接列表中删除节点实际上是一个简单的过程。我们将要删除的员工之前的下一个指针指向要删除的员工之后的员工。然后,我们将释放已删除节点的内存,否则将导致内存泄漏.

当然,使用链接列表可以做更多的事情。如果您有兴趣进一步探索链接列表,请查看下面突出显示的资源.

链表资源

了解了链接列表的基本概念之后,就该增加知识了。下面我们提供一些其他资源,以帮助您真正掌握链接列表并更深入地了解数据结构:

  • Narasimha Karumanchi撰写的《数据结构和算法变得轻松》(2016年):一本关于数据结构的好书,它将使您远远超出链接列表的范围.
  • 链表基础知识(PDF):这26页的PDF将为您提供伪代码和C语言示例所需要的几乎所有内容.
  • 数据结构的简要介绍:此简单介绍将带您一路创建第一个链表程序.
  • 链接列表教程:这是有关在C中创建链接列表的7个简短视频的集合++.
  • Learn-C.org链接列表页面:此页面引导您创建一个简单的C语言链接列表.
  • 使用Javascript的数据结构:通过此JavaScript教程在浏览器内部学习链接列表.

摘要

链接列表为管理和创建动态数据集提供了一个很棒的概念和实用方法。希望以上信息可以帮助您掌握和实现基本的链接列表,然后您将继续前进。.

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me