實現retainAll（）方法的最佳方法

Question

我有這個自定義類名爲MyAbstractList，它實現了MyList接口。這裏是代碼：

public abstract class MyAbstractList<E> implements MyList<E> { 
    protected int size = 0; // The size of the list 

    protected MyAbstractList() { 
    } 

    protected MyAbstractList(E[] objects) { 
     for (int i = 0; i < objects.length; i++) 
      add(objects[i]); 
    } 

    public void add(E e) { 
     add(size, e); 
    } 

    public boolean isEmpty() { 
     return size == 0; 
    } 

    public int size() { 
     return size; 
    } 

    public boolean addAll(MyList<E> otherList) { 
     for (E e : otherList) { 
      add(e); 
     } 
     if (otherList.size() > 0) 
      return true; 
     return false; 
    } 

    public boolean removeAll(MyList<E> otherList) { 
     boolean removed = false; 
     for (E e : otherList) { 
      if (remove(e) && !removed) 
       removed = true; 
     } 
     return removed; 
    } 

    public boolean remove(E e) { 
     if (indexOf(e) >= 0) { 
      remove(indexOf(e)); 
      return true; 
     } else 
      return false; 
    } 

    /** Retains the elements in this list that are also in otherList 
    * Returns true if this list changed as a result of the call  */ 
    public boolean retainAll(MyList<E> otherList) { 

    } 
} 

如何實施retainAll()方法？

MyList接口：

public interface MyList<E> extends java.lang.Iterable<E> { 
    /** Add a new element at the end of this list */ 
    public void add(E e); 

    /** Add a new element at the specified index in this list */ 
    public void add(int index, E e); 

    /** Clear the list */ 
    public void clear(); 

    /** Return true if this list contains the element */ 
    public boolean contains(E e); 

    /** Return the element from this list at the specified index */ 
    public E get(int index); 

    /** Return the index of the first matching element in this list. 
    * Return -1 if no match. */ 
    public int indexOf(E e); 

    /** Return true if this list contains no elements */ 
    public boolean isEmpty(); 

    /** Return the index of the last matching element in this list 
    * Return -1 if no match. */ 
    public int lastIndexOf(E e); 

    /** Remove the first occurrence of the element o from this list. 
    * Shift any subsequent elements to the left. 
    * Return true if the element is removed. */ 
    public boolean remove(E e); 

    /** Remove the element at the specified position in this list 
    * Shift any subsequent elements to the left. 
    * Return the element that was removed from the list. */ 
    public E remove(int index); 

    /** Replace the element at the specified position in this list 
    * with the specified element and returns the new set. */ 
    public Object set(int index, E e); 

    /** Return the number of elements in this list */ 
    public int size(); 

    /** Adds the elements in otherList to this list. 
    * Returns true if this list changed as a result of the call */ 
    public boolean addAll(MyList<E> otherList); 

    /** Removes all the elements in otherList from this list 
    * Returns true if this list changed as a result of the call */ 
    public boolean removeAll(MyList<E> otherList); 

    /** Retains the elements in this list that are also in otherList 
    * Returns true if this list changed as a result of the call */ 
    public boolean retainAll(MyList<E> otherList); 

    /** Return an iterator for the list */ 
    public java.util.Iterator<E> iterator(); 
} 

Answer 1

如果元素不是Comparable你只能搜索在參數不存在列表的元素。

public boolean retainAll(MyList<E> otherList) { 
    boolean changed = false; 
    for (int i = size() - 1; i >= 0; i--) { 
     Object obj = get(i); 
     if (!otherList.contains(obj)) { 
      remove(i); 
      changed = true; 
     } 
    } 
    return changed; 
} 

注：該算法爲O完成（N^2），如果你有相當的列表，你可以去O（N日誌（N））

第二個音符：不要使用迭代器來循環列表，因爲對列表內容的更改可能會拋出異常。

---

評點建議編輯由沙特：沒有必要更新size。這必須通過方法remove完成。