[关闭]
@xmruibi 2015-02-14T18:18:40.000000Z 字数 8186 阅读 1650

List & Abstract List & Abstract Sequential List

Data_Structure

1. List Interface:

  1.         public interface List<E> extends Collection<E> {  
  2.            /****** Extends Collection Interface ******/
  3.             int size();  
  4.             boolean isEmpty();  
  5.             boolean contains(Object o);  
  6.             Iterator<E> iterator();  
  7.             Object[] toArray();  
  8.             <T> T[] toArray(T[] a);  
  9.             boolean add(E e);  
  10.             boolean remove(Object o);  
  11.             boolean containsAll(Collection<?> c);  
  12.             boolean addAll(Collection<? extends E> c);  
  13.             boolean addAll(int index, Collection<? extends E> c);  
  14.             boolean removeAll(Collection<?> c);  
  15.             boolean retainAll(Collection<?> c);  
  16.             void clear();  
  17.             boolean equals(Object o);  
  18.             int hashCode(); 
  23.            /***** Implementations of List Interface *****/
  24.             E get(int index);// get the index-th element 
  25.             E set(int index, E element);//set index-th element as new one
  26.             void add(int index, E element);//insert the element before the original index-th element
  27.             E remove(int index);// remove the index-th element  
  28.             int indexOf(Object o);// get index from the head  
  29.             int lastIndexOf(Object o);// get the index from the last
  31.             ListIterator<E> listIterator();//返回系列表迭代器  
  32.             ListIterator<E> listIterator(int index);//从第index开始的系列表迭代器，该迭代器介绍如下 
  35.             List<E> subList(int fromIndex, int toIndex);//a kind of replica for current list, it isn't a new instance, but reference to original list elements. So any operation on sublist can effect the original element. 
  36.         }

2. AbstractList & AbstractSequentialList

AbstractList: is to achieve main implementation of List interface, reduce the workload of "Random Access" data collection (ArrayList).

AbstractSequentialList: for "Consecutive Access" data collection (LinkedList)

3. AbstractList

  1. public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>{
  2.             protected AbstractList() {//提供一个空的构造函数  
  3.             }  
  7.             /****                No implemented                ****/
  8.             public boolean add(E e) {//在尾部添加元素e  
  9.                 add(size(), e);//在尾部执行添加操作  
  10.                 return true;  
  11.             }  
  13.             abstract public E get(int index);  
  15.             public E set(int index, E element) {  
  16.                 throw new UnsupportedOperationException();  
  17.             }  
  18.             public void add(int index, E element) {  
  19.                 throw new UnsupportedOperationException();  
  20.             }  
  21.             public E remove(int index) {  
  22.                 throw new UnsupportedOperationException();  
  23.             }  
  25.             /*********** Notice the following implemention are relied on list iterator ***********/
  26.             // Get the index of given object from the collection beginning 
  27.             public int indexOf(Object o) {  
  28.                 ListIterator<E> it = listIterator();  
  29.                 if (o==null) {  
  30.                     while (it.hasNext())
  31.                         if (it.next()==null) 
  32.                             return it.previousIndex();
  33.                 } else { 
  34.                     while (it.hasNext())  
  35.                         if (o.equals(it.next()))  
  36.                             return it.previousIndex();  
  37.                 }  
  38.                 return -1;  
  39.             }  
  40.             // Get the index of given object from the collection end 
  41.             public int lastIndexOf(Object o) {  
  42.                 ListIterator<E> it = listIterator(size()); 
  43.                 if (o==null) {
  44.                     while (it.hasPrevious()) 
  45.                         if (it.previous()==null)  
  46.                             return it.nextIndex(); 
  47.                 } else {  
  48.                     while (it.hasPrevious())  
  49.                         if (o.equals(it.previous())) 
  50.                             return it.nextIndex(); 
  51.                 }  
  52.                 return -1;  
  53.             }  
  56.             /*******************/
  57.             public void clear() { 
  58.                 removeRange(0, size());  
  59.             }  
  61.             public boolean addAll(int index, Collection<? extends E> c) {  
  62.                 rangeCheckForAdd(index);
  63.                 boolean modified = false;  
  64.                 for (E e : c) {  
  65.                     add(index++, e); 
  66.                     modified = true;  
  67.                 }  
  68.                 return modified;  
  69.             }  
  71.             /************** Forward-Direction ***************/
  72.             public Iterator<E> iterator() {//  
  73.                 return new Itr();  
  74.             }  
  76.             private class Itr implements Iterator<E> {  
  77.                 int cursor = 0;// current position
  78.                 int lastRet = -1;//last position of cursor 
  79.                 int expectedModCount = modCount;//for thread safe  
  81.                 public boolean hasNext() {  
  82.                     return cursor != size();//just check the cursor is not in the last  
  83.                 }  
  84.                 // One direction
  85.                 public E next() {  
  86.                     checkForComodification();
  87.                     // for concurrency to check if the list changed during iteration  
  88.                     try {  
  89.                         int i = cursor;// current position  
  90.                         E next = get(i);// get the element by position
  91.                         lastRet = i;// record last position
  92.                         cursor = i + 1;// new positioin (next position)
  93.                         return next;  
  94.                     } catch (IndexOutOfBoundsException e) {  
  95.                         checkForComodification();//why check again???  
  96.                         throw new NoSuchElementException();  
  97.                     }  
  98.                 }  
  99.                 //remove method inside the iterator 
  100.                 public void remove() {  
  101.                     if (lastRet < 0)//only can remove the visited element  
  102.                         throw new IllegalStateException();  
  103.                     checkForComodification();  
  105.                     try {  
  106.                         AbstractList.this.remove(lastRet);//parent interface remove implmentation
  107.                         if (lastRet < cursor)  
  108.                             cursor--; // back the current position  
  109.                         lastRet = -1;//back the lastRet  
  110.                         expectedModCount = modCount;//modified expectedModCount  
  111.                     } catch (IndexOutOfBoundsException e) {  
  112.                         throw new ConcurrentModificationException();  
  113.                     }  
  114.                 }  
  115.                 /****************** For concurrency check *******************/
  116.                 final void checkForComodification() {  
  117.                     if (modCount != expectedModCount)  
  118.                         throw new ConcurrentModificationException();  
  119.                 }  
  120.             }  
  124.             /************** Bidirectional ***************/
  125.             public ListIterator<E> listIterator() {// default from 0 (beginning)  
  126.                 return listIterator(0);  
  127.             }  
  129.             public ListIterator<E> listIterator(final int index) {  
  130.                 rangeCheckForAdd(index);//inside the list  
  131.                 return new ListItr(index); 
  132.             }  
  134.             //Bidirectional iterator extends Forward-Iterator 
  135.             private class ListItr extends Itr implements ListIterator<E> {  
  136.                 ListItr(int index) {// initial by given index 
  137.                     cursor = index;// set current cursor as given index 
  138.                 }  
  140.                 public boolean hasPrevious() {  
  141.                     return cursor != 0;  
  142.                 }  
  144.                 public E previous() {  
  145.                     checkForComodification();// for concurrency
  146.                     try {  
  147.                         int i = cursor - 1;  
  148.                         E previous = get(i);  
  149.                         lastRet = cursor = i;//lastRet always for the last visited position
  150.                         return previous;  
  151.                     } catch (IndexOutOfBoundsException e) {  
  152.                         checkForComodification();  
  153.                         throw new NoSuchElementException();  
  154.                     }  
  155.                 }  
  157.                 public int nextIndex() {  
  158.                     return cursor;  
  159.                 }  
  161.                 public int previousIndex() {  
  162.                     return cursor-1;  
  163.                 }  
  165.                 /*******************Setter and Add implementation in iterator **********************/
  166.                 public void set(E e) {  
  167.                     if (lastRet < 0)  
  168.                         throw new IllegalStateException();  
  169.                     checkForComodification();  
  171.                     try {  
  172.                         AbstractList.this.set(lastRet, e); // get parent interface to set element 
  173.                         expectedModCount = modCount; //modify expectedModCount
  174.                     } catch (IndexOutOfBoundsException ex) {  
  175.                         throw new ConcurrentModificationException();  
  176.                     }  
  177.                 }  
  179.                 public void add(E e) {  
  180.                     checkForComodification();  
  182.                     try {  
  183.                         int i = cursor;  
  184.                         AbstractList.this.add(i, e);
  185.                         lastRet = -1;
  186.                         cursor = i + 1;
  187.                         expectedModCount = modCount; 
  188.                     } catch (IndexOutOfBoundsException ex) {  
  189.                         throw new ConcurrentModificationException();  
  190.                     }  
  191.                 }  
  192.             }  
  195.             /************** Return sublist with beginning index and ended index ***************/ 
  196.             public List<E> subList(int fromIndex, int toIndex) {  
  197.                 return (this instanceof RandomAccess ?new RandomAccessSubList<>(this, fromIndex, toIndex) :  
  198.                         new SubList<>(this, fromIndex, toIndex));  
  199.             }  
  200.             //Use iterator for comparasion 
  201.             public boolean equals(Object o) {  
  202.                 if (o == this)  
  203.                     return true;  
  204.                 if (!(o instanceof List))  
  205.                     return false;  
  207.                 ListIterator<E> e1 = listIterator();  
  208.                 ListIterator e2 = ((List) o).listIterator();  
  209.                 while (e1.hasNext() && e2.hasNext()) {  
  210.                     E o1 = e1.next();  
  211.                     Object o2 = e2.next();  
  212.                     if (!(o1==null ? o2==null : o1.equals(o2)))  
  213.                         return false;  
  214.                 }  
  215.                 return !(e1.hasNext() || e2.hasNext());  
  216.             }  
  217.             /******************** Learn more about hashcode algorithm ********************/
  218.             public int hashCode() {  
  219.                 int hashCode = 1;  
  220.                 for (E e : this)  
  221.                     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());  
  222.                 return hashCode;  
  223.             }  
  226.             /******************* Remove elements by range *******************/ 
  227.             protected void removeRange(int fromIndex, int toIndex) {  
  228.                 ListIterator<E> it = listIterator(fromIndex);  
  229.                 for (int i=0, n=toIndex-fromIndex; i<n; i++) {  
  230.                     it.next();  
  231.                     it.remove();  
  232.                 }  
  233.             }  
  237.             protected transient int modCount = 0; // notice the transient keyword    
  238.             private void rangeCheckForAdd(int index) {  
  239.                 if (index < 0 || index > size())  
  240.                     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
  241.             }  
  243.             private String outOfBoundsMsg(int index) {  
  244.                 return "Index: "+index+", Size: "+size();  
  245.             }  
  246. }

4. AbstractSequantialList

  1. // Doesn't support random access, but similar with linked list which is also the abstract class for linkedlist
  2. public abstract class AbstractSequentialList<E> extends AbstractList<E> {  
  3.     protected AbstractSequentialList() {//提供一个空的默认构造函数  
  4.     }  
  8.     /****************** Through Iterator to achieve getter and setter ******************/ 
  9.     public E get(int index) {  
  10.         try {  
  11.             return listIterator(index).next(); 
  12.         } catch (NoSuchElementException exc) {  
  13.             throw new IndexOutOfBoundsException("Index: "+index);  
  14.         }  
  15.     }  
  17.     public E set(int index, E element) {  
  18.         try {  
  19.             ListIterator<E> e = listIterator(index);
  20.             E oldVal = e.next();  
  21.             e.set(element);  
  22.             return oldVal;  
  23.         } catch (NoSuchElementException exc) {  
  24.             throw new IndexOutOfBoundsException("Index: "+index);  
  25.         }  
  26.     }
  30.     /********************** Add and Remove by Iterator ************************/
  31.     public void add(int index, E element) {  
  32.         try {  
  33.             listIterator(index).add(element);  
  34.         } catch (NoSuchElementException exc) {  
  35.             throw new IndexOutOfBoundsException("Index: "+index);  
  36.         }  
  37.     }  
  39.     public E remove(int index) {  
  40.         try {  
  41.             ListIterator<E> e = listIterator(index);  
  42.             E outCast = e.next();  
  43.             e.remove();  
  44.             return outCast;  
  45.         } catch (NoSuchElementException exc) {  
  46.             throw new IndexOutOfBoundsException("Index: "+index);  
  47.         }  
  48.     }  
  50.     public boolean addAll(int index, Collection<? extends E> c) {  
  51.         try {  
  52.             boolean modified = false;  // mark the modified
  53.             ListIterator<E> e1 = listIterator(index);  
  54.             Iterator<? extends E> e2 = c.iterator();  
  55.             while (e2.hasNext()) {  
  56.                 e1.add(e2.next());  
  57.                 modified = true;  
  58.             }  
  59.             return modified;  
  60.         } catch (NoSuchElementException exc) {  
  61.             throw new IndexOutOfBoundsException("Index: "+index);  
  62.         }  
  63.     }  
  65.     /***************** Iterator Part ********************/
  66.     public Iterator<E> iterator() {  
  67.         return listIterator();  
  68.     }  
  69.     //Bidrectional Iterator  
  70.     public abstract ListIterator<E> listIterator(int index);  
  71. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注