Bag Implementations That Use Arrays - Data Structures and Abstractions with Java - page 41

Remember that we are not required to maintain any particular order for a bag's entries. So
instead of shifting array entries after removing an entry, we can replace the entry being removed
with the last entry in the array, as follows. After locating anEntry in bag[index] , as Figure 2-7a
indicates, we copy the entry in bag[numberOfEntries - 1] to bag[index] (Figure 2-7b). We then
replace the entry in bag[numberOfEntries - 1] with null , as Figure 2-7c illustrates, and finally we
decrement numberOfEntries .

FIGURE 2-7

Avoiding a gap in the array while removing an entry

bag[index]

(a)

Doug Alice Nancy Ted Vandee Sue

(b)

Doug Sue Nancy Ted Vandee Sue

0 1 2 3 4 5

6

(c)

Doug Sue Nancy Ted Vandee null

0 1 2 3 4 5

6

2.23

Pseudocode for removing a given entry. Let's organize our discussion by writing some pseudo-
code to remove the given entry, anEntry , from a bag that contains it:
Locate anEntry in the array bag ; assume it occurs at bag[index]
bag[index] = bag[numberOfEntries - 1]
bag[numberOfEntries - 1] = null
Decrement the counter numberOfEntries
return true
This pseudocode assumes that the bag contains anEntry .
After we add some details to the pseudocode to accommodate the situation in which anEntry is
not in the bag, and to avoid computing numberOfEntries - 1 more than once, as we did in
Segment 2.21, the pseudocode appears as follows:
Search the array bag for anEntry
if (anEntry is in the bag at bag[index])
{

Decrement the counter numberOfEntries
bag[index] = bag[numberOfEntries]
bag[numberOfEntries] = null
return true

}
else
return false

2.24

Avoiding duplicate effort. We can easily translate this pseudocode into the Java method remove .
However, if we were to do so, we would see much similarity between our new method and the remove
method we wrote earlier in Segment 2.21. In fact, if anEntry occurs in bag[numberOfEntries - 1] ,
both remove methods will have exactly the same effect. To avoid this duplicate effort, both remove
methods can call a private method that performs the removal. We can specify such a method as follows:

// Removes and returns the entry at a given array index.
// If no such entry exists, returns null.
private T removeEntry( int givenIndex)