_chapter 2.htm

Core Java 2(中文名称：JAVA 2 核心技术 卷二：高级特性）这是英文版的。

  <table cellSpacing="0" cellPadding="1" width="93%" border="1">
    <colgroup span="3" align="left">
    </colgroup>
    <tr>
      <td class="docTableCell" vAlign="top"><span class="docEmphasis">
      Parameters:</span></td>
      <td class="docTableCell" vAlign="top"><tt>other</tt></td>
      <td class="docTableCell" vAlign="top">the collection holding the elements 
      to add</td>
    </tr>
  </table>
  <p>&nbsp;</li>
  <li>
  <p class="docList"><tt>void clear()</tt></p>
  <p class="docList">removes all elements from this collection.</li>
  <li>
  <p class="docList"><tt>boolean retainAll(Collection other)</tt></p>
  <p class="docList">removes all elements from this collection that do not equal 
  one of the elements in the other collection. Returns <tt>true</tt> if the 
  collection changed as a result of this call.</p>
  <table cellSpacing="0" cellPadding="1" width="93%" border="1">
    <colgroup span="3" align="left">
    </colgroup>
    <tr>
      <td class="docTableCell" vAlign="top"><span class="docEmphasis">
      Parameters:</span></td>
      <td class="docTableCell" vAlign="top"><tt>other</tt></td>
      <td class="docTableCell" vAlign="top">the collection holding the elements 
      to be kept</td>
    </tr>
  </table>
  <p>&nbsp;</li>
  <li>
  <p class="docList"><tt>Object[] toArray()</tt></p>
  <p class="docList">returns an array of the objects in the collection.</li>
</ul>
<h5 class="docSection3Title" id="ch02lev3sec2"><span class="docEmphasis"><tt>java.util.Iterator</tt></span></h5>
<p><img alt="graphics/api.gif" src="api.gif" border="0" width="46" height="45"><br>
&nbsp;</p>
<ul>
  <li>
  <p class="docList"><tt>boolean hasNext()</tt></p>
  <p class="docList">returns <tt>true</tt> if there is another element to visit.</li>
  <li>
  <p class="docList"><tt>Object next()</tt></p>
  <p class="docList">returns the next object to visit. Throws a <tt>
  NoSuchElementException</tt> if the end of the collection has been reached.</li>
  <li>
  <p class="docList"><tt>Object remove()</tt></p>
  <p class="docList">removes and returns the last visited object. This method 
  must immediately follow an element visit. If the collection has been modified 
  since the last element visit, then the method throws an <tt>
  IllegalStateException</tt>.</li>
</ul>
<h3 class="docSection1Title" id="c2s2">Concrete Collections</h3>
<p class="docText">Rather than getting into more details about all the 
interfaces, we thought it would be helpful to first discuss the concrete data 
structures that the Java library supplies. Once you have a thorough 
understanding of what classes you will want to use, we will return to abstract 
considerations and see how the collections framework organizes these classes.</p>
<h4 class="docSection2Title" id="ch02lev2sec3">Linked Lists</h4>
<p class="docText">We used arrays and their dynamic cousin, the <tt>ArrayList</tt> 
class, for many examples in Volume 1. However, arrays and array lists suffer 
from a major drawback. Removing an element from the middle of an array is very 
expensive since all array elements beyond the removed one must be moved toward 
the beginning of the array (see <a class="docLink" href="#ch02fig04">Figure 2-4</a>). 
The same is true for inserting elements in the middle.</p>
<center>
<h5 id="ch02fig04" class="docFigureTitle">Figure 2-4. Removing an element from an array</h5>
<p>
<img alt="graphics/02fig04.gif" src="02fig04.gif" border="0" width="300" height="235"></p>
</center>
<p class="docText">Another well-known data structure, the
<span class="docEmphasis">linked list,</span> solves this problem. Whereas an 
array stores object references in consecutive memory locations, a linked list 
stores each object in a separate <span class="docEmphasis">link.</span> Each 
link also stores a reference to the next link in the sequence. In the Java 
programming language, all linked lists are actually <span class="docEmphasis">
doubly linked,</span> that is, each link also stores a reference to its 
predecessor (see <a class="docLink" href="#ch02fig05">Figure 2-5</a>).</p>
<center>
<h5 id="ch02fig05" class="docFigureTitle">Figure 2-5. A doubly linked list</h5>
<p>
<img alt="graphics/02fig05.gif" src="02fig05.gif" border="0" width="500" height="244"></p>
</center>
<p class="docText">Removing an element from the middle of a linked list is an 
inexpensive operation梠nly the links around the element to be removed need to be 
updated (see <a class="docLink" href="#ch02fig06">Figure 2-6</a>).</p>
<center>
<h5 id="ch02fig06" class="docFigureTitle">Figure 2-6. Removing an element from a linked list</h5>
<p>
<img alt="graphics/02fig06.gif" src="02fig06.gif" border="0" width="500" height="231"></p>
</center>
<p class="docText">Perhaps you once had a course in data structures where you 
learned how to implement linked lists. You may have bad memories of tangling up 
the links when removing or adding elements in the linked list. If so, you will 
be pleased to learn that the Java collections library supplies a class <tt>
LinkedList</tt> ready for you to use.</p>
<p class="docText">The <tt>LinkedList</tt> class implements the <tt>Collection</tt> 
interface. You can use the familiar methods to traverse a list. The following 
code example prints the first three elements of a list, adds three elements, and 
then removes the third one.</p>
<pre>LinkedList staff = new LinkedList();
staff.add(&quot;Angela&quot;);
staff.add(&quot;Bob&quot;);
staff.add(&quot;Carl&quot;);
Iterator iter = staff.iterator();
for (int i = 0; i &lt; 3; i++)
   System.out.println(iter.next());
iter.remove(); // remove last visited element
</pre>
<p class="docText">However, there is an important difference between linked 
lists and generic collections. A linked list is an <span class="docEmphasis">
ordered collection</span> where the position of the objects matters. The <tt>
LinkedList.add</tt> method adds the object to the end of the list. But you often 
want to add objects somewhere in the middle of a list. This position-dependent
<tt>add</tt> method is the responsibility of an iterator, since iterators 
describe positions in collections. Using iterators to add elements only makes 
sense for collections that have a natural ordering. For example, the
<span class="docEmphasis">set</span> data type that we discuss in the next 
section does not impose any ordering on its elements. Therefore, there is no <tt>
add</tt> method in the <tt>Iterator</tt> interface. Instead, the collections 
library supplies a subinterface <tt>ListIterator</tt> that contains an <tt>add</tt> 
method:</p>
<pre>interface ListIterator extends Iterator
{
   void add(Object);
   . . .
}
</pre>
<p class="docText">Unlike <tt>Collection.add</tt>, this method does not return a
<tt>boolean</tt>梚t is assumed that the <tt>add</tt> operation always modifies 
the list.</p>
<p class="docText">In addition, the <tt>ListIterator</tt> interface has two 
methods that you can use for traversing a list backwards.</p>
<pre>Object previous()
boolean hasPrevious()
</pre>
<p class="docText">Like the <tt>next</tt> method, the <tt>previous</tt> method 
returns the object that it skipped over.</p>
<p class="docText">The <tt>listIterator</tt> method of the <tt>LinkedList</tt> 
class returns an iterator object that implements the <tt>ListIterator</tt> 
interface.</p>
<pre>ListIterator iter = staff.listIterator();
</pre>
<p class="docText">The <tt>add</tt> method adds the new element
<span class="docEmphasis">before</span> the iterator position. For example, the 
code</p>
<pre>ListIterator iter = staff.listIterator();
iter.next();
iter.add(&quot;Juliet&quot;);
</pre>
<p class="docText">skips past the first element in the linked list and adds <tt>
&quot;Juliet&quot;</tt> before the second element (see
<a class="docLink" href="#ch02fig07">Figure 2-7</a>).</p>
<center>
<h5 id="ch02fig07" class="docFigureTitle">Figure 2-7. Adding an element to a linked list</h5>
<p>
<img alt="graphics/02fig07.gif" src="02fig07.gif" border="0" width="500" height="376"></p>
</center>
<p class="docText">If you call the <tt>add</tt> method multiple times, the 
elements are simply added in the order in which you supplied them. They all get 
added in turn before the current iterator position.</p>
<p class="docText">When you use the <tt>add</tt> operation with an iterator that 
was freshly returned from the <tt>listIterator</tt> method and that points to 
the beginning of the linked list, the newly added element becomes the new head 
of the list. When the iterator has passed the last element of the list (that is, 
when <tt>hasNext</tt> returns <tt>false</tt>), the added element becomes the new 
tail of the list. If the linked list has <span class="docEmphasis">n</span> 
elements, there are <span class="docEmphasis">n</span> +1 spots for adding a new 
element. These spots correspond to the <span class="docEmphasis">n</span> +1 
possible positions of the iterator. For example, if a linked list contains three 
elements, A, B, and C, then the four possible positions (marked as <tt>|</tt>) 
for inserting a new element are:</p>
<pre>|ABC
A|BC
AB|C
ABC|
</pre>
<div class="docNote">
  <p class="docNoteTitle">NOTE</p>
  <table cellSpacing="0" cellPadding="1" width="90%" border="0">
    <tr>
      <td vAlign="top" width="60">
      <img alt="graphics/note.gif" src="note.gif" align="left" border="0" width="54" height="53"><br>
&nbsp;</td>
      <td vAlign="top">
      <p class="docText">You have to be careful with the &quot;cursor&quot; analogy. The
      <tt>remove</tt> operation does not quite work like the backspace key. 
      Immediately after a call to <tt>next</tt>, the <tt>remove</tt> method 
      indeed removes the element to the left of the iterator, just like the 
      backspace key would. However, if you just called <tt>previous</tt>, the 
      element to the right is removed. And you can't call <tt>remove</tt> twice 
      in a row.</p>
      <p class="docText">Unlike the <tt>add</tt> method, which only depends on 
      the iterator position, the <tt>remove</tt> method depends on the iterator 
      state.</td>
    </tr>
  </table>
</div>
<p class="docText">Finally, there is a <tt>set</tt> method that replaces the 
last element returned by a call to <tt>next</tt> or <tt>previous</tt> with a new 
element. For example, the following code replaces the first element of a list 
with a new value:</p>
<pre>ListIterator iter = list.listIterator();
Object oldValue = iter.next(); // returns first element
iter.set(newValue); // sets first element to newValue
</pre>
<p class="docText">As you might imagine, if an iterator traverses a collection 
while another iterator is modifying it, confusing situations can occur. For 
example, suppose an iterator points before an element that another iterator has 
just removed. The iterator is now invalid and should no longer be used. The 
linked list iterators have been designed to detect such modifications. If an 
iterator finds that its collection has been modified by another iterator or by a 
method of the collection itself, then it throws a <tt>
ConcurrentModificationException</tt>. For example, consider the following code:</p>
<pre>LinkedList list = . . .;
ListIterator iter1 = list.listIterator();
ListIterator iter2 = list.listIterator();
iter1.next();
iter1.remove();
iter2.next(); // throws ConcurrentModificationException
</pre>
<p class="docText">The call to <tt>iter2.next</tt> throws a <tt>
ConcurrentModificationException</tt> since <tt>iter2</tt> detects that the list 
was modified externally.</p>
<p class="docText">To avoid concurrent modification exceptions, follow this 
simple rule: You can attach as many iterators to a container as you like, 
provided that all of them are only readers. Alternatively, you can attach a 
single iterator that can both read and write.</p>
<p class="docText">Concurrent modification detection is achieved in a simple 
way. The container keeps track of the number of mutating operations (such as 
adding and removing elements). Each iterator keeps a separate count of the 
number of mutating operations that <span class="docEmphasis">it</span> was 
responsible for. At the beginning of each iterator method, the iterator simply 
checks whether its own mutation count equals that of the collection. If not, it 
throws a <tt>ConcurrentModificationException</tt>.</p>
<p class="docText">This is an excellent check and a great improvement over the 
fundamentally unsafe iterators in the C++ STL framework. Note, however, that it 
does not automatically make collections safe for multithreading. We discuss 
thread safety issues later in this chapter.</p>
<div class="docNote">
  <p class="docNoteTitle">NOTE</p>
  <table cellSpacing="0" cellPadding="1" width="90%" border="0">
    <tr>
      <td vAlign="top" width="60">
      <img alt="graphics/note.gif" src="note.gif" align="left" border="0" width="54" height="53"><br>
&nbsp;</td>
      <td vAlign="top">
      <p class="docText">There is, however, a curious exception to the detection 
      of concurrent modifications. The linked list only keeps track of
      <span class="docEmphasis">structural</span> modifications to the list, 
      such as adding and removing links. The <tt>set</tt> method does
      <span class="docEmphasis">not</span> count as a structural modification. 
      You can attach multiple iterators to a linked list, all of which call <tt>
      set</tt> to change the contents of existing links. This capability is 
      required for a number of algorithms in the <tt>Collections</tt> class that 
      we discuss later in this chapter.</td>
    </tr>
  </table>
</div>