内容表
- 介绍
- 先决条件
- 什么是linkedlist
- 为什么我们使用linkedlist
- 在C 中实现linkedlist
如果您正在阅读本文,我想您正在开始数据结构和算法的旅程。如果是这样,您正在阅读正确的文章。在开始之前,让我列出一些先决条件 - 我们需要知道的术语和概念,以便完全理解LinkedList的概念。
连续和非连续内存块:在连续的内存分配中,一个具有唯一地址的内存块分配给需要它的文件或过程。在非连续内存块中,不同位置的随机内存块分配给文件或进程。 LinkedList落入后者。这是LinkedList和数组之间的核心差异之一。数组存储在连续的内存位置。
struct :这是将C和其他相关语言中不同数据类型相关变量分组的一种方法。
结构
使用malloc 的动态内存分配:由于LinkedList中的项目存储在机器内存中的随机或不同位置中,因此我们需要动态操纵内存 - 即这使我们需要了解称为malloc的标准c lib()函数。
什么是链接列表?
我想,在您的旅程中,您熟悉数组。像数组一样的链接列表是线性数据结构。您可以依次依次存储数据。然而,在数组中,元素存储在同一内存位置,但在链接列表中,元素存储在内存中的不同位置。列表或列表项或节点的元素存储在不同的内存位置中。这些列表项目或节点中的每一个都包含两件事:
- 数据 - 可以是任何数据类型
- 下一个项目或节点的内存地址 - 指针
为什么使用链接列表?
动态大小:链接列表具有可变大小。阵列具有固定尺寸。如果您的目的编号或数据量在程序运行时会有所不同,则使用linkedlist是公平的。
更快的插入和删除:使用LinkedList插入和删除操作更快或更高的计算效率。如果您要对数据进行大量插入和删除,那么LinkedList更好。
实现链接列表
好的,在本文的这一部分中,我们将以C语言编写代码来实现LinkedList。它将从用户那里获取多个数据,并使用它们来创建链接列表。它需要并从用户那里获得的第一个数据是列表保存的几个数据。然后,它将提示用户输入数据,直到等于用户定义的数据数。接下来,该程序将打印出所有内容。
现在让我们开始。
步骤1 。首先,在代码块IDE中创建C项目。内部
main.c file:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data; //data of the node
struct node *nextPtr; //address of the next node
};
在上面的代码中,我们导入该程序所需的标准C库,还为列表创建了一个节点。该节点具有两个变量 - 一个用于存储数据的INT变量。另一个变量是将指针(内存地址)存储到下一个节点或列表项目。
步骤2:
struct node *startNode;
//function to create the list
static void createNodeList(int totalNodes);
static void displayList();
我们声明了指向起点节点的指针,还创建了两个函数原型。第一个函数将创建linkedlist。第二个将打印。
步骤3 :
int main()
{
int numberOfNodes;
printf("Input the number of nodes: ");
scanf("%d ", &numberOfNodes);
createNodeList(numberOfNodes);
displayList();
return 0;
}
主要功能是每个C程序的入口点。因此,我们创建了主函数,在主函数内部,我们声明了一个int varible numberofnodes,以保留列表的节点数。接下来,我们打印用户输入列表将包含的最大节点数,我们将存储在已声明的变量中。
步骤4 :
static void createNodeList(int totalNodes)
{
struct node *newNode;
struct node *nodeBuffer;
int nodeData;
int nodeCounter;
//allocate memory for starting node
startNode = (struct node*)malloc(sizeof(struct node));
//at this point you can check if the memory allocation is
//and stop the program if not
}
在第四步中,我开始定义第一个功能。我创建了许多变量,首先是结构节点类型以容纳新节点。下一个是缓冲区。下一个节点数据和节点计数器。
接下来,我使用malloc将内存分配给起始节点。请注意评论。我跳了。
步骤5:
printf("input data for node1: ");
scanf("%d", &nodeData);
//save user input to the data element of the node
startNode->data = nodeData;
//initialize the nodes next pointer to null
startNode->nextPtr = NULL;
//Point the buffer to address of the first node
nodeBuffer = startNode;
您已要求第一个用户输入并将其分配给节点。问题是要使用循环来获取其余部分。一个带有一个包含数据的节点的链接列表基本上具有两个节点。所以。
步骤6:
for(nodeCounter =2; nodeCounter<=totalNodes; nodeCounter++)
{
newNode = (struct node*)malloc(sizeof(struct node));
//exit if new node cannot be allocated
if(newNode == NULL)
{
printf("Memory cannot be allocated.");
break;
}
else
{
printf("input data for node %d: ",nodeCounter);
scanf("%d", &nodeData);
newNode->data = nodeData;
newNode->nextPtr = NULL;
//Link the previous node to the current node
nodeBuffer->nextPtr = newNode;
//copies address of current node
nodeBuffer = nodeBuffer->nextPtr;
}
}
nb:到目前为止,代码仍在createNodelist函数中,我们从步骤4开始。
我们现在需要做的下一件事是创建一个可以将我们的节点列表打印到控制台的函数。
步骤7:
static void displayList(){
struct node *nodeBuffer;
nodeBuffer = startNode;
//exit if it is empty
if(nodeBuffer == NULL){
printf("List is empyt");
return 0;
}
else{
//check if the current node is empty
while (nodeBuffer != NULL)
{
//PRINT THE DATA OF CRRENT NODE
printf("DATA: %d \n", nodeBuffer->data);
//go to the next node
nodeBuffer = nodeBuffer->nextPtr;
}
}
}
在本文中,您必须学习您需要理解的知识以了解LinkedList,以及LinkedList是什么,LinkedList和Array之间的区别以及为什么我们使用LinkedList。
参考:
Image Credit goes to Geekforgeeks
有用的资源:
源代码:Here
我是Vincent Ikechukwu,完整的堆栈Web开发人员和软件工程师。