DSA 内存中的链表
计算机内存
为了解释什么是链表，以及链表与数组的不同之处，我们需要了解一些关于计算机内存工作原理的基本知识。
计算机内存是程序运行时使用的存储空间。 这里存储着你的变量、数组和链表。
内存中的变量
假设我们要将整数“17”存储在变量 myNumber 中。为了简单起见，假设该整数存储为两个字节（16 位），并且 myNumber 在内存中的地址为 0x7F30。
0x7F30 实际上是存储 myNumber 整数值的两个字节内存中的第一个字节的地址。 当计算机访问 0x7F30 读取整数值时，它知道必须读取第一个和第二个字节，因为在这台特定计算机上，整数是两个字节。
下图显示了变量 myNumber = 17 如何存储在内存中。
上面的例子展示了如何在简单但流行的 Arduino Uno 微控制器上存储整数值。 此微控制器具有 8 位架构，带有 16 位地址总线，并使用两个字节存储整数和两个字节存储内存地址。 相比之下，个人电脑和智能手机使用 32 位或 64 位存储整数和地址，但内存的工作原理基本相同。
内存中的数组
为了理解链表，首先了解数组如何在内存中存储非常有用。
数组中的元素在内存中连续存储。 这意味着每个元素都存储在紧接上一个元素之后。
下图显示了整数数组 myArray = [3,5,13,2] 如何存储在内存中。 这里我们使用一种简单的内存，每个整数使用两个字节，就像前面的例子一样，只是为了理解概念。
计算机只知道 myArray 的第一个字节的地址，因此要使用代码 myArray[2] 访问第三个元素，计算机从 0x7F28 开始，跳过前两个整数。 计算机知道一个整数存储在两个字节中，因此它从 0x7F28 向前跳过 2x2 个字节，并从地址 0x7F32 开始读取值 13。
当在数组中删除或插入元素时，后面的每个元素必须向上移动以腾出新元素的空间，或者向下移动以占用被删除元素的空间。 此类移位操作非常耗时，并且可能导致实时系统出现问题，例如。
下图显示了删除数组元素时元素的移位方式。
在 C 语言中，操作数组也是你需要考虑的事情，因为你需要在插入或删除元素时显式地移动其他元素。 在 C 语言中，这不是在后台完成的。
在 C 语言中，你还需要确保你已经为数组分配了足够的初始空间，以便之后可以添加更多元素。
你可以在这篇之前的 DSA 教程页面上了解更多关于数组的信息：DSA 数组.
内存中的链表
我们可以创建一个链表，而不是将一组数据存储为数组。
链表在许多场景中使用，例如动态数据存储、栈和队列实现或图表示，仅举几例。
链表由包含某种数据和至少一个指向其他节点的指针或链接的节点组成。
使用链表的一大优势是，节点可以存储在内存中的任何可用空间，节点不必像数组中的元素一样连续存储在彼此之后。 链表的另一个优点是，当添加或删除节点时，列表中的其余节点不必移动。
下图显示了如何在内存中存储链表。 链表有四个节点，值分别为 3、5、13 和 2，每个节点都包含一个指向列表中下一个节点的指针。
每个节点占用四个字节。 两个字节用于存储整数值，两个字节用于存储指向列表中下一个节点的地址。 如前所述，存储整数和地址所需的字节数取决于计算机的架构。 这个例子，就像前面的数组例子一样，符合简单的 8 位微控制器架构。
为了更清楚地显示节点之间的关系，我们将以更简单的方式显示链表中的节点，与它们在内存中的位置关系较小，如下图所示。
如果我们使用这种新的可视化方式将前面的例子中的四个节点放在一起，它看起来像这样
如你所见，链表中的第一个节点称为“头”，最后一个节点称为“尾”。
与数组不同，链表中的节点不在内存中彼此紧邻。 这意味着当插入或删除节点时，不需要移动其他节点，这是一件好事。
链表的一个不太好的地方是，我们不能像访问数组那样直接访问节点，例如只需写 myArray[5]。 要访问链表中的第 5 个节点，我们必须从称为“头”的第一个节点开始，使用该节点的指针访问下一个节点，并以此类推，同时跟踪我们已访问的节点数量，直到到达第 5 个节点。
学习链表有助于我们更好地理解内存分配和指针等概念。
在学习树和图等更复杂的数据结构之前，了解链表也很重要，因为这些结构可以使用链表实现。
现代计算机中的内存
在本页上，我们一直使用 8 位微控制器中的内存作为例子，为了简单易懂。
现代计算机中的内存的工作原理与 8 位微控制器中的内存原理相同，但使用更多的内存来存储整数，并使用更多的内存来存储内存地址。
下面的代码显示了我们正在运行这些例子的服务器上整数的大小和内存地址的大小。
例子
使用 C 语言编写的代码
#include <stdio.h>
int main() {
int myVal = 13;
printf("Value of integer 'myVal': %d\n", myVal);
printf("Size of integer 'myVal': %lu bytes\n", sizeof(myVal)); // 4 bytes
printf("Address to 'myVal': %p\n", &myVal);
printf("Size of the address to 'myVal': %lu bytes\n", sizeof(&myVal)); // 8 bytes
return 0;
}上面的代码示例只能在 C 语言中运行，因为 Java 和 Python 运行在比特定/直接内存分配更高的抽象级别上。
C 语言中的链表实现
让我们实现前面提到的链表
让我们在 C 语言中实现这个链表，以了解链表如何在内存中存储的具体例子。
在下面的代码中，在包含库之后，我们创建一个节点结构，它类似于表示节点是什么的类：节点包含数据和指向下一个节点的指针。
createNode() 函数为新节点分配内存，使用作为函数参数传递的整数填充节点的数据部分，并返回指向新节点的指针（内存地址）。
printList() 函数只是遍历链表并打印每个节点的值。
在 main() 函数中，创建了四个节点，将它们链接在一起，打印它们，然后释放内存。 在使用完内存后释放内存是一个好习惯，可以避免内存泄漏。 内存泄漏是指使用完内存后没有释放，导致逐渐占用越来越多的内存。
例子
C 语言中的基本链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void printList(Node* node) {
while (node) {
printf("%d -> ", node->data);
node = node->next;
}
printf("null\n");
}
int main() {
Node* node1 = createNode(3);
Node* node2 = createNode(5);
Node* node3 = createNode(13);
Node* node4 = createNode(2);
node1->next = node2;
node2->next = node3;
node3->next = node4;
printList(node1);
// Free the memory
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
}为了打印上面代码中的链表，printList() 函数使用“next”指针从一个节点移动到下一个节点，这被称为链表的“遍历”。 您将在 链表操作页面 上了解有关链表遍历和其他链表操作的更多信息。
Python 和 Java 中的链表实现
我们现在将使用 Python 和 Java 实现同一个链表。
在下面的 Python 代码中，Node 类表示节点是什么：节点包含数据和指向下一个节点的链接。
Node 类用于创建四个节点，然后将这些节点链接在一起，并在最后打印出来。
如您所见，Python 代码比 C 代码短很多，如果您只想理解链表的概念，而不是链表在内存中的存储方式，那么它可能更好。
Java 代码与 Python 代码非常相似。 点击下面的“运行示例”按钮，然后选择“Java”选项卡查看 Java 代码。
例子
Python 中的基本链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
