_chapter 2.htm

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

<p class="docText">Now you have seen the fundamental methods of the <tt>
LinkedList</tt> class. You use a <tt>ListIterator</tt> to traverse the elements 
of the linked list in either direction, and to add and remove elements.</p>
<p class="docText">As you saw in the preceding section, there are many other 
useful methods for operating on linked lists that are declared in the <tt>
Collection</tt> interface. These are, for the most part, implemented in the <tt>
AbstractCollection</tt> superclass of the <tt>LinkedList</tt> class. For 
example, the <tt>toString</tt> method invokes <tt>toString</tt> on all elements 
and produces one long string of the format <tt>[A</tt>, <tt>B</tt>, <tt>C]</tt>. 
This is handy for debugging. Use the <tt>contains</tt> method to check whether 
an element is present in a linked list. For example, the call <tt>
staff.contains(&quot;Harry&quot;)</tt> returns <tt>true</tt> if the linked list already 
contains a string that is equal to the String <tt>&quot;Harry&quot;</tt>. However, there 
is no method that returns an iterator to that position. If you want to do 
something with the element beyond knowing that it exists, you have to program an 
iteration loop by hand.</p>
<div class="docNote">
  <p class="docNoteTitle">CAUTION</p>
  <table cellSpacing="0" cellPadding="1" width="90%" border="0">
    <tr>
      <td vAlign="top" width="60">
      <img alt="graphics/caution.gif" src="caution.gif" align="left" border="0" width="54" height="51"><br>
&nbsp;</td>
      <td vAlign="top">
      <p class="docText">The Java platform documentation points out that you 
      should not add a reference of a collection to itself. Otherwise, it is 
      easy to generate a stack overflow in the virtual machine. For example, the 
      following call is fatal:</p>
      <pre>LinkedList list = new LinkedList();
list.add(list); // add list to itself
String contents = list.toString(); // dies with infinite recursion
</pre>
      <p class="docText">Naturally, this is not a situation that comes up in 
      everyday programming.</td>
    </tr>
  </table>
</div>
<p class="docText">The library also supplies a number of methods that are, from 
a theoretical perspective, somewhat dubious. Linked lists do not support fast 
random access. If you want to see the <span class="docEmphasis">n</span>th 
element of a linked list, you have to start at the beginning and skip past the 
first <span class="docEmphasis">n</span> - 1 elements first. There is no 
shortcut. For that reason, programmers don't usually use linked lists in 
programming situations where elements need to be accessed by an integer index.</p>
<p class="docText">Nevertheless, the <tt>LinkedList</tt> class supplies a <tt>
get</tt> method that lets you access a particular element:</p>
<pre>Object obj = list.get(n);
</pre>
<p class="docText">Of course, this method is not very efficient. If you find 
yourself using it, you are probably using the wrong data structure for your 
problem.</p>
<p class="docText">You should <span class="docEmphasis">never</span> use this 
illusory random access method to step through a linked list. The code</p>
<pre>for (int i = 0; i &lt; list.size(); i++)
   <span class="docEmphasis">do something with</span>  list.get(i);
</pre>
<p class="docText">is staggeringly inefficient. Each time you look up another 
element, the search starts again from the beginning of the list. The <tt>
LinkedList</tt> object makes no effort to cache the position information.</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">The <tt>get</tt> method has one slight optimization: if 
      the index is at least <tt>size() / 2</tt>, then the search for the element 
      starts at the end of the list.</td>
    </tr>
  </table>
</div>
<p class="docText">The list iterator interface also has a method to tell you the 
index of the current position. In fact, because Java iterators conceptually 
point between elements, it has two of them: the <tt>nextIndex</tt> method 
returns the integer index of the element that would be returned by the next call 
to <tt>next</tt>; the <tt>previousIndex</tt> method returns the index of the 
element that would be returned by the next call to <tt>previous</tt>. Of course, 
that is simply one less than <tt>nextIndex</tt>. These methods are efficient梩he 
iterators keep a count of the current position. Finally, if you have an integer 
index <tt>n</tt>, then <tt>list.listIterator(n)</tt> returns an iterator that 
points just before the element with index <tt>n</tt>. That is, calling <tt>next</tt> 
yields the same element as <tt>list.get(n)</tt>. Of course, obtaining that 
iterator is inefficient.</p>
<p class="docText">If you have a linked list with only a handful of elements, 
then you don't have to be overly paranoid about the cost of the <tt>get</tt> and
<tt>set</tt> methods. But then why use a linked list in the first place? The 
only reason to use a linked list is to minimize the cost of insertion and 
removal in the middle of the list. If you only have a few elements, you can just 
use an array or a collection such as <tt>ArrayList</tt>.</p>
<p class="docText">We recommend that you simply stay away from all methods that 
use an integer index to denote a position in a linked list. If you want random 
access into a collection, use an array or <tt>ArrayList</tt>, not a linked list.</p>
<p class="docText">The program in <a class="docLink" href="#ch02list01">Example 
2-1</a> puts linked lists to work. It simply creates two lists, merges them, 
then removes every second element from the second list, and finally tests the
<tt>removeAll</tt> method. We recommend that you trace the program flow and pay 
special attention to the iterators. You may find it helpful to draw diagrams of 
the iterator positions, like this:</p>
<pre>|ACE   |BDFG
A|CE   |BDFG
AB|CE  B|DFG
. . .
</pre>
<p class="docText">Note that the call</p>
<pre>System.out.println(a);
</pre>
<p class="docText">prints all elements in the linked list <tt>a</tt>.</p>
<h5 id="ch02list01" class="docExampleTitle">Example 2-1 LinkedListTest.java</h5>
<pre> 1. import java.util.*;
 2.
 3. /**
 4.    This program demonstrates operations on linked lists.
 5. */
 6. public class LinkedListTest
 7. {
 8.    public static void main(String[] args)
 9.    {
10.       List a = new LinkedList();
11.       a.add(&quot;Angela&quot;);
12.       a.add(&quot;Carl&quot;);
13.       a.add(&quot;Erica&quot;);
14.
15.       List b = new LinkedList();
16.       b.add(&quot;Bob&quot;);
17.       b.add(&quot;Doug&quot;);
18.       b.add(&quot;Frances&quot;);
19.       b.add(&quot;Gloria&quot;);
20.
21.       // merge the words from b into a
22.
23.       ListIterator aIter = a.listIterator();
24.       Iterator bIter = b.iterator();
25.
26.       while (bIter.hasNext())
27.       {
28.          if (aIter.hasNext()) aIter.next();
29.          aIter.add(bIter.next());
30.       }
31.
32.       System.out.println(a);
33.
34.       // remove every second word from b
35.
36.       bIter = b.iterator();
37.       while (bIter.hasNext())
38.       {
39.          bIter.next(); // skip one element
40.          if (bIter.hasNext())
41.          {
42.             bIter.next(); // skip next element
43.             bIter.remove(); // remove that element
44.          }
45.       }
46.
47.       System.out.println(b);
48.
49.       // bulk operation: remove all words in b from a
50.
51.       a.removeAll(b);
52.
53.       System.out.println(a);
54.    }
</pre>
<h5 class="docSection3Title" id="ch02lev3sec3"><span class="docEmphasis"><tt>java.util.List</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>ListIterator listIterator()</tt></p>
  <p class="docList">returns a list iterator for visiting the elements of the 
  list.</li>
  <li>
  <p class="docList"><tt>ListIterator listIterator(int index)</tt></p>
  <p class="docList">returns a list iterator for visiting the elements of the 
  list whose first call to <tt>next</tt> will return the element with the given 
  index.</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>index</tt></td>
      <td class="docTableCell" vAlign="top">the position of the next visited 
      element</td>
    </tr>
  </table>
  <p>&nbsp;</li>
  <li>
  <p class="docList"><tt>void add(int i, Object element)</tt></p>
  <p class="docList">adds an element at the specified position.</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>index</tt></td>
      <td class="docTableCell" vAlign="top">the position of the new element</td>
    </tr>
    <tr>
      <td class="docTableCell" vAlign="top">&nbsp;</td>
      <td class="docTableCell" vAlign="top"><tt>element</tt></td>
      <td class="docTableCell" vAlign="top">the element to add</td>
    </tr>
  </table>
  <p>&nbsp;</li>
  <li>
  <p class="docList"><tt>void addAll(int i, Collection elements)</tt></p>
  <p class="docList">adds all elements from a collection to the specified 
  position.</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>index</tt></td>
      <td class="docTableCell" vAlign="top">the position of the first new 
      element</td>
    </tr>
    <tr>
      <td class="docTableCell" vAlign="top">&nbsp;</td>
      <td class="docTableCell" vAlign="top"><tt>elements</tt></td>
      <td class="docTableCell" vAlign="top">the elements to add</td>
    </tr>
  </table>
  <p>&nbsp;</li>
  <li>
  <p class="docList"><tt>Object remove(int i)</tt></p>
  <p class="docList">removes and returns an element at the specified position.</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>index</tt></td>
      <td class="docTableCell" vAlign="top">the position of the element to 
      remove</td>
    </tr>
  </table>
  <p>&nbsp;</li>
  <li>
  <p class="docList"><tt>Object set(int i, Object element)</tt></p>
  <p class="docList">replaces the element at the specified position with a new 
  element and returns the old element.</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>index</tt></td>
      <td class="docTableCell" vAlign="top">the replacement position</td>
    </tr>
    <tr>
      <td class="docTableCell" vAlign="top">&nbsp;</td>
      <td class="docTableCell" vAlign="top"><tt>element</tt></td>