4.md

# 第四章 序列和树的实现

> 译者：[biubiubiuboomboomboom](https://github.com/biubiubiuboomboomboom)

在第二和第三章我们看见了相当一部分关于List接口以及框架的实现。
现在，我们回顾一下这些接口的标准化表示（具体实现）并观察一些特殊队列的接口及其实现。


## 4.1   用数组实现List接口

  很多“生产式”的程序语言都内置了一些数据结构，比如Java的数组 --- 一种以整数作为索引的、随机访问变量的队列。数组这种数据结构有两个主要的性能优势。
首先，它是一种紧凑的(节省空间的)变量序列，通常只占用比组成变量本身更小的空间。其次，在访问序列中的变量时，随机访问的速度非常快，时间复杂度只有常数级别。其主要的缺点是在改变序列大小时，速度会变的很慢(在最坏的情况下)。不过，只要稍微注意一下，我们就能发现其实最后分摊在数组支持的列表上的操作开销都是固定的。
  一种Java内置的数组类型是 java.util.ArrayList （部分的实现如图4.11 所示）。你可以使用他的构造函数去创建一个新的 ArrayList 并且选择它的初始大小。然后你可以使用add方法去添加对象，并将根据你的需要去扩张数组。我能对关于 ArrayList 的操作代价说什么呢？显然，读取和扩容的复杂度都是 θ（1）；有趣的一点是，如你所见， ArrayList 的容量永远是正的。add方法在数组需要根据数据进行展开时会调用 ensureCapacity 方法实现，使得 ArrayList 的容量在需要扩张时加倍。让我们一起来看看选择这种设计背后的原因吧。我们只考虑在调用 A.add(x) 即 A.add(A.size(),x) 的情况。
  假设我们替换掉原有的长度
  ```
      if (count + 1 > data.length)
        ensureCapacity (data.length * 2);
  ```
  并选择最小的扩张
  ```
      ensureCapacity (count+1);
  ```
  这种情况下，当初始的数组容量用完时，每个 add 操作都将展开数组的数据。

让我们来测量向数组元素添加多个值的开销。在Java中,我们可以用新对象[K]来代替Θ(K)来表示开销。当我们为了增加开销而将前一个数组元素复制到现有数组中时，(使用System.arraycopy)，这也不会改变。因此，在最坏情况下的开销 Ci 取决于 A.add(x) ,我们可以用一个简单的增量表达式来概括：
Ci(K,M)={ α1, if M>k; α2（K+1）,if K=M  , 上式中K的值为A.size()， M >= K，其表示的是 A 当前的数据量（即 A.data.length） 且 αi 是一个恒定的量。
所以，我们可以保守的说 C(K, M, I)∈Θ(K).
  现在让我们考虑实现的成本Cd，如图4.1所示，当必须增加容量时，我们总是将容量加倍。即 Cd(K, M) ={α1,ifM > K;α3(2K+ 1),ifM=K 。 最坏情况下的成本看起来是一样的;大小增加2的因子只是改变了常数因子，我们仍然可以使用与之前相同的公式:Cd(K, M)∈O(K)。
  所以从这个最坏情况的角度来看,似乎这两个策略有相同的成本。然而，我们应该保持怀疑。我们采用每次扩容大小只加1的策略。应该考虑的是整个序列的add操作，而不是仅仅考虑单个的操作情况。相比之下，使用双倍大小策略，随着数组的增长，我们的扩展越来越少，因此大多数添加调用都在固定的时间内完成。那么，把它们描述成时间与k成正比真的准确吗?
  考虑对a .add(x)的一系列N个调用，从一个初始容量为M0< N的空ArrayList开始，采用按1递增的策略，调用号M0(从0开始编号)、M0+1、M0+2...的花费分别与M0+1、M0+2的时间成比例… 因此，从初始大小为M0的空列表开始的N个> M0操作的总成本Cincr为 Cincr∈Θ(M0+M0+ 1 +. . .+N)=  Θ((N+M0)·N/2)=  Θ(N2)  其中M0为固定值。
换句话说，成本在增加的项目数量上是二次的。
  现在考虑加倍策略。我们将分析其使用的潜在函数，从第1章第4小节中展示的数据中选择一个常数作为 ai，取一个花费为均值的操作 i,再找一个合适的潜在的 Φ ，Φ>0。则有: ai=ci+ Φi+1−Φi , 其中 ci 表示 第 ith 个加法操作的实际开销。 在这种情况下，一个潜在的表达式是 Φi= 4i−2Si+ 2S0 ,Si 表示的是在第 ith 个操作之前数组的容量。在第一次扩容后，我们总是能得到 2i >= Si ,所以对于所有的 i 总有  Φi≥0。
  我们可以取数组中第i个加法之前的项数为i，假设我们从0开始进行加法。第i次加法的实际成本ci，如果i < Si，则为1个时间单位，否则(当i=Si时)分配一个多倍数组、复制所有现有项，然后再添加一个的成本，我们可以将其作为2Si时间单位(当然要选择合适的“时间单位”)。因此，在当 i < Si 时, 我们得到：
  ai=ci+ Φi+1−Φi=  1 + 4(i+ 1)−2Si+1+ 2S0−(4i−2Si+ 2S0)=  1 + 4(i+ 1)−2Si+ 2S0−(4i−2Si+ 2S0)=  4
  在 i =Si 时 我们可以得到 ：
    ai=ci+ Φi+1−Φi=  2Si+ 4(i+ 1)−2Si+1+ 2S0−(4i−2Si+ 2S0)=  2Si+ 4(i+ 1)−4Si+ 2S0−(4i−2Si+ 2S0)=  4
    所以ai= 4，证明在加倍策略下数组末尾相加的平摊代价确实是常数。
  
  
##  4.2 链表结构
   “链式结构”一词通常指的是组合的、动态增长的数据结构，其中包含用于通过指针(链接)连接在一起的各个成员的小对象。
    
###   4.2.1 单向链表
   抽象语言有一个普遍存在的复合数据结构，即序对(pair)或首尾结构(cons cell)，它可以表示任何可以想象的数据结构。也许它最常见的用途是表示事物列表，如图4.2a所示。每一对由两个容器组成，其中一个容器用于存储指向数据项的指针，另一个容器用于存储指向列表中下一对的指针，即末尾的空指针。在Java中，一个大致相当于pair的类如下:
```
    class Entry{
          Entry (Object head , Entry next){
               this.head = head;
               this.next = next;
          }
          Object head;
          Entry next;
    }
```    
   我们调用由这样一对单链结形成的列表，因为每一对都携带一个指向另一对的指针(链接)。
   改变链表(它的一组容器)的结构涉及到俗称的“指针摆动”。图4.2回顾了作为列表使用的对的插入和删除的基本操作。
    
###   4.2.2  哨兵
   如图4.2所示，链表在开头插入或删除的过程与在中间插入或删除的过程不同，因为它是变量L，而不是改变的下一个字段:
```
    L= L.next // 删除 L 指向的链表的首项
    L= new Entry ("aardvark", L); // 在链表首部增加一项
```
  我们可以使用一种称为哨兵节点的聪明技巧，避免对列表开头的特殊情况使用这种方法。
  标记背后的思想是使用一个额外的对象，一个不携带存储的集合项之一的对象，以避免出现任何特殊情况。图4.3演示了结果。
  哨兵的使用改变了一些测试。例如，测试是否链表L在没有标记的情况下为空只是简单地将L与null进行比较，其中使用标记的列表的测试将L.next与null进行比较。
    
### 4.2.3   双向链表
    
   单链表易于创建和操作，但是对于完全实现Java List接口来说，单链表并不理想。一个明显的问题是，前面对列表迭代器的操作没有在单链接结构上快速实现。另一个问题则是指针在迭代时会被迫返回到列表的开始，然后跟随适当数量的next字段，几乎不会直接完全返回到当前位置，这需要与列表大小成比例的时间。在列表迭代器上的remove操作的实现中出现了一些更细微的麻烦。要从单链表中删除项目p，您需要一个指向p之前项目的指针，因为它是必须修改的对象的下一个字段。
    
   通过向列表结构中的对象添加一个前辈链接，使列表中给定项的前项和后项具有同等的可访问性，这两个问题都很容易解决。与单链结构一样，前端和端哨兵的使用进一步简化了操作，消除了从链表的首或尾添加或删除的特殊情况。在双向链结构的情况下，另一种方法是使整个列表循环，即在列表的前面和后面都使用一个标记。这个可爱的技巧节省了少量的空间，否则将会浪费首节点的哨兵和尾部的下一节点指针。图4.4说明了结果表示及其上的主要操作。
    
## 4.2.4 列表接口中链表的实现
    
   双重链接结构支持实现Java List接口所需的所有操作。链接的类型(LinkedList.Entry)对实现是私有的。链表对象本身只包含一个指向链表标记的指针(一旦创建，它就不会更改)和一个包含链表中项数的整数变量。当然，从技术上讲，后一种方法是多余的，因为总可以计算列表中的项数，但是保持这种可变性可以使得列表的大小是一个常量时间的操作。图4.5演示了所涉及的三个主要数据结构:LinkedList、LinkedList.Entry，以及迭代器LinkedList.LinkedIter。
    
    
    
## 4.2.5 特殊列表
   列表的一个常见用途是表示只在一端或两端操作和检查的项目序列。其中，最熟悉的是：
      1、栈 （或者是先进后出的队列） ，只支持在首或尾的一端增加或删除。
      2、队列 （或者是先进后出的队列），只支持在一端添加或在另一端删除。
      3、有两个端点的队列，只支持在两端进行插入和删除。
    图4.8中展示了他们的操作。

##   4.3  栈
   Java提供了Java.util类型。作为java.util.Vector类型的扩展(本身是ArrayList的一种变体)：
```
      package java.util;
      public class Stack<T> extends Vector<T>{
        /** An empty Stack */
        public Stack(){}
        public boolean empty(){ return isEmpty();}
        public T peek (){ check(); return get(size()-1);}
        public T pop (){ check(); return remove(size()-1);}
        public T push (T x){add(x);return x;}
        public int search (Object x){ 
          int r = lastIndexOf(x);
          return r == -1? -1:size()-r;
        }
        private void check(){
          if(empty()) throw new EmptyStackException();
        }
      }
```    
   但是，因为它是库中较老的类型之一。java.util.Stack并不那么完美。特别是，没有单独的接口描述“堆栈性”。相反，只有Stack类，它不可避免地结合了接口和实现。图4.9显示了如何设计堆栈接口(在Java意义上) 
    堆栈有许多用途，部分原因是它们与递归和回溯搜索关系密切。例如，考虑一个寻找迷宫出口的简单策略。我们假设某个Maze类，以及一个表示迷宫中某个位置的Position类。在迷宫中的任何位置，你都可以向四个不同的方向移动(用数字0-4表示，可能代表罗盘指向北、东、南和西)。我们的想法是把面包屑放在我们已经去过的每个地方。从我们参观的每一个地方，我们试着走每一个可能的方向，并从那个点继续。如果我们发现我们已经访问过一个职位，或者从某个职位出发没有偏离方向，我们就会回溯到我们之前访问过的最后一个职位，并继续从之前的职位开始我们还没有尝试过的方向，当我们到达出口时停止(参见图4.10)。作为一个程序(使用我希望具有启发性的方法名)，我们可以用两种等价的方式编写它。首先,递归地:
```
    /** Find an exit from M starting from PLACE. */
    void findExit(Maze M,Postion place){
      if(M.isAnExit (place))
        M.exitAt(place);
        if (! M.isMarkedAsVisited (place)) {
        M.markAsVisited (place);
        for (dir = 0; dir < 4; dir += 1)
        if (M.isLegalToMove (place, dir))
        findExit (M, place.move (dir));
        }
    }
```   
   然后，迭代一下：
```
    import ucb.util.Stack;
    import ucb.util.ArrayStack;
    /** Find an exit from M starting from PLACE. */
    void findExit(Maze M, Position place0) {
    Stack<Position> toDo = new ArrayStack<Position> ();
    toDo.push (place0);
    while (! toDo.isEmpty ()) {
    Position place = toDo.pop ();
    if (M.isAnExit (place))
    M.exitAt (place);
    if (! M.isMarkedAsVisited (place)) {
    M.markAsVisited (place);
    for (dir = 3; dir >= 0; dir -= 1)
    if (M.isLegalToMove (place, dir))
    toDo.push (place.move (dir));
    }
    }
    }
```
   其中 ArrayStack 是 ucb.util.Stack 的实现（见 §4.5）
    迭代版本背后的思想是toDo堆栈保存place_values的值，这些值作为参数出现在递归版本中，以查找Exitin。两个版本以相同的顺序访问相同的位置(这就是为什么循环在迭代版本中向后运行)。实际上，toDo在递归版本中扮演调用stackin的角色。实际上，递归过程的典型实现也为此使用堆栈，尽管它对程序员来说是不可见的
    
    
### 4.4.2 先进先出 及 双端 队列
   先近先出就是我们通常所说的在排队的意思:人们或事物在队列的一端加入队列，然后在另一端离开队列，这样第一个到达(或进入队列)的人就会第一个离开(或离开队列)。队列在程序中广泛出现，它们可以表示需要服务的请求序列。Java库(从Java 2开始，版本1.5)提供了一个标准的FIFO队列接口，但它是专门针对程序可能不得不等待一个元素被添加到队列中的情况而设计的。图4.11显示了一个更“经典”的可能接口。deque是最通用的双端队列，在程序中可能很少显式使用。它比FIFO队列使用更多的列表接口，因此专门化的需求不是特别迫切。不过，为了完整起见，我在图4.12中包含了一个可能的接口。
    
## 4.5 栈、队列 及双端队列的实现
   我们可以为ucb.util实现一个具体的堆栈类。栈接口如图4.13所示:作为ArrayList的扩展，就像java.util一样。Stack是java.util.Vector的一个继承前的版本。正如您所看到的，堆栈接口方法的名称是这样的，我们可以简单地从ArrayList继承size、isEmpty和lastIndexOf的实现。
    但是让我们用一些泛化来增加ArrayStack实现的趣味性。图4.14演示了一种有趣的类，称为适配器或包装器(第三章开始介绍的另一种设计模式)。这里显示的类StackAdapter将使列表对象看起来像一个堆栈。图中还显示了一个使用它从ArrayList类生成具体堆栈表示的示例。
    同样，对于List接口的任何实现，我们都可以轻松地提供Queue或Deque的实现，但是有一个问题。基于数组和基于链表的List实现都将同样好地支持我们的堆栈接口，提供在恒定平摊时间内操作的push和pop方法。但无论怎样选择,使用一个类似ArrayListin一样的方式实现队列的或双端队列接口都将会带来很差的性能。问题是显而易见的:正如我们所看到的,我们可以添加或删除从anarray很快的结束(高指数),但删除其他(索引0)需要在所有的元素数组,这需要时间Θ(N), Nis队列的大小。当然，我们可以简单地坚持使用LinkedLists，它没有这个问题，但是也有一个聪明的技巧，可以用数组高效地表示一般队列。
    当我们删除第一个队列时，我们不改变队列的项，而是改变数组中队列开始的位置。我们在数组中保留两个索引，一个指向第一个进入队列的项，另一个指向最后一个。这两个索引在数组中“互相追赶”，当它们通过高索引端时，就会回到索引0，反之亦然。这种排列被称为环状缓冲区。图4.15说明了这种情况。图4.16显示了一个可能的实现。
    
练习：
      4.1 实现Deque类型，作为java.util.Vector的扩展。到java.util所需的操作。AbstractList、addfirst、last、insertFirst、insertLast、removeFirst、removeLast，这样做的方式是，对向量的所有操作都继续有效(例如，get(0)继续得到与first()相同的元素)，并且所有这些操作的平摊代价保持不变。
      4.2 用构造函数实现一种类型的列表:
      public ConcatList (List L0, List L1){…}不支持添加和删除对象的可选操作，但给出了L0和L1连接的视图。也就是说，这样一个列表上的get(i)在执行get操作时，在L0和L1的连接中给出元素i(也就是说，对L0和L1引用的列表的更改反映在连接的列表中)。还要确保iterator和listIterator能够工作
      4.3 单链表结构可以是循环的。也就是说，列表中的某个元素可以有一个tail (next)字段，该字段指向列表中的较早项(不一定是列表中的第一个元素)。提出一种方法来检测列表中的某个地方是否存在这样的循环。但是，不要在任何数据结构中使用任何破坏性操作。也就是说，您不能使用其他数组、列表、向量、哈希表或类似的东西来跟踪列表中的项。只使用simplelist指针，而不更改任何列表的任何字段。请参见hw5目录中的CList.java。
      4.4 图4.6和LinkedList中LinkedList的实现。图4.7中的LinkedIter不提供对底层列表的并发修改检查。因此，一个代码片段，例如
```
      for (ListIterator<Object> i = L.listIterator ();i.hasNext (); ) 
      {if (bad (i.next ()))
      L.remove (i.previousIndex ());
      }
```
   会产生意想不到的效果。根据LinkedList的特殊定义，应该发生的是，当你调用L.remove时，i就无效了，并且对i方法的后续调用将抛出concurrentmodificationexception
      a.对于theLinkedListclass，上面的循环出了什么问题，为什么?
      b.修改我们的linkedlist实现方法来执行并发修改检查(因此上面的循环抛出ConcurrentModificationException)
      
   4.5 设计一个类似于StackAdapter的DequeAdapter类，允许从任意列表对象创建deques(或队列)。
      
   4.6 提供ArrayDeque的there size方法的实现(图4.16)。如果需要展开，您的方法应该将用于表示循环缓冲区的ArrayList的大小加倍。注意!您需要做的不仅仅是增加数组的大小，否则表示将会中断。