数据结构/列表结构

数据结构
简介 - 渐进符号 - 数组 - 列表结构 & 迭代器
 栈 & 队列 - 树 - 最小 & 最大堆 - 图
 哈希表 - 集合 - 权衡

列表结构和迭代器

我们现在已经看到了两种不同的数据结构，它们允许我们存储元素的有序序列。但是，它们有两种截然不同的接口。数组允许我们使用get-element() 和 set-element() 函数来访问和更改元素。节点链要求我们使用get-next() 直到找到所需的节点，然后我们可以使用get-value() 和 set-value() 来访问和修改其值。现在，如果您已经编写了一些代码，并且意识到您应该使用另一个序列数据结构？您必须浏览已经编写的所有代码，并将一组访问器函数更改为另一组。太麻烦了！幸运的是，有一种方法可以将此更改局部化到一个地方：通过使用列表抽象数据类型（ADT）。

List<item-type> ADT

get-begin():List Iterator<item-type>: 返回表示列表第一个元素的列表迭代器（我们很快就会定义它）。在 $O(1)$ 时间内运行。
get-end():List Iterator<item-type>: 返回表示列表最后一个元素之后的元素的列表迭代器。在 $O(1)$ 时间内运行。
prepend(new-item:item-type): 在列表开头添加一个新元素。在 $O(1)$ 时间内运行。
insert-after(iter:List Iterator<item-type>, new-item:item-type): 在iter之后立即添加一个新元素。在 $O(N)$ 时间内运行。
remove-first(): 移除列表开头的元素。在 $O(1)$ 时间内运行。
remove-after(iter:List Iterator<item-type>): 移除iter之后立即的元素。在 $O(N)$ 时间内运行。
is-empty():Boolean: 如果列表中没有元素，则为真。具有默认实现。在 $O(1)$ 时间内运行。
get-size():Integer: 返回列表中的元素数量。具有默认实现。在 $O(N)$ 时间内运行。
get-nth(n:Integer):item-type: 返回列表中的第 n 个元素，从 0 开始计数。具有默认实现。在 $O(N)$ 时间内运行。
set-nth(n:Integer, new-value:item-type): 将列表中的第 n 个元素（从 0 开始计数）分配一个新值。具有默认实现。在 $O(N)$ 时间内运行。

迭代器是另一种抽象，它封装了对单个元素的访问以及在列表中的增量移动。它的接口与介绍中介绍的节点接口非常相似，但由于它是一个抽象类型，不同的列表可以以不同的方式实现它。

List Iterator<item-type> ADT

get-value():item-type: 返回此迭代器所引用的列表元素的值。
set-value(new-value:item-type): 将此迭代器所引用的列表元素分配一个新值。
move-next(): 使此迭代器引用列表中的下一个元素。
equal(other-iter:List Iterator<item-type>):Boolean: 如果另一个迭代器引用与此迭代器相同的列表元素，则为真。

所有操作都在 $O(1)$ 时间内运行。

List ADT 的定义中还有其他几个方面需要进一步解释。首先，请注意 get-end() 操作返回一个位于列表“末尾之外”的迭代器。这使得它的实现稍微棘手一些，但允许您编写类似于以下的循环

var iter:List Iterator := list.get-begin()
while(not iter.equal(list.get-end()))
 # Do stuff with the iterator
 iter.move-next()
end while

其次，每个操作都给出了最坏情况下的运行时间。任何 List ADT 的实现都保证能够至少以这种速度运行此操作。大多数实现将以更快的速度运行大多数操作。例如，List 的节点链实现可以在 $O(1)$ 内运行 insert-after()。

第三，一些操作表明它们具有默认实现。这意味着这些操作可以用其他更原始的操作来实现。它们被包含在 ADT 中，以便某些实现可以更快地实现它们。例如，get-nth() 的默认实现运行在 $O(N)$ 内，因为它必须遍历所有元素才能到达第 n 个元素。但是，List 的数组实现可以使用它的 get-element() 操作在 $O(1)$ 内实现它。其他默认实现是

abstract type List<item-type>
 method is-empty()
  return get-begin().equal(get-end())
 end method

 method get-size():Integer
  var size:Integer := 0
  var iter:List Iterator<item-type> := get-begin()
  while(not iter.equal(get-end()))
   size := size+1
   iter.move-next()
  end while
  return size
 end method

 helper method find-nth(n:Integer):List Iterator<item-type>
  if n >= get-size()
   error "The index is past the end of the list"
  end if
  var iter:List Iterator<item-type> := get-begin()
  while(n > 0)
   iter.move-next()
   n := n-1
  end while
  return iter
 end method

 method get-nth(n:Integer):item-type
  return find-nth(n).get-value()
 end method

 method set-nth(n:Integer, new-value:item-type)
  find-nth(n).set-value(new-value)
 end method
end type

语法糖

在这本书中，我们偶尔会介绍一些缩写，使我们能够编写更少的伪代码，并使您更容易阅读。现在，我们将介绍一种更简单的方法来比较迭代器，以及一种专门用于遍历序列的循环。

我们不会使用 equal() 方法来比较迭代器，而是会重载 == 操作符。更准确地说，以下两个表达式是等效的

iter1.equal(iter2)
iter1 == iter2

其次，我们将使用 for 关键字来表示列表遍历。以下两个代码块是等效的

var iter:List Iterator<item-type> := list.get-begin()
while(not iter == list.get-end())
 operations on iter
 iter.move-next()
end while

for iter in list
 operations on iter
end for

实现

为了实际使用 List ADT，我们需要编写一个具体的数据类型来实现它的接口。有两种标准数据类型自然地实现了 List：在引言中描述的节点链，通常称为单链表；以及数组类型的扩展，称为向量，它会自动调整自身大小以适应插入的节点。

单链表

type Singly Linked List<item-type> implements List<item-type>

head 指向列表中的第一个节点。当它为 null 时，列表为空。

  data head:Node<item-type>

最初，列表为空。

  constructor()
    head := null
  end constructor

  method get-begin():Sll Iterator<item-type>
    return new Sll-Iterator(head)
  end method

“末尾之外”的迭代器只是一个空节点。要了解原因，请考虑当您拥有指向列表中最后一个元素的迭代器并调用 move-next() 时会发生什么。

  method get-end():Sll Iterator<item-type>
    return new Sll-Iterator(null)
  end method

  method prepend(new-item:item-type)
    head = make-node(new-item, head)
  end method

  method insert-after(iter:Sll Iterator<item-type>, new-item:item-type)
    var new-node:Node<item-type> := make-node(new-item, iter.node().get-next())
    iter.node.set-next(new-node)
  end method

  method remove-first()
    head = head.get-next()
  end method

这将迭代器持有的节点指向后面两个节点的节点。

  method remove-after(iter:Sll Iterator<item-type>)
    iter.node.set-next(iter.node.get-next().get-next())
  end method
end type

如果我们希望 get-size() 成为一个 $O(1)$ 操作，我们可以添加一个 Integer 数据成员，始终跟踪列表的大小。否则，默认的 $O(N)$ 实现也能正常工作。

单链表的迭代器只是一个指向节点的引用。

type Sll Iterator<item-type>
  data node:Node<item-type>

  constructor(_node:Node<item-type>)
    node := _node
  end constructor

大多数操作只是将请求传递给节点。

  method get-value():item-type
    return node.get-value()
  end method

  method set-value(new-value:item-type)
    node.set-value(new-value)
  end method

  method move-next()
    node := node.get-next()
  end method

对于相等性测试，我们假设底层系统知道如何比较节点的相等性。在几乎所有语言中，这都是一个指针比较。

  method equal(other-iter:List Iterator<item-type>):Boolean
    return node == other-iter.node
  end method
end type

向量

让我们先编写向量的迭代器。这将使向量的实现更加清晰。

type Vector Iterator<item-type>
  data array:Array<item-type>
  data index:Integer

  constructor(my_array:Array<item-type>, my_index:Integer)
    array := my_array
    index := my_index
  end constructor

  method get-value():item-type
    return array.get-element(index)
  end method

  method set-value(new-value:item-type)
    array.set-element(index, new-value)
  end method

  method move-next()
    index := index+1
  end method

  method equal(other-iter:List Iterator<item-type>):Boolean
    return array==other-iter.array and index==other-iter.index
  end method
end type

我们用原始的 Array 数据类型来实现向量。始终保持数组大小完全正确效率低下（想想您需要进行多少次调整大小），因此我们同时存储 size（向量中的逻辑元素数量）和 capacity（数组中的空间数量）。数组的有效索引将始终从 0 到 capacity-1。

type Vector<item-type>
  data array:Array<item-type>
  data size:Integer
  data capacity:Integer

我们用容量为 10 来初始化向量。选择 10 是相当随意的。如果我们想要让它看起来不那么随意，我们会选择 2 的幂，而像你这样的天真读者会认为选择这种方式有一定的深层二进制原因。

  constructor()
    array := create-array(0, 9)
    size := 0
    capacity := 10
  end constructor

  method get-begin():Vector-Iterator<item-type>
    return new Vector-Iterator(array, 0)
  end method

结束迭代器的索引为 size。这比最高的有效索引多 1。

  method get-end():List Iterator<item-type>
    return new Vector-Iterator(array, size)
  end method

我们将使用此方法来帮助我们实现插入例程。在调用它之后，数组的 capacity 将保证至少为 new-capacity。一个简单的实现将只分配一个具有 new-capacity 个元素的全新数组，并将旧数组复制过来。要了解这为什么效率低下，请考虑如果我们在循环中开始追加元素会发生什么。一旦我们超过了原始容量，每个新元素都需要我们复制整个数组。这就是为什么此实现每当需要增长时至少将底层数组的大小加倍的原因。

  helper method ensure-capacity(new-capacity:Integer)

如果当前容量已经足够大，则快速返回。

    if capacity >= new-capacity
      return
    end if

现在，找到我们需要的新的容量，

    var allocated-capacity:Integer := max(capacity*2, new-capacity)
    var new-array:Array<item-type> := create-array(0, allocated-capacity - 1)

将旧数组复制过来，

    for i in 0..size-1
      new-array.set-element(i, array.get-element(i))
    end for

并更新向量的状态。

    array := new-array
    capacity := allocated-capacity
  end method

此方法使用了一个通常是非法的迭代器（它指向向量开头之前的项目）来欺骗 insert-after() 做正确的事情。通过这样做，我们避免了代码重复。

  method prepend(new-item:item-type)
    insert-after(new Vector-Iterator(array, -1), new-item)
  end method

insert-after() 需要复制 iter 和向量末尾之间的所有元素。这意味着它通常在 $O(N)$ 时间内运行。但是，在 iter 指向向量中最后一个元素的特殊情况下，我们不需要复制任何元素来为新元素腾出空间。追加操作可以在 $O(1)$ 时间内运行，加上 ensure-capacity() 调用所需的时间。ensure-capacity() 有时需要复制整个数组，这需要 $O(N)$ 时间。但更常见的情况是，它根本不需要做任何事情。

摊还分析
事实上，如果你考虑一系列追加操作，这些操作从ensure-capacity()增加 Vector 容量（这里将容量称为 $C$ ）之后立即开始，并在容量下次增加之前立即结束，你会发现将会有恰好 ${\frac {C}{2}}=O(C)$ 次追加。在容量下次增加时，它将需要将 $C$ 个元素复制到新的数组中。所以这整个序列的 ${\frac {C}{2}}$ 次函数调用共进行了 ${\frac {3C}{2}}=O(C)$ 次操作。我们将这种情况下，对于 $O(N)$ 次函数调用有 $O(N)$ 次操作的情况称为“摊还 $O(1)$ 时间”。

  method insert-after(iter:Vector Iterator<item-type>, new-item:item-type)
    ensure-capacity(size+1)

这个循环将向量中的所有元素复制到向上一个索引的位置。我们向后循环是为了在复制每个后续元素之前为其腾出空间。

    for i in size-1 .. iter.index+1 step -1
      array.set-element(i+1, array.get-element(i))
    end for

现在数组中间有一个空位，我们可以将新元素放在那里。

    array.set-element(iter.index+1, new-item)

并更新向量的 size。

    size := size+1
  end method

同样，使用了一些技巧来避免重复代码。

  method remove-first()
   remove-after(new Vector-Iterator(array, -1))
  end method

与insert-after()类似，remove-after 需要复制iter和向量末尾之间的所有元素。所以一般情况下，它的运行时间为 $O(N)$ 。但在iter指向向量中最后一个元素的特殊情况下，我们可以简单地将向量的 size 减 1，而不必复制任何元素。remove-last 操作的运行时间为 $O(1)$ 。

  method remove-after(iter:List Iterator<item-type>)
    for i in iter.index+1 .. size-2
      array.set-element(i, array.get-element(i+1))
    end for
    size := size-1
  end method

此方法有一个默认实现，但我们已经存储了 size，因此我们可以用 $O(1)$ 的时间来实现，而不是默认实现的 $O(N).$

  method get-size():Integer
    return size
  end method

因为数组允许对元素进行常数时间访问，所以我们可以用 $O(1)$ 的时间来实现get-和set-nth()，而不是默认实现的 $O(N)$

  method get-nth(n:Integer):item-type
    return array.get-element(n)
  end method

  method set-nth(n:Integer, new-value:item-type)
    array.set-element(n, new-value)
  end method
end type

双向列表

待办事项
这部分内容过于简略。应该在以后进行补充。

有时我们希望Data Structures/List Structures也能在列表中向后移动。双向列表允许列表向前和向后搜索。双向列表实现了一个额外的迭代器函数，move-previous()。

Bidirectional List<item-type> ADT

get-begin():Bidirectional List Iterator<item-type>: 返回表示列表第一个元素的列表迭代器（我们很快就会定义它）。在 $O(1)$ 时间内运行。
get-end():Bidirectional List Iterator<item-type>: 返回表示列表最后一个元素之后的元素的列表迭代器。在 $O(1)$ 时间内运行。
insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type): 在iter之前添加一个新元素。运行时间为 $O(N)$ 。
remove(iter:Bidirectional List Iterator<item-type>): 移除iter指向的元素。调用此函数后，iter将指向列表中的下一个元素。运行时间为 $O(N)$ 。
is-empty():Boolean: 如果列表中没有元素，则返回真。有一个默认实现。运行时间为 $O(1)$ 。
get-size():Integer: 返回列表中的元素数量。具有默认实现。在 $O(N)$ 时间内运行。
get-nth(n:Integer):item-type: 返回列表中的第 n 个元素，从 0 开始计数。具有默认实现。在 $O(N)$ 时间内运行。
set-nth(n:Integer, new-value:item-type): 将列表中的第 n 个元素（从 0 开始计数）分配一个新值。具有默认实现。在 $O(N)$ 时间内运行。

Bidirectional List Iterator<item-type> ADT

get-value():item-type: 返回此迭代器指向的列表元素的值。如果迭代器指向列表末尾，则未定义。
set-value(new-value:item-type): 为此迭代器指向的列表元素分配一个新值。如果迭代器指向列表末尾，则未定义。
move-next(): 使此迭代器指向列表中的下一个元素。如果迭代器指向列表末尾，则未定义。
move-previous(): 使此迭代器指向列表中的上一个元素。如果迭代器指向列表中的第一个元素，则未定义。
equal(other-iter:List Iterator<item-type>):Boolean: 如果另一个迭代器指向与此迭代器相同的列表元素，则返回真。

所有操作都在 $O(1)$ 时间内运行。

双向链表实现

待办事项
解释一下：它是链表的一部分，可以显示链表之间的连接。

向量实现

我们已经见过的向量有一个完全足够好的实现来作为双向链表。我们所需要做的就是向它及其迭代器添加额外的成员函数；旧的函数不需要改变。

type Vector<item-type>
  ... # already-existing data and methods

根据原始的insert-after()方法实现它。在它运行之后，我们必须调整iter的索引，以便它仍然指向相同的元素。

  method insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type)
    insert-after(new Vector-Iterator(iter.array, iter.index-1))
    iter.move-next()
  end method

同样，根据旧函数实现它。在remove-after()运行之后，索引将已经是正确的。

  method remove(iter:Bidirectional List Iterator<item-type>)
    remove-after(new Vector-Iterator(iter.array, iter.index-1))
  end method
end type

权衡

待办事项
将以下有用的信息重构到上面

following outline from talk page:
 Common list operations & example
   set(pos, val), get(pos), remove(pos), append(val)
     [Perhaps discuss operations on Nodes, versus operations on the List
     itself: example, Nodes have a next operation, but the List itself has
     a pointer to the head and tail node, and an integer for the number of
     elements. This view would work well in both the Lisp and OO worlds.]
 Doubley linked list
 Vectors (resizeable arrays)

为了选择适合工作的正确数据结构，我们需要对将要对数据进行的操作有一定的了解。

我们是否知道在任何时候都不会超过 100 个数据，或者我们需要偶尔处理千兆字节的数据？
我们如何读取数据？始终按时间顺序？始终按名称排序？随机访问记录编号？
我们总是将数据添加到末尾或开头？还是我们会在中间进行大量的插入和删除？

我们必须在各种要求之间取得平衡。如果我们需要以 3 种不同的方式频繁地读取数据，请选择一种允许我们以不太慢的速度执行所有 3 种操作的数据结构。不要选择一些对于*一种*方式来说速度慢得无法忍受的数据结构，无论它对于其他方式来说有多快。

通常，对于某些任务来说，最短、最简单的编程解决方案将使用线性（一维）数组。

如果我们将数据保留为 ADT，这将使我们更容易暂时切换到其他底层数据结构，并客观地衡量它是否更快或更慢。

优点/缺点

在大多数情况下，数组的优点是链表的缺点，反之亦然。

数组的优点（与链表相比）

索引 - 对数组中任何元素的索引访问速度很快；链表必须从开头遍历才能到达所需的元素。
更快 - 通常情况下，访问数组中的元素比访问链表中的元素更快。

链表的优点（与数组相比）

调整大小 - 链表可以轻松地通过添加元素来调整大小，而不会影响列表中的其他元素；数组只能通过分配新的内存块并复制所有元素来扩大。
插入 - 可以轻松地将元素插入链表的中间：创建一个新的链接，该链接指向它后面的链接，然后将前面的链接指向新的链接。

旁注：- 如何在数组的中间插入元素。如果数组未满，您将获取数组中要插入位置或索引之后的所有元素，并将它们向前移动 1 个位置，然后插入您的元素。如果数组已满并且您要插入元素，您将不得不从某种意义上“调整数组的大小”。必须创建一个比原始数组大一个大小的新数组以插入您的元素，然后将原始数组的所有元素复制到新数组，同时考虑插入元素的位置或索引，然后插入您的元素。

数据结构
简介 - 渐进符号 - 数组 - 列表结构 & 迭代器
 栈 & 队列 - 树 - 最小 & 最大堆 - 图
 哈希表 - 集合 - 权衡