1 
public boolean addAll(int i, Collection<? extends T> c) {
   for (T x : c)
   add(i++, x);
   return true;
}

List 方法 addAll(i,c) 将集合 c 的所有元素插入到位置 i 的列表中。这需要很多时间。有什么方法可以更快地实施吗？请问有什么想法吗？谢谢

下面是arrayDeque的实现：

public class ArrayDeque extends AbstractList { /** * 存储在这个队列中的元素的类 */ protected Factory f;

/**
 * Array used to store elements
 */
protected T[] a;

/**
 * Index of next element to de-queue
 */
protected int j;

/**
 * Number of elements in the queue
 */
protected int n;

/**
 * Grow the internal array
 */
protected void resize() {
    T[] b = f.newArray(Math.max(2*n,1));
    for (int k = 0; k < n; k++) 
        b[k] = a[(j+k) % a.length];
    a = b;
    j = 0;
}

/**
 * Constructor
 */
public ArrayDeque(Class<T> t) {
    f = new Factory<T>(t);
    a = f.newArray(1);
    j = 0;
    n = 0;
}

public int size() {
    return n;
}

public T get(int i) {
    if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
    return a[(j+i)%a.length];
}

public T set(int i, T x) {
    if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
    T y = a[(j+i)%a.length];
    a[(j+i)%a.length] = x;
    return y;
}

public void add(int i, T x) {
    if (i < 0 || i > n) throw new IndexOutOfBoundsException();
    if (n+1 > a.length) resize();
    if (i < n/2) {  // shift a[0],..,a[i-1] left one position
        j = (j == 0) ? a.length - 1 : j - 1; // (j-1) mod a.length
        for (int k = 0; k <= i-1; k++)
            a[(j+k)%a.length] = a[(j+k+1)%a.length];
    } else {        // shift a[i],..,a[n-1] right one position
        for (int k = n; k > i; k--)
            a[(j+k)%a.length] = a[(j+k-1)%a.length];
    }
    a[(j+i)%a.length] = x;
    n++;
}

public T remove(int i) {
    if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
    T x = a[(j+i)%a.length];
    if (i < n/2) {  // shift a[0],..,[i-1] right one position
        for (int k = i; k > 0; k--)
            a[(j+k)%a.length] = a[(j+k-1)%a.length];
        j = (j + 1) % a.length;
    } else {        // shift a[i+1],..,a[n-1] left one position
        for (int k = i; k < n-1; k++)
            a[(j+k)%a.length] = a[(j+k+1)%a.length];
    }
    n--;
    if (3*n < a.length) resize();
    return x;
}

public void clear() {
    n = 0;
    resize();
}

}

4

1 回答 1

2

与其一次添加一项，不如考虑执行以下操作：

  • 确保数据结构中有足够的空间用于所有新元素。
  • 将位置上的所有元素i向下移动一个空格，该空格数等于将要添加的新元素的数量。这可以在 O(1 + n - i) 时间内完成，因为每个项目只移动一次。
  • 编写要插入到新位置的元素。

总的来说，这需要时间 O(n - i + k + 1)，其中 n 是原始数据结构中的元素数，i 是要插入的位置，k 是插入的新元素数。关键优势是您可以一次完成所有换档，而不是做很多很多较小的换档。

希望这可以帮助！

于 2013-10-01T02:17:20.020 回答