数组与链接列表
数组是存储元素集合的最常用的数据结构。大多数编程语言都提供了方法来轻松地声明数组和访问数组中的元素。链表，更确切地说是单链表，也是一种可以用来存储元素集合的数据结构。它由一系列节点组成，每个节点都有对序列中下一个节点的引用。
如图1所示，是一段代码，通常用于声明并向数组赋值。图2描述了数组在内存中的样子。
上面的代码定义了一个可以存储5个整数的数组，并使用索引0到4访问它们。数组的一个重要属性是整个数组被分配为一个内存块，每个元素在数组中都有自己的空间。一旦定义了数组，它的大小就固定了。因此，如果在编译时不确定数组的大小，那么就必须定义一个足够大的数组来保证安全。但是，在大多数情况下，我们实际使用的元素数量少于我们分配的数量。所以相当多的内存实际上被浪费了。另一方面，如果“足够大的数组”实际上不够大，程序就会崩溃。
链表在它自己的内存块中将内存分别分配给它的元素，通过将这些元素作为链中的链接链接来获得整体结构。图3中的每个字段都有两个链接的列表元素。数据字段保存存储的实际数据，下一个字段保存对链中下一个元素的引用。链接列表的第一个元素存储为链接列表的头。
| 数据 | 下一个 |
图3：链表的元素
图4描述了一个包含三个元素的链表。每个元素存储其数据，除最后一个元素外的所有元素都存储对下一个元素的引用。最后一个元素的下一个字段中包含一个空值。列表中的任何元素都可以通过从开头开始并跟随下一个指针来访问，直到满足所需的元素为止。
