Java-集合类 List篇
2024-12-17 18:58:15 来源: 阅读:
List作为一个集合类的接口，我们实际使用中通常是使用其实现类，常用的实现类有ArrayList、Vector、LinkedList，以及Vector的子类Stack。
List 因为是基于基于数组或链表存储，所以它是有序的、允许空、且可重复。
先来看下它的继承、实现关系：
最高接口为Iterable，该接口中只有一个方法为iterator()，查看下JDK源码，该方法返回一个Iterator类型的接口。那么为什么不直接继承Iterator接口呢？
1 /* 2 * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved. 3 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22 * 23 * 24 */ 25 26 package java.lang; 27 28 import java.util.Iterator; 29 30 /** 31 * Implementing this interface allows an object to be the target of 32 * the "foreach" statement. 33 * 34 * @param <T> the type of elements returned by the iterator 35 * 36 * @since 1.5 37 */ 38 public interface Iterable<T> { 39 40 /** 41 * Returns an iterator over a set of elements of type T. 42 * 43 * @return an Iterator. 44 */ 45 Iterator<T> iterator(); 46 }
我们看下 Iterator的源码：
/* * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. * * * * * * * * * * * * * * * * * * * * */ package java.util; /** * An iterator over a collection. {@code Iterator} takes the place of * {@link Enumeration} in the Java Collections Framework. Iterators * differ from enumerations in two ways: * * <ul> * <li> Iterators allow the caller to remove elements from the * underlying collection during the iteration with well-defined * semantics. * <li> Method names have been improved. * </ul> * * <p>This interface is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @param <E> the type of elements returned by this iterator * * @author Josh Bloch * @see Collection * @see ListIterator * @see Iterable * @since 1.2 */ public interface Iterator<E> { /** * Returns {@code true} if the iteration has more elements. * (In other words, returns {@code true} if {@link #next} would * return an element rather than throwing an exception.) * * @return {@code true} if the iteration has more elements */ boolean hasNext(); /** * Returns the next element in the iteration. * * @return the next element in the iteration * @throws NoSuchElementException if the iteration has no more elements */ E next(); /** * Removes from the underlying collection the last element returned * by this iterator (optional operation). This method can be called * only once per call to {@link #next}. The behavior of an iterator * is unspecified if the underlying collection is modified while the * iteration is in progress in any way other than by calling this * method. * * @throws UnsupportedOperationException if the {@code remove} * operation is not supported by this iterator * * @throws IllegalStateException if the {@code next} method has not * yet been called, or the {@code remove} method has already * been called after the last call to the {@code next} * method */ void remove(); }
其主要方法 hasNext() 、next ()方法，当我们集合在传递过程中，是无法预知它的当前迭代位置的，所以hasNext和next（）方法将失效，而继承Iterable接口则可以返回一个迭代器，每次都是从头开始计数，且多个迭代器之间不干扰！
我们再来看下AbstractList抽象类:
1 /* 2 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. 3 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22 * 23 * 24 */ 25 26 package java.util; 27 28 /** 29 * This class provides a skeletal implementation of the {@link List} 30 * interface to minimize the effort required to implement this interface 31 * backed by a "random access" data store (such as an array). For sequential 32 * access data (such as a linked list), {@link AbstractSequentialList} should 33 * be used in preference to this class. 34 * 35 * <p>To implement an unmodifiable list, the programmer needs only to extend 36 * this class and provide implementations for the {@link #get(int)} and 37 * {@link List#size() size()} methods. 38 * 39 * <p>To implement a modifiable list, the programmer must additionally 40 * override the {@link #set(int, Object) set(int, E)} method (which otherwise 41 * throws an {@code UnsupportedOperationException}). If the list is 42 * variable-size the programmer must additionally override the 43 * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods. 44 * 45 * <p>The programmer should generally provide a void (no argument) and collection 46 * constructor, as per the recommendation in the {@link Collection} interface 47 * specification. 48 * 49 * <p>Unlike the other abstract collection implementations, the programmer does 50 * <i>not</i> have to provide an iterator implementation; the iterator and 51 * list iterator are implemented by this class, on top of the "random access" 52 * methods: 53 * {@link #get(int)}, 54 * {@link #set(int, Object) set(int, E)}, 55 * {@link #add(int, Object) add(int, E)} and 56 * {@link #remove(int)}. 57 * 58 * <p>The documentation for each non-abstract method in this class describes its 59 * implementation in detail. Each of these methods may be overridden if the 60 * collection being implemented admits a more efficient implementation. 61 * 62 * <p>This class is a member of the 63 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 64 * Java Collections Framework</a>. 65 * 66 * @author Josh Bloch 67 * @author Neal Gafter 68 * @since 1.2 69 */ 70 71 public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 72 /** 73 * Sole constructor. (For invocation by subclass constructors, typically 74 * implicit.) 75 */ 76 protected AbstractList() { 77 } 78 79 /** 80 * Appends the specified element to the end of this list (optional 81 * operation). 82 * 83 * <p>Lists that support this operation may place limitations on what 84 * elements may be added to this list. In particular, some 85 * lists will refuse to add null elements, and others will impose 86 * restrictions on the type of elements that may be added. List 87 * classes should clearly specify in their documentation any restrictions 88 * on what elements may be added. 89 * 90 * <p>This implementation calls {@code add(size(), e)}. 91 * 92 * <p>Note that this implementation throws an 93 * {@code UnsupportedOperationException} unless 94 * {@link #add(int, Object) add(int, E)} is overridden. 95 * 96 * @param e element to be appended to this list 97 * @return {@code true} (as specified by {@link Collection#add}) 98 * @throws UnsupportedOperationException if the {@code add} operation 99 * is not supported by this list 100 * @throws ClassCastException if the class of the specified element 101 * prevents it from being added to this list 102 * @throws NullPointerException if the specified element is null and this 103 * list does not permit null elements 104 * @throws IllegalArgumentException if some property of this element 105 * prevents it from being added to this list 106 */ 107 public boolean add(E e) { 108 add(size(), e); 109 return true; 110 } 111 112 /** 113 * {@inheritDoc} 114 * 115 * @throws IndexOutOfBoundsException {@inheritDoc} 116 */ 117 abstract public E get(int index); 118 119 /** 120 * {@inheritDoc} 121 * 122 * <p>This implementation always throws an 123 * {@code UnsupportedOperationException}. 124 * 125 * @throws UnsupportedOperationException {@inheritDoc} 126 * @throws ClassCastException {@inheritDoc} 127 * @throws NullPointerException {@inheritDoc} 128 * @throws IllegalArgumentException {@inheritDoc} 129 * @throws IndexOutOfBoundsException {@inheritDoc} 130 */ 131 public E set(int index, E element) { 132 throw new UnsupportedOperationException(); 133 } 134 135 /** 136 * {@inheritDoc} 137 * 138 * <p>This implementation always throws an 139 * {@code UnsupportedOperationException}. 140 * 141 * @throws UnsupportedOperationException {@inheritDoc} 142 * @throws ClassCastException {@inheritDoc} 143 * @throws NullPointerException {@inheritDoc} 144 * @throws IllegalArgumentException {@inheritDoc} 145 * @throws IndexOutOfBoundsException {@inheritDoc} 146 */ 147 public void add(int index, E element) { 148 throw new UnsupportedOperationException(); 149 } 150 151 /** 152 * {@inheritDoc} 153 * 154 * <p>This implementation always throws an 155 * {@code UnsupportedOperationException}. 156 * 157 * @throws UnsupportedOperationException {@inheritDoc} 158 * @throws IndexOutOfBoundsException {@inheritDoc} 159 */ 160 public E remove(int index) { 161 throw new UnsupportedOperationException(); 162 } 163 164 165 // Search Operations 166 167 /** 168 * {@inheritDoc} 169 * 170 * <p>This implementation first gets a list iterator (with 171 * {@code listIterator()}). Then, it iterates over the list until the 172 * specified element is found or the end of the list is reached. 173 * 174 * @throws ClassCastException {@inheritDoc} 175 * @throws NullPointerException {@inheritDoc} 176 */ 177 public int indexOf(Object o) { 178 ListIterator<E> it = listIterator(); 179 if (o==null) { 180 while (it.hasNext()) 181 if (it.next()==null) 182 return it.previousIndex(); 183 } else { 184 while (it.hasNext()) 185 if (o.equals(it.next())) 186 return it.previousIndex(); 187 } 188 return -1; 189 } 190 191 /** 192 * {@inheritDoc} 193 * 194 * <p>This implementation first gets a list iterator that points to the end 195 * of the list (with {@code listIterator(size())}). Then, it iterates 196 * backwards over the list until the specified element is found, or the 197 * beginning of the list is reached. 198 * 199 * @throws ClassCastException {@inheritDoc} 200 * @throws NullPointerException {@inheritDoc} 201 */ 202 public int lastIndexOf(Object o) { 203 ListIterator<E> it = listIterator(size()); 204 if (o==null) { 205 while (it.hasPrevious()) 206 if (it.previous()==null) 207 return it.nextIndex(); 208 } else { 209 while (it.hasPrevious()) 210 if (o.equals(it.previous())) 211 return it.nextIndex(); 212 } 213 return -1; 214 } 215 216 217 // Bulk Operations 218 219 /** 220 * Removes all of the elements from this list (optional operation). 221 * The list will be empty after this call returns. 222 * 223 * <p>This implementation calls {@code removeRange(0, size())}. 224 * 225 * <p>Note that this implementation throws an 226 * {@code UnsupportedOperationException} unless {@code remove(int 227 * index)} or {@code removeRange(int fromIndex, int toIndex)} is 228 * overridden. 229 * 230 * @throws UnsupportedOperationException if the {@code clear} operation 231 * is not supported by this list 232 */ 233 public void clear() { 234 removeRange(0, size()); 235 } 236 237 /** 238 * {@inheritDoc} 239 * 240 * <p>This implementation gets an iterator over the specified collection 241 * and iterates over it, inserting the elements obtained from the 242 * iterator into this list at the appropriate position, one at a time, 243 * using {@code add(int, E)}. 244 * Many implementations will override this method for efficiency. 245 * 246 * <p>Note that this implementation throws an 247 * {@code UnsupportedOperationException} unless 248 * {@link #add(int, Object) add(int, E)} is overridden. 249 * 250 * @throws UnsupportedOperationException {@inheritDoc} 251 * @throws ClassCastException {@inheritDoc} 252 * @throws NullPointerException {@inheritDoc} 253 * @throws IllegalArgumentException {@inheritDoc} 254 * @throws IndexOutOfBoundsException {@inheritDoc} 255 */ 256 public boolean addAll(int index, Collection<? extends E> c) { 257 rangeCheckForAdd(index); 258 boolean modified = false; 259 for (E e : c) { 260 add(index++, e); 261 modified = true; 262 } 263 return modified; 264 } 265 266 267 // Iterators 268 269 /** 270 * Returns an iterator over the elements in this list in proper sequence. 271 * 272 * <p>This implementation returns a straightforward implementation of the 273 * iterator interface, relying on the backing list's {@code size()}, 274 * {@code get(int)}, and {@code remove(int)} methods. 275 * 276 * <p>Note that the iterator returned by this method will throw an 277 * {@link UnsupportedOperationException} in response to its 278 * {@code remove} method unless the list's {@code remove(int)} method is 279 * overridden. 280 * 281 * <p>This implementation can be made to throw runtime exceptions in the 282 * face of concurrent modification, as described in the specification 283 * for the (protected) {@link #modCount} field. 284 * 285 * @return an iterator over the elements in this list in proper sequence 286 */ 287 public Iterator<E> iterator() { 288 return new Itr(); 289 } 290 291 /** 292 * {@inheritDoc} 293 * 294 * <p>This implementation returns {@code listIterator(0)}. 295 * 296 * @see #listIterator(int) 297 */ 298 public ListIterator<E> listIterator() { 299 return listIterator(0); 300 } 301 302 /** 303 * {@inheritDoc} 304 * 305 * <p>This implementation returns a straightforward implementation of the 306 * {@code ListIterator} interface that extends the implementation of the 307 * {@code Iterator} interface returned by the {@code iterator()} method. 308 * The {@code ListIterator} implementation relies on the backing list's 309 * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)} 310 * and {@code remove(int)} methods. 311 * 312 * <p>Note that the list iterator returned by this implementation will 313 * throw an {@link UnsupportedOperationException} in response to its 314 * {@code remove}, {@code set} and {@code add} methods unless the 315 * list's {@code remove(int)}, {@code set(int, E)}, and 316 * {@code add(int, E)} methods are overridden. 317 * 318 * <p>This implementation can be made to throw runtime exceptions in the 319 * face of concurrent modification, as described in the specification for 320 * the (protected) {@link #modCount} field. 321 * 322 * @throws IndexOutOfBoundsException {@inheritDoc} 323 */ 324 public ListIterator<E> listIterator(final int index) { 325 rangeCheckForAdd(index); 326 327 return new ListItr(index); 328 } 329 330 private class Itr implements Iterator<E> { 331 /** 332 * Index of element to be returned by subsequent call to next. 333 */ 334 int cursor = 0; 335 336 /** 337 * Index of element returned by most recent call to next or 338 * previous. Reset to -1 if this element is deleted by a call 339 * to remove. 340 */ 341 int lastRet = -1; 342 343 /** 344 * The modCount value that the iterator believes that the backing 345 * List should have. If this expectation is violated, the iterator 346 * has detected concurrent modification. 347 */ 348 int expectedModCount = modCount; 349 350 public boolean hasNext() { 351 return cursor != size(); 352 } 353 354 public E next() { 355 checkForComodification(); 356 try { 357 int i = cursor; 358 E next = get(i); 359 lastRet = i; 360 cursor = i + 1; 361 return next; 362 } catch (IndexOutOfBoundsException e) { 363 checkForComodification(); 364 throw new NoSuchElementException(); 365 } 366 } 367 368 public void remove() { 369 if (lastRet < 0) 370 throw new IllegalStateException(); 371 checkForComodification(); 372 373 try { 374 AbstractList.this.remove(lastRet); 375 if (lastRet < cursor) 376 cursor--; 377 lastRet = -1; 378 expectedModCount = modCount; 379 } catch (IndexOutOfBoundsException e) { 380 throw new ConcurrentModificationException(); 381 } 382 } 383 384 final void checkForComodification() { 385 if (modCount != expectedModCount) 386 throw new ConcurrentModificationException(); 387 } 388 } 389 390 private class ListItr extends Itr implements ListIterator<E> { 391 ListItr(int index) { 392 cursor = index; 393 } 394 395 public boolean hasPrevious() { 396 return cursor != 0; 397 } 398 399 public E previous() { 400 checkForComodification(); 401 try { 402 int i = cursor - 1; 403 E previous = get(i); 404 lastRet = cursor = i; 405 return previous; 406 } catch (IndexOutOfBoundsException e) { 407 checkForComodification(); 408 throw new NoSuchElementException(); 409 } 410 } 411 412 public int nextIndex() { 413 return cursor; 414 } 415 416 public int previousIndex() { 417 return cursor-1; 418 } 419 420 public void set(E e) { 421 if (lastRet < 0) 422 throw new IllegalStateException(); 423 checkForComodification(); 424 425 try { 426 AbstractList.this.set(lastRet, e); 427 expectedModCount = modCount; 428 } catch (IndexOutOfBoundsException ex) { 429 throw new ConcurrentModificationException(); 430 } 431 } 432 433 public void add(E e) { 434 checkForComodification(); 435 436 try { 437 int i = cursor; 438 AbstractList.this.add(i, e); 439 lastRet = -1; 440 cursor = i + 1; 441 expectedModCount = modCount; 442 } catch (IndexOutOfBoundsException ex) { 443 throw new ConcurrentModificationException(); 444 } 445 } 446 } 447 448 /** 449 * {@inheritDoc} 450 * 451 * <p>This implementation returns a list that subclasses 452 * {@code AbstractList}. The subclass stores, in private fields, the 453 * offset of the subList within the backing list, the size of the subList 454 * (which can change over its lifetime), and the expected 455 * {@code modCount} value of the backing list. There are two variants 456 * of the subclass, one of which implements {@code RandomAccess}. 457 * If this list implements {@code RandomAccess} the returned list will 458 * be an instance of the subclass that implements {@code RandomAccess}. 459 * 460 * <p>The subclass's {@code set(int, E)}, {@code get(int)}, 461 * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int, 462 * Collection)} and {@code removeRange(int, int)} methods all 463 * delegate to the corresponding methods on the backing abstract list, 464 * after bounds-checking the index and adjusting for the offset. The 465 * {@code addAll(Collection c)} method merely returns {@code addAll(size, 466 * c)}. 467 * 468 * <p>The {@code listIterator(int)} method returns a "wrapper object" 469 * over a list iterator on the backing list, which is created with the 470 * corresponding method on the backing list. The {@code iterator} method 471 * merely returns {@code listIterator()}, and the {@code size} method 472 * merely returns the subclass's {@code size} field. 473 * 474 * <p>All methods first check to see if the actual {@code modCount} of 475 * the backing list is equal to its expected value, and throw a 476 * {@code ConcurrentModificationException} if it is not. 477 * 478 * @throws IndexOutOfBoundsException if an endpoint index value is out of range 479 * {@code (fromIndex < 0 || toIndex > size)} 480 * @throws IllegalArgumentException if the endpoint indices are out of order 481 * {@code (fromIndex > toIndex)} 482 */ 483 public List<E> subList(int fromIndex, int toIndex) { 484 return (this instanceof RandomAccess ? 485 new RandomAccessSubList<>(this, fromIndex, toIndex) : 486 new SubList<>(this, fromIndex, toIndex)); 487 } 488 489 // Comparison and hashing 490 491 /** 492 * Compares the specified object with this list for equality. Returns 493 * {@code true} if and only if the specified object is also a list, both 494 * lists have the same size, and all corresponding pairs of elements in 495 * the two lists are <i>equal</i>. (Two elements {@code e1} and 496 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null : 497 * e1.equals(e2))}.) In other words, two lists are defined to be 498 * equal if they contain the same elements in the same order.<p> 499 * 500 * This implementation first checks if the specified object is this 501 * list. If so, it returns {@code true}; if not, it checks if the 502 * specified object is a list. If not, it returns {@code false}; if so, 503 * it iterates over both lists, comparing corresponding pairs of elements. 504 * If any comparison returns {@code false}, this method returns 505 * {@code false}. If either iterator runs out of elements before the 506 * other it returns {@code false} (as the lists are of unequal length); 507 * otherwise it returns {@code true} when the iterations complete. 508 * 509 * @param o the object to be compared for equality with this list 510 * @return {@code true} if the specified object is equal to this list 511 */ 512 public boolean equals(Object o) { 513 if (o == this) 514 return true; 515 if (!(o instanceof List)) 516 return false; 517 518 ListIterator<E> e1 = listIterator(); 519 ListIterator e2 = ((List) o).listIterator(); 520 while (e1.hasNext() && e2.hasNext()) { 521 E o1 = e1.next(); 522 Object o2 = e2.next(); 523 if (!(o1==null ? o2==null : o1.equals(o2))) 524 return false; 525 } 526 return !(e1.hasNext() || e2.hasNext()); 527 } 528 529 /** 530 * Returns the hash code value for this list. 531 * 532 * <p>This implementation uses exactly the code that is used to define the 533 * list hash function in the documentation for the {@link List#hashCode} 534 * method. 535 * 536 * @return the hash code value for this list 537 */ 538 public int hashCode() { 539 int hashCode = 1; 540 for (E e : this) 541 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 542 return hashCode; 543 } 544 545 /** 546 * Removes from this list all of the elements whose index is between 547 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 548 * Shifts any succeeding elements to the left (reduces their index). 549 * This call shortens the list by {@code (toIndex - fromIndex)} elements. 550 * (If {@code toIndex==fromIndex}, this operation has no effect.) 551 * 552 * <p>This method is called by the {@code clear} operation on this list 553 * and its subLists. Overriding this method to take advantage of 554 * the internals of the list implementation can <i>substantially</i> 555 * improve the performance of the {@code clear} operation on this list 556 * and its subLists. 557 * 558 * <p>This implementation gets a list iterator positioned before 559 * {@code fromIndex}, and repeatedly calls {@code ListIterator.next} 560 * followed by {@code ListIterator.remove} until the entire range has 561 * been removed. <b>Note: if {@code ListIterator.remove} requires linear 562 * time, this implementation requires quadratic time.</b> 563 * 564 * @param fromIndex index of first element to be removed 565 * @param toIndex index after last element to be removed 566 */ 567 protected void removeRange(int fromIndex, int toIndex) { 568 ListIterator<E> it = listIterator(fromIndex); 569 for (int i=0, n=toIndex-fromIndex; i<n; i++) { 570 it.next(); 571 it.remove(); 572 } 573 } 574 575 /** 576 * The number of times this list has been <i>structurally modified</i>. 577 * Structural modifications are those that change the size of the 578 * list, or otherwise perturb it in such a fashion that iterations in 579 * progress may yield incorrect results. 580 * 581 * <p>This field is used by the iterator and list iterator implementation 582 * returned by the {@code iterator} and {@code listIterator} methods. 583 * If the value of this field changes unexpectedly, the iterator (or list 584 * iterator) will throw a {@code ConcurrentModificationException} in 585 * response to the {@code next}, {@code remove}, {@code previous}, 586 * {@code set} or {@code add} operations. This provides 587 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in 588 * the face of concurrent modification during iteration. 589 * 590 * <p><b>Use of this field by subclasses is optional.</b> If a subclass 591 * wishes to provide fail-fast iterators (and list iterators), then it 592 * merely has to increment this field in its {@code add(int, E)} and 593 * {@code remove(int)} methods (and any other methods that it overrides 594 * that result in structural modifications to the list). A single call to 595 * {@code add(int, E)} or {@code remove(int)} must add no more than 596 * one to this field, or the iterators (and list iterators) will throw 597 * bogus {@code ConcurrentModificationExceptions}. If an implementation 598 * does not wish to provide fail-fast iterators, this field may be 599 * ignored. 600 */ 601 protected transient int modCount = 0; 602 603 private void rangeCheckForAdd(int index) { 604 if (index < 0 || index > size()) 605 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 606 } 607 608 private String outOfBoundsMsg(int index) { 609 return "Index: "+index+", Size: "+size(); 610 } 611 } 612 613 class SubList<E> extends AbstractList<E> { 614 private final AbstractList<E> l; 615 private final int offset; 616 private int size; 617 618 SubList(AbstractList<E> list, int fromIndex, int toIndex) { 619 if (fromIndex < 0) 620 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 621 if (toIndex > list.size()) 622 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 623 if (fromIndex > toIndex) 624 throw new IllegalArgumentException("fromIndex(" + fromIndex + 625 ") > toIndex(" + toIndex + ")"); 626 l = list; 627 offset = fromIndex; 628 size = toIndex - fromIndex; 629 this.modCount = l.modCount; 630 } 631 632 public E set(int index, E element) { 633 rangeCheck(index); 634 checkForComodification(); 635 return l.set(index+offset, element); 636 } 637 638 public E get(int index) { 639 rangeCheck(index); 640 checkForComodification(); 641 return l.get(index+offset); 642 } 643 644 public int size() { 645 checkForComodification(); 646 return size; 647 } 648 649 public void add(int index, E element) { 650 rangeCheckForAdd(index); 651 checkForComodification(); 652 l.add(index+offset, element); 653 this.modCount = l.modCount; 654 size++; 655 } 656 657 public E remove(int index) { 658 rangeCheck(index); 659 checkForComodification(); 660 E result = l.remove(index+offset); 661 this.modCount = l.modCount; 662 size--; 663 return result; 664 } 665 666 protected void removeRange(int fromIndex, int toIndex) { 667 checkForComodification(); 668 l.removeRange(fromIndex+offset, toIndex+offset); 669 this.modCount = l.modCount; 670 size -= (toIndex-fromIndex); 671 } 672 673 public boolean addAll(Collection<? extends E> c) { 674 return addAll(size, c); 675 } 676 677 public boolean addAll(int index, Collection<? extends E> c) { 678 rangeCheckForAdd(index); 679 int cSize = c.size(); 680 if (cSize==0) 681 return false; 682 683 checkForComodification(); 684 l.addAll(offset+index, c); 685 this.modCount = l.modCount; 686 size += cSize; 687 return true; 688 } 689 690 public Iterator<E> iterator() { 691 return listIterator(); 692 } 693 694 public ListIterator<E> listIterator(final int index) { 695 checkForComodification(); 696 rangeCheckForAdd(index); 697 698 return new ListIterator<E>() { 699 private final ListIterator<E> i = l.listIterator(index+offset); 700 701 public boolean hasNext() { 702 return nextIndex() < size; 703 } 704 705 public E next() { 706 if (hasNext()) 707 return i.next(); 708 else 709 throw new NoSuchElementException(); 710 } 711 712 public boolean hasPrevious() { 713 return previousIndex() >= 0; 714 } 715 716 public E previous() { 717 if (hasPrevious()) 718 return i.previous(); 719 else 720 throw new NoSuchElementException(); 721 } 722 723 public int nextIndex() { 724 return i.nextIndex() - offset; 725 } 726 727 public int previousIndex() { 728 return i.previousIndex() - offset; 729 } 730 731 public void remove() { 732 i.remove(); 733 SubList.this.modCount = l.modCount; 734 size--; 735 } 736 737 public void set(E e) { 738 i.set(e); 739 } 740 741 public void add(E e) { 742 i.add(e); 743 SubList.this.modCount = l.modCount; 744 size++; 745 } 746 }; 747 } 748 749 public List<E> subList(int fromIndex, int toIndex) { 750 return new SubList<>(this, fromIndex, toIndex); 751 } 752 753 private void rangeCheck(int index) { 754 if (index < 0 || index >= size) 755 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 756 } 757 758 private void rangeCheckForAdd(int index) { 759 if (index < 0 || index > size) 760 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 761 } 762 763 private String outOfBoundsMsg(int index) { 764 return "Index: "+index+", Size: "+size; 765 } 766 767 private void checkForComodification() { 768 if (this.modCount != l.modCount) 769 throw new ConcurrentModificationException(); 770 } 771 } 772 773 class RandomAccessSubList<E> extends SubList<E> implements RandomAccess { 774 RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) { 775 super(list, fromIndex, toIndex); 776 } 777 778 public List<E> subList(int fromIndex, int toIndex) { 779 return new RandomAccessSubList<>(this, fromIndex, toIndex); 780 } 781 }
AbstractList 实现了List<E>接口，但是他的子类如ArrayList 、Vector 也实现了List<E>，是因为equals(Object o) hashCode()等公用方法的具体实现
此类提供 List 接口的骨干实现，从而最大限度地减少了实现由“随机访问”数据存储（如数组）支持的接口所需的工作。对于连续的访问数据（如链表），应优先使用AbstractSequentialList，如LinkedList则继承自AbstractSequentialList而非此类。
还有个较奇怪的点，
public void add(int index, E element), public E remove(int index) ,public E set(int index, E element)
三个方法均抛出UnsupportedOperationException异常。为什么呢？
因为这三个不是公用方法了，必须由具体继承该抽象类的子类去覆写这三个方法！
接下来比较下三个最常用的实现类ArrayList、Vector、LinkedList异同
1.ArrayList是基于数组格式存储，寻址空间是连续的。而LinkedList是基于链表结构存储数据，物理空间是不连续的。当进行查找或定位某一元素时，LinkedList需要移动其结点指针，ArrayList的速率要比LinkedList更快。
进行删除、插入操作时，若是链表结构，只需打开其结点，重新指向下一结点即可完成操作，而数组的插入，需保证其寻址空间的连续性，故需将其插入位置后的元素进行移动。所以进行插入、删除操作时，LinkedList的速率要比ArrayList快。
2.LinkedList 还实现了 Queue 接口,该接口比List提供了更多的方法,包括 offer(),peek(),poll()等.
注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。
注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。
3.Vector与ArrayList都是基于数组来实现的，不同的是它实现了线程同步，即同一时刻，只允许一个线程对集合进行读写，但是实现同步需要很高的开销，因此它的访问速率比ArrayList慢。
4.Stack为继承自Vector的后进先出的堆栈模型。
Stack(类)
View Code
Stack 为堆栈模型，遵循后进先出（Last in First Out）。主要方法:
E push(E item)
把项压入堆栈顶部。
E pop()
移除堆栈顶部的对象，并作为此函数的值返回该对象。
E peek()
查看堆栈顶部的对象，但不从堆栈中移除它。
boolean empty()
测试堆栈是否为空。
int search(Object o)
返回对象在堆栈中的位置，以 1 为基数。
其中数组的最后一位元素即为栈顶元素，search方法返回的是离栈顶最近的item与栈顶之间的距离！
源码如下：
1 /* 2 * Copyright (c) 1994, 2010, Oracle and/or its affiliates. All rights reserved. 3 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22 * 23 * 24 */ 25 26 package java.util; 27 28 /** 29 * The <code>Stack</code> class represents a last-in-first-out 30 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five 31 * operations that allow a vector to be treated as a stack. The usual 32 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a 33 * method to <tt>peek</tt> at the top item on the stack, a method to test 34 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt> 35 * the stack for an item and discover how far it is from the top. 36 * <p> 37 * When a stack is first created, it contains no items. 38 * 39 * <p>A more complete and consistent set of LIFO stack operations is 40 * provided by the {@link Deque} interface and its implementations, which 41 * should be used in preference to this class. For example: 42 * <pre> {@code 43 * Deque<Integer> stack = new ArrayDeque<Integer>();}</pre> 44 * 45 * @author Jonathan Payne 46 * @since JDK1.0 47 */ 48 public 49 class Stack<E> extends Vector<E> { 50 /** 51 * Creates an empty Stack. 52 */ 53 public Stack() { 54 } 55 56 /** 57 * Pushes an item onto the top of this stack. This has exactly 58 * the same effect as: 59 * <blockquote><pre> 60 * addElement(item)</pre></blockquote> 61 * 62 * @param item the item to be pushed onto this stack. 63 * @return the <code>item</code> argument. 64 * @see java.util.Vector#addElement 65 */ 66 public E push(E item) { 67 addElement(item); 68 69 return item; 70 } 71 72 /** 73 * Removes the object at the top of this stack and returns that 74 * object as the value of this function. 75 * 76 * @return The object at the top of this stack (the last item 77 * of the <tt>Vector</tt> object). 78 * @throws EmptyStackException if this stack is empty. 79 */ 80 public synchronized E pop() { 81 E obj; 82 int len = size(); 83 84 obj = peek(); 85 removeElementAt(len - 1); 86 87 return obj; 88 } 89 90 /** 91 * Looks at the object at the top of this stack without removing it 92 * from the stack. 93 * 94 * @return the object at the top of this stack (the last item 95 * of the <tt>Vector</tt> object). 96 * @throws EmptyStackException if this stack is empty. 97 */ 98 public synchronized E peek() { 99 int len = size(); 100 101 if (len == 0) 102 throw new EmptyStackException(); 103 return elementAt(len - 1); 104 } 105 106 /** 107 * Tests if this stack is empty. 108 * 109 * @return <code>true</code> if and only if this stack contains 110 * no items; <code>false</code> otherwise. 111 */ 112 public boolean empty() { 113 return size() == 0; 114 } 115 116 /** 117 * Returns the 1-based position where an object is on this stack. 118 * If the object <tt>o</tt> occurs as an item in this stack, this 119 * method returns the distance from the top of the stack of the 120 * occurrence nearest the top of the stack; the topmost item on the 121 * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt> 122 * method is used to compare <tt>o</tt> to the 123 * items in this stack. 124 * 125 * @param o the desired object. 126 * @return the 1-based position from the top of the stack where 127 * the object is located; the return value <code>-1</code> 128 * indicates that the object is not on the stack. 129 */ 130 public synchronized int search(Object o) { 131 int i = lastIndexOf(o); 132 133 if (i >= 0) { 134 return size() - i; 135 } 136 return -1; 137 } 138 139 /** use serialVersionUID from JDK 1.0.2 for interoperability */ 140 private static final long serialVersionUID = 1224463164541339165L; 141 }
我们可以看到push(E item)实际上是调用父类Vector的addElement方法，empty()调用的是父类的Size（）方法。
因为水平有限，可能不足和不够严谨之处，欢迎批评雅正~~