数据结构（data structure）或具体数据类型（concrete data type）是指一组数据的内部存储方式。数组（array）和链接结构（linked structure）这两种数据结构是编程语言里多项集最常用的实现。在计算机的内存中，这两种结构类型采用不同的方法来存储和访问数据，这也导致操控多项集的算法会有不同的时间和空间权衡。本章将研究数组和链接结构所特有的数据组织方式，以及对它们进行操作的具体细节。在后续章节中，我们将讨论它们在实现其他各种类型多项集里的用法。

4.1　数组数据结构

数组是指在给定索引位置可以访问和替换的元素序列。你可能会觉得这个描述和 Python中的列表是一样的。这是因为，Python列表的底层数据结构正是一个数组。然而，Python程序员通常会在需要使用数组的地方用列表来实现，但Python和其他许多编程语言在实现多项集的时候多半会使用数组。因此，你需要熟悉如何使用数组。

本章里关于数组的很多内容也同样适用于Python的列表，但是数组的限制要更多。程序员只能在指定位置访问和替换数组中的元素、检查数组的长度、获取它的字符串表达式。程序员不能基于位置添加或删除元素，也不能对数组的长度进行修改。通常来说，数组的长度也就是它的容量，在创建之后就是固定的。

Python的array模块包含一个叫作array的类，它非常类似于列表，但是只能存储数字。为了方便后面的讨论，我们会定义一个叫作Array的新类。这个类会满足前面提到的关于数组的那些限制，可以存储任何类型的元素。有趣的是，这个Array类会用Python列表保存它里面的元素。这个类定义的方法允许用户使用下标运算符[]、len函数、str函数以及支持数组对象的for循环。表4-1列出了Array里这些操作所对应的方法，左边一列里的变量a代表Array类的对象。

表4-1　数组的操作和Array类的方法

当Python遇到表4-1左边那一列的操作时，它会自动调用右边一列里Array对象的相应方法。比如，在for循环里遍历Array对象时，Python就会自动调用Array对象里的__iter__方法。从表里也可以看到，程序员在创建数组时也必须指定它的容量（也就是物理尺寸）。在需要的情况下，可以用None对整个数组进行默认的覆盖填充。

下面是Array类的代码（在arrays.py文件里）。

"""
File: arrays.py
An Array is like a list, but the client can use
only [], len, iter, and str.

To instantiate, use
<variable> = Array(<capacity>, <optional fill value>)

The fill value is None by default.
"""
class Array(object):
    """Represents an array."""

    def __init__(self, capacity, fillValue = None):
        """Capacity is the static size of the array.
        fillValue is placed at each position."""
        self.items = list()
        for count in range(capacity):
            self.items.append(fillValue)

    def __len__(self):
        """-> The capacity of the array."""
        return len(self.items)

    def __str__(self):
        """-> The string representation of the array."""
        return str(self.items)

    def __iter__(self):
        """Supports traversal with a for loop."""
        return iter(self.items)

    def __getitem__(self, index):
        """Subscript operator for access at index."""
        return self.items[index]

    def __setitem__(self, index, newItem):
        """Subscript operator for replacement at index."""
        self.items[index] = newItem

下面这个Shell交互展示了数组的用法。

>>> from arrays import Array
>>> a = Array(5)                         # Create an array with 5 positions
>>> len(a)                               # Show the number of positions
5
>>> print(a)                             # Show the contents
[None, None, None, None, None]
>>> for i in range(len(a)):              # Replace contents with 1..5
         a[i] = i + 1
>>> a[0]                                 # Access the first item
1
>>> for item in a:                       # Traverse the array to print all
         print(item)
1
2
3
4
5

可以看出，数组是一个有严格限制的列表。

4.1.1　随机访问和连续内存

下标操作或索引操作会让程序员非常轻松地在指定位置对元素进行存储或检索。数组的索引操作是非常快的。数组索引是随机访问（random access）操作，而在随机访问时，计算机总会执行固定的步骤来获取第

个元素的位置。因此，不论数组有多大，访问第一个元素所需的时间和访问最后一个元素所需要的时间都是相同的。

计算机通过分配一块连续内存（contiguous memory）单元来存储数组里的元素，从而支持对数组的随机访问，如图4-1所示。

图4-1　一块连续内存

虽然现实情况并不会这样完美，但是为了简便易懂，这个图假定每个数据元素都只占用一个内存单元。机器地址是8位二进制数。

由于数组里的元素地址都是按照数字顺序进行排列的，因此可以通过添加两个值来计算出数组元素的机器地址，它们是数组的基地址（base address）以及元素的偏移量（offset）。其中，数组的基地址就是第一个元素的机器地址，而元素的偏移量就是它的索引值再乘以一个代表数组元素所需内存单元数的常量（在Python里，这个值始终是1）。简而言之，Python数组里的索引操作包括下面两个步骤。

• 得到数组内存块的基地址。
• 将索引值添加到这个地址并返回。

在这个例子里，数组内存块的基地址是100111012，并且每个元素都需要一个内存单元。索引位置2处的数据元素的地址是210+100111012，也就是100111112。

对于随机访问需要注意的一点是，计算机不用在数组里搜索给定的单元，也就是说，并不用从数组的第一个单元开始向右逐一移动计数，直至到达第

个单元结束。虽然常数时间内可以完成的随机访问应该是数组里效率最高的操作了，但是实现这个功能要求必须在连续内存块里存储数组。稍后你就会看到，这样做会让数组在执行其他操作时产生一些额外的成本。

4.1.2　静态内存和动态内存

在比较老的编程语言（如FORTRAN或Pascal）里，数组是静态数据结构。在这种情况下，数组的长度或容量在编译时就确定了，因此程序员需要通过一个常量来指定它的大小。由于程序员在运行时不能改变数组的长度，因此他在编写代码的时候就要预测程序里所有的应用需要多大的数组内存。如果这个程序总是使用一个已知元素数量并且固定大小的数组，就没有任何问题。但是在其他情况下，数据元素的数量会有不同，那么程序员就只能申请足够多的内存来满足在数组里存储可能有最大数量元素的情况。显然，在程序里这样做会浪费大量的内存。更糟糕的是，当数据元素的数量超过数组的长度时，程序仍然只能返回错误消息。

像Java和C++这类的现代编程语言会允许程序员创建动态数组（dynamic array），从而为这个问题提供了一种补救方法。和静态数组相似的是，动态数组也会占用一块连续内存，并支持随机访问。但是，动态数组的长度只在运行时才知道。因此，Java或C++程序员可以在动态数组实例化的时候指定它的长度。在Python里实现的Array类的行为也是这样的。

好在，程序员可以通过另一种方法在运行时根据应用程序的数据要求来调整数组的长度。这时，数组有以下3种不同形式。

• 在程序启动时创建一个具有合理默认大小的数组。
• 当数组无法容纳更多数据时，创建一个更大的新数组，并把旧数组里的数据元素传输给它。
• 如果数组在浪费内存（应用程序删除了一些数据），那么用类似的方式减小数组的长度。

显然，这些调整会由Python列表自动进行。

4.1.3　物理尺寸和逻辑尺寸

使用数组时，程序员往往必须区分它的长度（也就是物理尺寸）及其逻辑尺寸。数组的物理尺寸（physical size）是指数组单元的总数，或者创建数组时指定其容量的那个数字；而数组的逻辑尺寸（logical size）是指当前应用程序使用的元素数量。当数组被填满的时候，程序员并不需要担心它们的不同。但是，这样的情况并不常见。图4-2展示了3个物理尺寸相同但逻辑尺寸不同的数组，可以看到，当前已被数据占用的单元被加上了阴影。

图4-2　具有相同物理尺寸、不同逻辑尺寸的数组

左边两个数组里包含垃圾内容（garbage）的部分是可以访问的。换句话说，这些内存单元里的数据对当前应用程序是没有用的。因此，程序员在大多数应用程序里都要注意对数组的物理尺寸和逻辑尺寸进行追踪。

通常来说，逻辑尺寸和物理尺寸会告诉你有关数组状态的几个重点。

• 如果逻辑尺寸为0，那么数组就为空。也就是说，这个数组不包含任何数据元素。
• 如果并非上述情况，在任何情况下，数组中最后一个元素的索引都是它的逻辑尺寸减1。
• 如果逻辑尺寸等于物理尺寸，那么表示数组已被填满了。

练习题

1．请说明随机访问的工作原理，以及这个操作这么快的原因。

2．数组和Python列表之间有什么区别？

3．请说明数组的物理尺寸和逻辑尺寸之间的区别。

4.2　数组的操作

接下来，我们将学习如何实现数组的几种操作。数组类型到目前为止并没有提供这些操作，因此在程序员使用之前要先编写它们。在后面的例子里，我们可以先假定有下面这些数据配置。

DEFAULT_CAPACITY = 5
logicalSize = 0
a = Array(DEFAULT_CAPACITY)

可以看到，这个数组的初始逻辑尺寸是0，而默认的物理尺寸（也就是容量）是5。对于每个使用这个数组的方法来说，我们将给出关于其实现方式的说明以及相应带有注释的Python代码段。同样地，这些操作也用来定义包含数组的多项集方法。

4.2.1　增大数组的尺寸

当数组的逻辑尺寸等于它的物理尺寸时，如果要插入新的元素，就需要增大数组的尺寸。如果需要为数组提供更多内存，Python的list类型会在调用insert或append方法时执行这个操作。调整数组尺寸的过程包含如下3个步骤。

• 创建一个更大的新数组。
• 将数据从旧数组中复制到新数组。
• 将指向旧数组的变量指向新数组对象。

下面是这个操作的代码。

if logicalSize == len(a):
     temp = Array(len(a) + 1)             # Create a new array
     for i in range(logicalSize):         # Copy data from the old
         temp [i] = a[i]                  # array to the new array
     a = temp                             # Reset the old array variable
                                          # to the new array

可以看到，旧数组所使用的内存留给了垃圾回收器，并且在这段代码里，还会把数组的长度增加一个内存单元来容纳新元素。那么，请思考这个逻辑对性能所产生的影响。在调整数组尺寸时，复制操作的数量是线性增长的。因此，将

个元素添加到数组里的总时间复杂度是1+2+3+…+

，也就是

(

+1)/2，因此是

。

可以在每次增大数组尺寸时把数组尺寸翻倍，以得到一个更合理的时间复杂度，如下所示：

temp = Array(len(a) * 2)          # Create new array

这个版本的操作时间的复杂度分析将作为练习留给你。当然，这里对时间复杂度的提升是以耗费一些内存作为代价的。这样可让这个操作的总体空间复杂度为线性，因为无论用哪一种策略增大数组尺寸，总是需要一个数组来存放数据。

4.2.2　减小数组的尺寸

如果减小数组的逻辑尺寸，就会浪费相应的内存单元。因此，当删除某一个元素，并且未使用的内存单元数达到或超过了某个阈值（如数组物理尺寸的3/4）时，就该减小物理尺寸了。

如果浪费的内存超过特定阈值，那么Python的list类型会在调用pop方法时执行减小数组物理尺寸的操作。减小数组尺寸的过程与增大数组尺寸的过程相反，步骤如下所示。

• 创建一个更小的新数组。
• 将数据从旧数组中复制到新数组。
• 将指向旧数组的变量指向新数组对象。

当数组的逻辑尺寸小于或等于其物理尺寸的1/4，并且它的物理尺寸至少是这个数组建立时默认容量的2倍时，这个过程的相应代码就该派上用场了。这个算法会把数组的物理尺寸减小到原来的一半，并且也不会小于其默认容量。下面是相应的代码。

if logicalSize <= len(a) // 4 and len(a) >= DEFAULT_CAPACITY * 2:
    temp = Array(len(a) // 2)        # Create new array
    for i in range(logicalSize):     # Copy data from old array
         temp [i] = a [i]            # to new array
    a = temp                         # Reset old array variable to
                                     # new array

可以看到，这个策略允许在减小数组尺寸时浪费一些内存。这样做是为了降低向任何一个方向上继续调整大小的可能性。对减少数组尺寸操作的时间/空间复杂度分析将作为练习留给你。

4.2.3　将元素插入增大的数组

把元素插入数组中和替换数组里的元素是不一样的。在执行替换操作时，元素已在一个给定的索引位置，因此对这个位置进行简单复制就可以了，这时数组的逻辑尺寸并不会改变。但是，在执行插入操作时，程序员必须做以下这4件事。

• 就像前文提到的，在插入元素之前先检查可以使用的空间，根据需要来增大数组的物理尺寸。
• 将数组里从逻辑结尾到目标索引的所有元素向后移动。这个过程会在目标索引位置处为新元素留下一个空格。
• 将新元素分配到目标索引位置。
• 将逻辑尺寸加1。

图4-3展示了将元素D5插入包含4个元素的数组位置1所需要的步骤。

图4-3　将元素插入数组

可以看到，元素的移动顺序非常重要。如果是从目标索引处开始移动元素，那么会丢失它后面的两个元素。因此，在把每个元素复制到它后面的内存单元时，必须从数组的逻辑结尾开始再回溯到目标索引的位置。下面是Python中插入操作的代码。

# Increase physical size of array if necessary
# Shift items down by one position
for i in range(logicalSize, targetIndex, -1):
    a[i] = a[i - 1]
# Add new item and increment logical size
a[targetIndex] = newItem
logicalSize += 1

在平均情况下，执行插入操作时移动元素的时间复杂度是线性的，因此插入操作的时间复杂度也是线性的。

4.2.4　从数组里删除元素

从数组里删除元素的步骤正好和将元素插入数组中的相反，步骤如下。

• 将数组里从目标索引到逻辑结尾的所有元素向前移动。这个过程会关闭删除目标索引位置中的元素所留下的空格。
• 将逻辑尺寸减1。
• 检查是否存在内存空间的浪费，并根据需要减小数组的物理尺寸。

图4-4展示了从包含5个元素的数组里将位置1处的元素删除的步骤。

和插入操作一样，元素的移动顺序非常重要。对于删除操作来说，应从目标位置后面的那个元素开始，朝着数组的逻辑结尾处移动，并把每个元素都复制到它前面的那个内存单元里。下面是Python中删除操作的代码。

# Shift items up by one position
for i in range(targetIndex, logicalSize - 1):
     a[i] = a[i + 1]
# Decrement logical size
logicalSize -= 1
# Decrease size of array if necessary

图4-4　从数组里删除元素

同样，在平均情况下，移动元素的时间复杂度是线性的，因此删除操作的时间复杂度也是线性的。

4.2.5　复杂度的权衡：时间、空间和数组

数组结构在运行时性能和内存使用上做出了十分有趣的取舍。表4-2列出了所有数组操作的运行时复杂度以及两个其他操作的运行时复杂度：在数组的逻辑结尾处插入和删除元素。

表4-2　数组操作的运行时复杂度

可以看到，数组提供了对已经存在的元素进行快速访问的功能，以及在逻辑结尾处快速插入和删除的功能。然而，在任意位置处进行插入和删除操作的速度则会慢上一个数量级。调整数组的尺寸也需要线性时间，但是因为这个操作会把数组尺寸加倍或减半，所以可以最大限度地减少需要执行的次数。

由于偶尔会调整数组的尺寸，因此插入和删除操作在使用内存的时候会有

的复杂度。如果用了前文讨论的方法，那么这就是最坏情况下的性能；而在平均情况下，这些操作的内存使用情况仍然为O(1)。

使用数组的时候，内存里唯一真正被浪费的是那些尚未填充满的数组单元。评估数组内存使用率的一个非常有用的概念是负载因子（load factor）。数组的负载因子等同于它所存储的元素数除以数组的容量。比如，当数组已满的时候，负载因子就是1；当数组为空时，负载因子就是0；当内存单元的容量为10且占用了3个单元时，负载因子就是0.3。当数组的负载因子降到某个阈值（如0.25）以下时，你就可以通过调整数组尺寸将浪费的内存单元数保持在尽可能低的水平。

练习题

1．请说明为什么插入或删除给定元素时必须要移动数组里的某些元素。

2．在插入过程中，移动数组元素时，要先移动哪个元素？先移动插入位置的元素，还是最后一个元素？为什么？

3．如果插入位置是数组的逻辑末尾，请说明这个插入操作的运行时复杂度。

4．假设数组当前包含14个元素，它的负载因子为0.70，那么它的物理容量是多少？

4.3　二维数组（网格）

到目前为止，我们讨论的数组只能用来表示简单的元素序列，这可以称为一维数组（one-dimensional array）。对于许多应用程序来说，二维数组（two-dimensional array）或者说网格（grid）非常有用。比如，包含数字的表格可以被实现为二维数组。图4-5就展示了4行5列的二维数组。

图4-5　具有4行5列的二维数组（网格）

假设这个网格叫作grid。要访问grid里的元素，可以通过两个下标来指定其行和列的相应位置，并且这两个索引都是从0开始的。

x = grid[2][3] # Set x to 23, the value in (row 2, column 3)

在本节中，我们将学习如何创建和处理简单的二维数组（网格）。例子里的这些网格都是矩形的，并且有固定的尺寸。

4.3.1　使用网格

除了用双下标，网格还必须要有两个方法，用来返回行数和列数。为了便于讨论，我们把这两个方法分别命名为getHeight和getWidth。用来操作一维数组的方法可以很容易地扩展到网格里。比如，下面这段代码会计算变量grid里所有数字的总和。外部循环会迭代4次并向下逐行移动，在每次进入外部循环的时候，内部循环都会迭代5次，从而在不同行的列之间移动。

sum = 0
for row in range(grid.getHeight()):            # Go through rows
     for column in range(grid.getWidth()):     # Go through columns
          sum +=grid[row][column]

在这里，通过使用getHeight和getWidth方法而不是具体的数字4和5，这段代码可以用在任何尺寸的网格上。

4.3.2　创建并初始化网格

假设存在一个叫作Grid的二维数组类。要创建一个Grid对象，应运行包含3个参数（高度、宽度以及初始的填充值）的Grid构造函数。下面这段代码实例化了一个具有4行5列并且填充值为0的Grid对象，然后将这个对象打印出来。

>>> from grid import Grid
>>> grid = Grid(4, 5, 0)
>>> print(grid)
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

在创建网格之后，你可以把它的内存单元重新设置为任何值。下面这段代码会遍历这个网格，并将它的内存单元设置成图4-5所示的值。

# Go through rows
for row in range(grid.getHeight()):
     # Go through columns
     for column in range(grid.getWidth()):
          grid[row][column] = int(str(row) + str(column))

4.3.3　定义Grid类

Grid类有点像前面介绍过的Array类。用户可以通过运行方法来得到它的行数和列数，并得到它的字符串表达式。但是，该类并不会提供迭代器。通过数组可以很方便地存储网格，顶层数组的长度等于网格的行数；而顶层数组里的每个内存单元也是一个数组，这个数组的长度是网格的列数。这个子数组包含给定行中的相应数据。为了支持客户端能够使用双下标，你只需要提供__getitem__方法。下面是Grid类的代码（在grid.py文件里）。

"""
Author: Ken Lambert
"""

from arrays import Array 

class Grid(object):
    """Represents a two-dimensional array."""

    def __init__(self, rows, columns, fillValue = None):
         self.data = Array(rows)
         for row in range (rows):
             self.data[row] = Array(columns, fillValue) 

    def getHeight(self):
       """Returns the number of rows."""
       return len(self.data) 

    def getWidth(self):
       "Returns the number of columns."""
       return len(self.data[0]) 

    def __getitem__(self, index):
       """Supports two-dimensional indexing
       with [row][column]."""
       return self.data[index] 

    def __str__(self):
       """Returns a string representation of the grid."""
       result = ""
       for row in range (self.getHeight()):
          for col in range (self.getWidth()):
               result += str(self.data[row][col]) + " "
          result += "\n"
       return result

4.3.4　参差不齐的网格和多维数组

到目前为止，我们所讨论的网格都是二维并且是矩形的。其实，你还可以把网格创建成参差不齐的样子，也可以创建高于两个维度的网格。

参差不齐的网格有固定的行数，但是每一行里的数据列数各有不同。列表数组或数组是可以实现这种网格的合适结构。

如果需要的话，可以在定义网格的时候就把维度传递给它。这时，唯一的限制就是计算机的内存容量了。比如，可以把三维数组当作一个盒子，里面装满了整齐排列在行和列里的更小的盒子。创建这个数组的时候需要指定它的深度、高度以及宽度。因此可以给数组类型添加一个叫作getDepth的方法，从而像getWidth和getHeight方法一样再得到这个维度的相关数据。在这个实现里，每个元素都可以通过3个作为索引的整数进行访问，也可以通过有3层循环的控制语句结构来使用它。

练习题

1．什么是二维数组（网格）？

2．请描述一个可能会用到二维数组的应用程序。

3．编写一个程序，使之可以在Grid对象里搜索一个负整数。循环应该在遇到网格里的第一个负整数的地方终止，这时变量row和column应该被设置为这个负数的位置。如果在网格里找不到负数，那么变量row和column应该等于网格的行数和列数。

4．说说运行下面这段代码后网格里的内容是什么。

matrix = Grid(3, 3)
for row in range(matrix.getHeight()):
     for column in range(matrix.getWidth()):
         matrix[row][column] = row * column

5．编写一段代码以创建一个参差不齐的网格，它的行分别用来存储3个、6个和9个元素。

6．提供一个把Grid类用作数据结构来实现三维array类的策略。

7．编写一段代码：这段代码会把三维数组里每个单元的值都初始化为它的3个索引位置。例如，如果位置是（深度、行、列），则对于位置（2、3、3）来说，它的值就是233。

8．编写一段代码：这段代码可以显示出三维数组里的所有元素。打印出的每一行数据都应该代表给定行和列里的所有元素，而深度将从第一个位置向后递归到最后一个位置。遍历应该从第1行、第1列以及第一个深度位置开始，依次遍历所有的深度、列和行。

4.4　链接结构

除了数组，链接结构也是在程序里常用的数据结构。和数组类似，链接结构也是一种具体的数据类型，可以用来实现若干类型的多项集（包括列表）。本书在稍后的部分将对如何在多项集（如列表和二叉树）里使用链接结构进行更深入的探讨。在本节里，我们将介绍程序员在使用链接结构实现任何类型的多项集时所必须要知道的几个特征。

4.4.1　单向链接结构和双向链接结构

顾名思义，链接结构由可以链接到其他节点的节点组成。尽管节点之间可能会有许多链接，但两个最简单的链接结构是：单向链接结构（singly linked structure）和双向链接结构（doubly linked structure）。

用框和指针符号可以绘制出非常有用的链接结构图例。图4-6就是用这两种符号表示的上面提到的两种链接结构。

图4-6　两种类型的链接结构

通过一个额外的头部链接（head link），可以使用单向链接结构访问第一个节点。接下来，用户就可以通过这个节点里发出的链接（由图4-6里的箭头表示）来访问其他节点了。因此，在单向链接结构里，你可以很容易地获得节点的后继节点，但不那么容易获得节点的前序节点。

双向链接结构会包含双向的链接，因此用户可以很轻松地移动到节点的后继节点或前序节点，这个时候会用到第二个额外的链接[被称为尾部链接（tail link）]，它能够让双向链接结构的用户直接访问最后一个节点。

在两种链接结构里，最后一个节点都没有指向后续节点的链接。在图4-6里，用斜杠代替箭头以表示没有链接，这称为空链接（empty link）。还有一点需要注意，在双向链接结构里，第一个节点也没有指向前序节点的链接。

和数组一样，这些链接结构也可以用来存储元素的线性序列。但是，使用链接结构的程序员无法通过指定的索引位置直接访问这个元素。在这种情况下，程序员必须从数据结构的一个顶端开始，然后按照链接进行访问，直至到达所需的位置（或找到期望的元素）为止。链接结构的这种性质对于很多操作都有显著的影响，这部分内容将在稍后讨论。

为链接结构分配内存的方式和为数组分配内存的方式是完全不同的，而且对于插入和删除操作来说，有两个显著影响。

• 在找到插入或删除点之后，可以在不移动内存里的数据元素的情况下执行插入或删除操作。
• 可以在每次插入或删除期间自动调整链接结构的大小，不需要花费额外的内存空间，也不需要复制数据元素。

接下来，我们将学习什么样的底层内存才能让链接结构具备这些优点。

4.4.2　非连续内存和节点

回想一下，数组里的元素必须存储在一段连续的内存中，这就意味着数组里各个元素的逻辑顺序和它们在内存单元里的物理顺序是紧密耦合的。相比而言，链接结构会把结构里各个元素的逻辑顺序和它们在内存里的顺序解耦。也就是说，要在内存的某个位置上找到链接结构里特定元素的内存单元，只需要让计算机跟随指向这个元素的地址或位置链接就行了。这称为非连续内存（noncontiguous memory）。

链接结构里用来存储的基本单位是节点（node），其中单向链接节点（singly linked node）包含下面这些组件或字段。

• 数据元素。
• 指向结构里下一个节点的链接。

对于双向链接节点（doubly linked node）来说，除了上述组件，还会包含一个指向结构里前一个节点的链接。

图4-7展示了内部链接为空的单向链接节点和双向链接节点。

图4-7　链接为空的两种节点类型

根据编程语言的不同，程序员可以通过下面几种方法来让节点利用非连续内存。

• 在FORTRAN这样的早期语言里，唯一的内置数据结构就是数组。在这种情况下，程序员可以通过两个并排的数组为单向链接结构实现非连续内存和节点。这两个数组里的第一个数组包含数据元素；第二个数组则包含数据数组里当前节点所对应的后续节点的索引位置。因此，随后的链接访问在这里也就代表着：用第一个数组里的数据元素索引来访问第二个数组里的值，然后再把这个值作为第一个数组里下一个数据元素的索引。在这里，空链接会用值?1来表示。图4-8展示了一个链接结构以及它的数组存储方式。可以看到，这样做可以有效地将链接结构里数据元素的逻辑位置和它在数组里的物理位置分离。

图4-8　通过数组表示链接结构

• 在更现代的语言里（比如Pascal和C++），程序员可以通过访问指针（pointer）直接得到所需的数据地址。在这些更现代的语言里，单向链接结构里的节点包含一个数据元素和一个指针值。对于空链接来说，它的指针值用特殊值null（或nil）来表示。这样，程序员就不用通过数组设置非连续内存了，而只需要向计算机请求一个名为对象堆（object heap）的新节点的指针。这个节点来自非连续内存的内置区域。然后，程序员把这个节点里的指针设置为指向另一个节点，从而建立到这个链接结构里其他数据的链接。通过显式地使用指针和内置堆，你可以得到比使用FORTRAN等语言更好的解决方案，因为不再需要负责管理非连续内存的底层数组存储方式了。毕竟，任何计算机的内存（RAM）也就只是一个大数组而已。但是，Pascal和C++还需要程序员来管理堆，因此程序员要通过特殊的dispose或delete操作把不使用的节点返回给堆。
• Python程序员通过使用对对象的引用（reference）设置节点和链接结构。在Python里，任何变量都可以用来引用任何数据，这也包括值None，它可以用来代表空链接。因此，Python程序员可以通过定义包含两个字段的对象来定义单向链接节点，这两个字段是对数据元素的引用和对另一个节点的引用。Python为每个新的节点对象提供非连续内存的动态分配，并且当应用程序不再引用这个对象的时候，它会自动把这部分内存返回给系统（垃圾回收）。

在接下来的讨论里，术语链接、指针和引用是可以互换使用的。

4.4.3　定义单向链接节点类

节点类非常简单，因为节点对象的灵活性和易用性非常重要，所以通常会引用节点对象的实例变量而不是方法调用，并且构造函数也需要用户在创建节点时可以设置节点的链接。前文提到，单向链接节点只包含数据元素和对下一个节点的引用。下面是用来实现单向链接节点类的代码。

class Node(object):
    """Represents a singly linked node."""

    def __init__(self, data, next = None):
         """Instantiates a Node with a default next of None."""
         self.data = data
         self.next = next

4.4.4　使用单向链接节点类

节点变量会被初始化为None或一个新的Node对象。下面这段代码展示了二者的不同。

# Just an empty link
node1 = None
# A node containing data and an empty link
node2 = Node("A", None)
# A node containing data and a link to node2
node3 = Node("B", node2)

图4-9展示了运行上述代码后这3个变量的状态。

图4-9　3个外部链接

你可以从图里看到下面几点。

• node1没有指向任何节点对象（是None）。
• node2和node3都指向了链接的对象。
• node2指向了下一个指针是None的对象。

接下来，假设要运行下面这个语句，以把第一个节点放置在已经包含了node2和node3的链接结构的开头：

node1.next = node3

这时，Python会引发AttributeError异常。因为变量node1的值是None，所以它并不包含用来引用节点对象的next字段。要创建所期望的链接，你可以运行以下代码。

node1 = Node("C", node3)

或者

node1 = Node("C", None)
node1.next = node3

通常来说，你可以在尝试访问字段之前，先检查给定的节点变量是不是None，以避免这个异常的发生。

if nodeVariable != None:
   <access a field in nodeVariable>

和数组一样，链接结构也可以通过循环来使用。可以用循环创建一个链接结构并访问其中的每个节点。下面这个测试脚本将用Node类创建一个单向链接结构，并打印出它的内容。

"""
File: testnode.py
Tests the Node class.
"""

from node import Node

head = None
# Add five nodes to the beginning of the linked structure
for count in range(1, 6):
    head = Node(count, head)
# Print the contents of the structure
while head != None:
    print(head.data)
    head = head.next

从代码里可以看到，这个程序有一个叫作head的指针，用于生成整个链接结构。这个指针的用法是让所有新插入的元素始终位于链接结构的开头。在显示数据时，它们会以和插入时相反的顺序出现。此外，当显示数据时，头部指针会被重置到下一个节点，直到头部指针变为None为止。因此，在这个过程结束之后，你就可以把链接结构里所有节点都删除。这些节点在程序里不再可用，并且会在下一次垃圾回收期间被回收。

本文摘自《数据结构（Python语言描述）（第2版）》

本书用Python语言来讲解数据结构及实现方法。全书首先概述Python编程的功能—这些功能是实际编程和解决问题时所必需的；其次介绍抽象数据类型的规范、实现和应用，多项集类型，以及接口和实现之间的重要差异；随后介绍线性多项集、栈、队列和列表；最后介绍树、图等内容。本书附有大量的复习题和编程项目，旨在帮助读者巩固所学知识。

本书不仅适合高等院校计算机专业师生阅读，也适合对Python感兴趣的读者和程序员阅读。