本文内容目录如下，会分拆为两篇笔记，另一则笔记是 "数组和链表结构(python)_1"。
3. 链表结构
Linked Structures
在数组之后，链表结构可能使程序中最常用的数据结构。
3.1 单链表结构和双链表结构
单链表结构(Singly Linked Structure)和双链表结构(Doubly Linked Structure)是两种最简单的链表结构，其结构如下图所示：
单链表结构的用户通过外部的头链接(head link)可访问链表的第一个节点，然后根据该节点提供的信息，便可访问其后继项，并以此类推。在单链表结构中，很容易获取当前节点的后继项，但很难获取当前节点的前驱项。
双链表包含两个方向的链接，因此用户很容易获取当前项的前驱项和后继项。双链表还提供了名为尾链接(tail link)的外部链接，以便用户直接访问链表的最后一项。
两种链表的最后一项都不包含指向下一项的链接，这种情况被称为空链接(empty link)。双链表的第一项和最后一项都包含空链接。
链表结构无法通过索引直接访问其中的某项，必须从链表的第一项起沿着链表找寻目标索引。
3.2 非连续性内存和节点
数组使用的是连续内存，而链表是用的是非连续性内存(Noncontiguous Memory) 。
链表结构的基本单位是节点(node)，它包含了一个数据项和一个对后继项的引用。双链表的节点中还包含了一个对前驱项的引用。
注意，不同于 C++ 使用指针指向后继项，Python 直接引用后继项即可。在 Python 中变量可以引用任何内容，包括 None(表示空链接)。
3.3 定义单链表的节点类
Defining a Singly Linked Node Class Node
节点类很简单，其构造方法允许用户设置节点连接，不过节点对象通常不包含方法调用。
class Node(object):
def __init__(self, data, next=None):
"""Instantiates a Node with default next of None"""
self.data = data
self.next = next
def __str__(self):
return str(self.data)
# Just an None object
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)
执行上述代码后，三个变量的状态如下图所示：
下面的代码展示了使用循环方式来创建一个链表结构，并访问其中的每一个节点。其中最新插入的项总位于链表前端。另外，当打印数据时，head 会重新指向下一个节点，直到 head 为 None 为止。因此，完成输出后，实际上会从链表中删除所有节点。对于程序来说，这些被删除的节点会在下一次垃圾回收的时候被回收。
head = None
for count in range(1, 6):
head = Node(count, head)
while head is not None:
print(head)
head = head.next
3.4 单链表结构的操作
几乎数组上的所有操作都是基于索引的，并且索引是数组结构中不可或缺的部分。但是，在链表结构中，程序员必须通过操作结构中的链表来模拟基于索引的操作。
a. 遍历
遍历(traversal)在时间上是线性的，并且不需要额外的内存。
head = None
for count in range(3, 0, -1):
head = Node(count, head)
probe = head
while probe is not None:
# <use or modify probe.data >
print(probe)
probe = probe.next
遍历过程如下图所示：
b. 搜索和访问
顺序搜索和遍历类似，平均情况下对单链表结构的顺序搜索也是线性的。
head = None
for count in range(3, 0, -1):
head = Node(count, head)
# targetItem是被查找的目标项
probe = head
while probe is not None and targetItem != probe.data:
probe = probe.next
if probe is not None:
# <targetItem has been found>
else:
# <targetItem is not in the linked structure>
和数组不同，链表结构不支持随机访问。因此，访问链表结构中的某一项，也是一次顺序搜索操作，如下是访问第 i 项的代码：
# 假定 0 <= index < n, index是目标索引项
probe = head
while index > 0:
probe = probe.next
index -= 1
return probe.data
c. 替换
以下两种替换操作在平均情况下都是线性的。
在单链表结构中，替换给定项的操作需要利用搜索操作：
head = None
for count in range(3, 0, -1):
head = Node(count, head)
# targetItem是被替换的目标项
probe = head
while probe is not None and targetItem != probe.data:
probe = probe.next
if probe is not None:
probe.data = newItem # 替换目标项的数据
return True
else:
return False
替换给索引位置的操作需要利用访问操作：
# 假定 0 <= index < n, index是目标索引项
probe = head
while index > 0:
probe = probe.next
index -= 1
probe.data = newItem # 替换目标索引位置的数据
d. 在开始处插入
在一个链表结构的开始处插入项时，可分为以下两种情况：
- 第一种情况下，head 的初始状态就是
None，将 head 设置为新节点即可。 - 第二种情况下，不需要像数组那样复制并移动数据，也不需要额外的内存。
所以，在一个链表结构的开始处插入数据时，时间和内存都是常数，这与数组的操作过程截然不同。
e. 在末尾处插入
在一个数组的末尾插入一项时，需要的时间和内存都是常数，除非必须调整数组的大小。 在单链表结构的末尾插入时，需考虑以下两种情况：
- 第一种情况，head 的初始状态就是
None，将 head 设置为新节点即可。 - 第二种情况，当 head 初始状态不为
None时，需要先遍历链表以获取链表的最后一个节点，然后再进行插入。该操作在时间上是线性的，在空间上是常数。
newNode = Node(newItem)
if head is None:
head = newNode
else:
probe = head
while probe.next != None:
probe = probe.next
probe.next = newNode
下图展示了在拥有 3 项元素的一个链表末尾插入新项的过程：
f. 从开始处删除
该操作的使用的时间和内存都是常数，和数组上的相同操作有明显区别。
# Assumes at least one node in the structure
removedItem = head.data
head = head.next
return removedItem
下图记录了删除过程：
g. 从末尾处删除
从一个数组的末尾删除一项时，需要的时间和内存都是常数，除非必须调整数组的大小。 假设单链表中至少存在一个节点，从链表中删除最后一个节点时需要考虑以下两种情况：
- 第一种情况，只有一个节点，直接将 head 指针设置为
None即可 - 第二种情况，至少存在两个节点时，需要先找到倒数第二个节点，并将其
next指针设置为None。
# Assumes at least one node in structure
removedItem = head.data
if head.next is None:
head = None
else:
probe = head
while probe.next.next != None:# 找到倒数第二项
probe = probe.next
removedItem = probe.next.data
probe.next = None
return removedItem
下图展示了从拥有 3 个项的链表结构中删除最后一项的过程：
h. 在任何位置插入
在数组的第 i 个索引位置插入一项时，需要先将从索引 i 到 n-1 的项都向后移动。 在链表的第 i 个索引位置插入项时，需要先找到第 i-1 (如果 i) 或 n-1 (如果 i>=n)的索引位置，然后插入一个节点。和遍历操作一样，该操作的性能也是线性的，但使用的内存数是常数。
if head is None or index <= 0:
head = Node(newItem, head)
else:
# Search for node at position index - 1 or the last position
probe = head
j = 0
while j <= index-2 and probe.next != None:
probe = probe.next
j += 1
# Insert new node after node at position index - 1
# or last position
probe.next = Node(newItem, probe.next)
下图展示了在包含 3 个项的链表结构中，在第 2 个索引位置插入一项的过程：
在目标项之前插入一项：
if head is not None:
if head.next is None and\
targetItem == head.data:
# 链表中仅有一个元素，且该元素等于目标项
head = Node(newItem, head)
else:
probe = head
while probe.next is not None and\
targetItem != probe.next.data:
probe = probe.next
if probe.next is not None:
probe.next = Node(newItem, probe.next)
else:
# 不存在目标项时的操作
i. 从任意位置删除
从一个链表结构中删除索引值是 i 的项，存在以下三种情况：
- i<=0 ，直接删除索引为 0 的节点
- 0 ，找到索引为 i-1 的节点，然后删除其后的节点
- i>=n ，直接删除最后一个节点
# 假设链表结构中至少包含一个节点
if index <= 0 or head.next is None
removedItem = head.data
head = head.next
return removedItem # 返回被删除的节点
else:
# Search for node at position index - 1 or
# the next to last position
probe = head
while index > 1 and probe.next.next != None:
probe = probe.next
index -= 1
removedItem = probe.next.data
probe.next = probe.next.next
return removedIte
下图展示了从包含 4 个节点链表结构中删除索引为 2 的节点的过程：
3.5 复杂度分析
下表给出了单链表各种操作的运行时间：
| 操作 | 运行时间 |
|---|---|
| 访问第 i 个位置的元素 | O(n)，平均情况 |
| 替换第 i 个位置的元素 | O(n)，平均情况 |
| 在开始处插入 | O(1)，最好情况和最坏情况 |
| 从开始处删除 | O(1)，最好情况和最坏情况 |
| 在第 i 个位置插入 | O(n)，平均情况 |
| 从第 i 个位置删除 | O(n)，平均情况 |
单链表只有两个操作在时间上不是线性的。单链表结构相较数组的主要优点并不是时间性能，而是内存性能。当必须调整数组的尺寸时，其时间和内存都是线性的。当调整链表结构的尺寸时(插入或删除操作都会伴随链表尺寸的改变)，其时间和内存都是常数。因为链表结构的物理尺寸和逻辑尺寸相等，所有在链表结构中没有浪费内存的问题。链表结构有一个额外的内存代价，因为单链表结构必须要为指针使用 n 个内存单元。这种代价在双链表结构中还会翻倍，因为双链表的节点有两个链接。
3.6 链表的变体
a. 包含哑头结点的循环链表结构
对于单链表结构，在其开始处插入(删除)节点的操作，其实是在任意位置插入(删除)节点的特殊情况——特殊之处在于 head 引用需要被改变。如果使用带哑头节点(Dummy Header Node)的循环链表结构，便可避免这种特殊性，从而在任何情况下都无需改变 head 引用的对象。
首先，循环链表结构的最后一个节点的链接总会引用第一个节点；其次，这个实现中第一个节点始终是哑头节点——哑头节点不包含数据，用于充当链表结构中开头和结尾的一个标志——并且 head 始终会引用哑头节点。在该实现的空链表结构中，哑头节点的链接会引用哑头节点自身。空链表结构如下：
head = Node(None, None)
head.next = head
示意图如下：
本实现的数据节点位于哑头节点之后，并且最后一个数据节点的链接需要引用哑头节点。另外，数据节点的索引依然从 0 开始。下图展示了包含一个数据节点的实现：
执行在任意索引位置插入节点的操作时，本实现的代码如下：
# Search for node at position index - 1 or the last position
probe = head
j = 0
while j+1 <= index and probe.next != head:
probe = probe.next
j += 1
# Insert new node after node at position index - 1 or
# last position
probe.next = Node(newItem, probe.next)
可见，本实现的优点在于插入(删除)操作都只需要考虑一种情况。
b. 双链表结构
由于双链表包含两个方向的链接，因此可获取当前项的前驱项和后继项。由于尾链接(tail link)的存在，使得用户可以直接访问最后一个节点。
通过扩展之前的 Node 类，便可实现双链表结构的节点类：
class Node(object):
def __init__(self, data, next = None):
"""Instantiates a Node with default next of None"""
self.data = data
self.next = next
class TwoWayNode(Node):
def __init__(self, data, previous = None, next = None):
"""Instantiates a TwoWayNode."""
Node.__init__(self, data, next)
self.previous = previous
构建双链表的代码如下：
"""File: testtwowaynode.py
Tests the TwoWayNode class.
"""
from node import TwoWayNode
# Create a doubly linked structure with one node
head = TwoWayNode(1)
tail = head
# Add four nodes to the end of the doubly linked structure
for data in range(2, 6):
# 通过尾链接添加节点，同时会修改尾连接的引用。
# 前提是链表非空，并且tail始终引用链表的最后一个节点。
tail.next = TwoWayNode(data, tail)
tail = tail.next
# Print the contents of the linked structure in reverse order
probe = tail
while probe != None:
print(probe.data)
probe = probe.previous
下图展示了在双链表结构的末尾插入一个新节点的过程：
双链表结构较为通用的插入和删除操作也存在两种情况，这点与单链表的操作相同，可以通过借助带有哑头节点的循环链表来简化插入和删除操作。
除了在尾部插入和删除的操作，双链表结构其余操作的时间复杂度与单链表的对应操作相同。不过，双链表结构中额外的指针，需要一个额外的。线性的内存使用量。
