本节书摘来华章计算机《数据结构与抽象：Java语言描述（原书第4版）》一书中的第2章 ，第2.1.7节，［美］弗兰克M.卡拉诺（Frank M. Carrano） 蒂莫西M.亨利（Timothy M. Henry） 著 罗得岛大学 新英格兰理工学院 辛运帏 饶一梅 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.1.7 删除项的方法
我们将从包中删除项的3个方法推迟到现在，因为3个方法中的一个有些困难，它涉及的查找机制与contains中用到的相似。我们从更容易定义的另两个方法入手。
方法clear。方法clear从包中删除所有的项，一次删除一个。下面这个clear的定义调用方法remove，直到包为空。
循环中每次要删除哪个项是不重要的。所以，我们调用删除一个不确定项的remove方法。另外，不保存方法返回的这个项。
注意，因为remove方法将调用checkInitialization，所以clear不需要显式地调用它。
注：我们可以根据尚未定义的方法remove来定义方法clear。但是，在定义remove之前，我们不能完全测试clear。
自测题10 修改方法clear的定义，让它不调用isEmpty。
提示：while语句应该有一个空循环体。
自测题11 用下列语句
替换上一段的clear定义中的循环，有什么缺点？
删除不确定项。不带参数的方法remove从包中删除一个不确定项，只要包不为空。回忆程序清单1-1所示的接口中给出的方法的规格说明，该方法返回被它删除的项：
如果方法执行前包是空的，则返回null。
从包中删除一个项，涉及从数组中删除它。虽然我们能访问数组bag中的任何项，但最后一项是最容易删除的。为此，
- 访问最后一项，它能被返回。
- 将项的数组元素设置为null。
- numberOfEntries减1。
numberOfEntries减1，就会忽略最后一项，意味着它已被高效地删除了，即使我们没有将它在数组中的位置设置为null。但是不要跳过这一步。
将前面的步骤转换为Java程序，得到如下的方法定义：
安全说明：将数组元素bag[numberOfEntries???-???1]设置为null，标记被删除对象可进行垃圾回收，并防止恶意代码来访问它。
安全说明：在正确计数后更新计数器。在前面的代码中，删除数组最后一项后才将numberOfEntries减1，即使计算了3次numberOfEntries-1。虽然下面的改进可以避免这个重复，但时间上微不足道的节省不值得冒太早减小计数器带来的不安全
风险：
不可否认，在这种情形下，数组和计数器不同步的情况还是有可能的。不管怎样，如果逻辑更复杂，则数组处理过程中可能会发生异常。这个中断将导致已更新的计数器不准确。
自测题12 为什么方法remove将从数组bag中删除的项替换为null？
自测题13 前一个remove方法删除数组bag中的最后一项。删除其他项为什么会更难完成？
删除给定的项。从包中删除项的第3个方法涉及删除给定项（称为anEntry）的方法。如果项在包中出现多次，则仅删除它的一次出现。没有指定删除哪次出现。我们只删除查找时遇到的anEntry的首次出现。正如我们在1.2节中所讨论的，方法将根据在包中是否找到这个项而返回真或假。
假定包不为空，则查找数组bag与方法contains所做的一样。如果anEntry等于bag[index]，则记下index的值。图2-4说明成功查找后的数组。
现在需要删除bag[index]中的项。如果只写
则删除bag[index]中指向的项的引用，但数组中会留下空隙。即包的内容不再占据连续的数组位置，如图2-5a所示。我们可以移动随后的项来去掉这个空隙，如图2-5b所示，并将指向最后项的重复引用替换为null，如图2-5c所示。但不一定用这个费时的方法。
记住，我们不需要维护包中项的具体次序。所以删除项后，不是移动数组项，而是用数组中最后面的项替换被删除的项，如图2-6所示。找到bag[index]中的anEntry后，如图2-6a所示，将bag[numberOfEntries-1]中的项复制到bag[index]中（见图2-6b）。然后将bag[numberOfEntries-1]中的项替换为null，如图2-6c所示，最后numberOfEntries减1。
删除给定项的伪代码。现在将前面的讨论用伪代码写出来，对给定的项anEntry，从含有它的包中删除：
这个伪代码假定包中含有anEntry。
在伪代码中添加一些细节，以适应anEntry不在包中的情形，伪代码如下：
避免重复工作。很容易将这段伪代码翻译为Java方法remove。但是，如果我们这样做了，就会发现新方法与删除不确定项中写过的remove方法有很多类似的地方。实际上，如果anEntry出现在bag[numberOfEntries-1]处，则这两个remove方法将有完全相同的效果。为避免这样的重复劳动，两个remove方法可以调用一个私有方法来完成删除操作。可以如下说明一个方法：
因为这是一个私有方法，所以类中的其他方法可以给它传一个下标作为参数，仍能让这个下标（实现细节）对类的客户隐藏。
在实现这个私有方法之前，让我们看看是否可以用它来修改“删除不确定项”中的remove方法。因为该方法删除并返回数组bag的最后一项，即bag[numberOfEntries-1]，所以它的定义中可以调用removeEntry(numberOfEntries-1)。继续我们的工作，就如同removeEntry已经定义且测试过一样，可以如下定义remove：
这个定义看上去不错，我们来实现第二个remove方法。
第二个remove方法。第一个remove方法不查找要删除的项，因为它删除数组中的最后一项。但第二个remove方法必须执行查找。现在先不考虑在数组中查找一个项的细节，我们将这个任务委派给另一个私有方法来完成，它的规格说明如下所示。
假定这个私有方法已经定义且测试过，我们在第二个remove方法中调用它，如下所示。
注意，removeEntry返回它删除的项或者null。这正是第一个remove方法所需要的，但第二个remove方法必须返回一个布尔值。所以，在第二个方法中，我们必须将想删除的项与removeEntry的返回值进行比较，以便得到希望的布尔值。
自测题14 remove的前一个定义中的return语句能写成下面这样吗？
自测题15 ArrayBag中的数组bag含有包aBag中的项。如果数组含有字符串"A"，"A"，"B"，"A"，"C"，为什么aBag.remove("B")将数组的内容改变为"A"，"A"，"C"，"A"，null，而不是"A"，"A"，"A"，"C"，null或"A"，"A"，null，"A"，"C"？
私有方法removeEntry的定义。现在回过头来看在“删除给定项的伪代码”中为从包中删除指定项而写的伪代码。私有方法removeEntry假定项的查找已经完成，所以可以忽略伪代码的第一步。不管怎样，伪代码的其他部分给出了删除一个项的基本逻辑。可以修改伪代码，如下所示。
前一段给出的第二个remove方法的定义将getIndexOf返回的整数传给removeEntry。因为getIndexOf可能返回-1，所以removeEntry必须对这样一个参数值进行查找。因此，如果包不为空（即如果numberOfEntries大于0）且givenIndex大于或等于0，则removeEntry删除位于givenIndex的数组项，将它用最后一项来替换，并让numberOfEntries减1。然后该方法返回删除的项。但是，如果包是空的，则该方法返回null。
该方法的代码如下所示。
找到要删除的项。现在需要考虑如何在包中找到要删除的项，这样才可以将它的下标传给removeEntry。方法contains执行与remove的定义中查找anEntry相同的机制。不幸的是，contains返回真或假，它不返回项在数组中的下标。所以在定义这个方法时不能简单调用那个方法。
设计决策：方法contains应该返回找到项的下标吗？
我们应该修改contains的定义，让它返回一个下标而不是一个布尔值吗？不应该。作为一个公有方法，contains不应该给客户提供这样的实现细节。客户不应该期望得到放在数组中的包的项，因为它们没有具体的次序。不应改变contains的规格说明，而是应该遵循最初的规划，定义一个私有方法来查找一个项并返回它的下标。
getIndexOf的定义。getIndexOf的定义与contains的定义很像，我们记得方法contains中它的循环是这样的：
这个循环结构适合于方法getIndexOf，但当找到项时必须保存index的值。该方法将返回这个下标而不是一个布尔值。
为修改前面这个循环以便将其用在getIndexOf中，我们定义一个整数变量where来记录当anEntry等于bag[index]时index的值。所以getIndexOf是这样的：
方法getIndexOf返回where的值。注意，我们将where初始化为-1，这是没找到anEntry时返回的值。
自测题16 在方法getIndexOf的return语句之前，能添加什么assert语句来表示方法能够返回的可能值？
自测题17 修改方法getIndexOf的定义，让它不使用布尔值。
旁白：正向思考
与方法contains不一样，方法getIndexOf将布尔变量found仅用来控制循环，而不是作为返回值。所以我们可以修改逻辑，避免取反操作符!的使用。
我们使用变量stillLooking来替代found，并将它初始化为真。然后可以将布尔表达式!found替换为stillLooking，如你在下面的方法getIndexOf的定义中所见：
如果在数组中找到anEntry，则将stillLooking设置为假来结束循环。有些程序员倾向于正向思考，如这个版本中所述，而另一些人觉得!found就已经非常清楚了。
方法contains定义的修改。完成remove和它们调用的私有方法的定义后，我们知道方法contains可以调用私有方法getIndexOf，得到比方法contains中更简单的定义。我们记得，如果anEntry在包中，则表达式getIndexOf(anEntry)返回0～numberOfEntries-1的一个整数，否则返回-1。即如果anEntry在包中，则getIndexOf(anEntry)大于-1。所以可以定义contains如下：
因为已经修改了contains的定义，所以应该再次测试它。为此，我们还要测试私有方法getIndexOf。
注：方法contains和remove都必须执行类似的对项的查找。将查找功能单独放在方法contains和remove都能调用的一个私有方法中，使得我们的代码更易调试及维护。这个策略与在两个remove方法都调用的私有方法removeEntry中定义删除操作时用到的一样。
设计决策：什么方法应该调用checkInitialization？
类ArrayBag的关键点是数组bag的分配。你已经看到，像add这样依赖于这个数组的方法，是从调用checkInitialization开始的，以确保构造方法已经完全初始化了ArrayBag对象，包括数组的分配。而我们可以坚持在直接涉及数组bag的每个方法中调用checkInitialization，不过我们选择更加灵活的做法。例如，私有方法getIndexOf和removeEntry直接访问bag，但它们不调用checkInitialization。为什么？删除给定项的remove方法调用getIndexOf和removeEntry。如果这两个私有方法都调用checkInitialization，则它被公有方法调用两次。所以，对于这个具体实现来说，我们在公有方法中调用checkInitialization，并为这两个私有方法添加一个前置条件来说明checkInitialization必须要先调用。因为它们是私有方法，所以这样的前置条件只给我们这些实现者和维护者使用。一旦做了这个决策，其他的remove方法和contains方法都必须调用checkInitialization，因为它们都只调用这两个私有方法中的一个。
注意，私有方法getIndexOf和removeEntry都执行一个已定义的任务。它们不再为第二个任务（检查初始化）负责。
程序设计技巧：即使可能已经有了方法的正确定义，但如果你想到了一个更好的实现，也不要犹豫地去修改它。肯定要再次测试方法！
测试。我们的ArrayBag类基本上完成了。可以使用前面测试remove和clear的测试方法了——我们假定它们是正确的。从一个没满的包开始，在线程序ArrayBagDemo3删除包中的项直到它为空时为止。它还包括了从满包开始的类似的测试。最后，应该将前面的测试整合起来再次运行它们。在本书在线网站的源代码中，测试程序是ArrayBagDemo，完整的类是ArrayBag。