继承结构
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
写在前面的一些方法说明
-
Arrays.copyOf(Object[] original, int newLength)，往往一段代码胜过千言万语
-
移位
>>、<<
int a = 8; // 二进制：··· 0000 1000
a = a >> 1; // 二进制：··· 0000 0100
System.out.println(a) // 4
a = a << 2; // 二进制：··· 0001 0000
System.out.println(a) // 16
-
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
-
private void grow(int minCapacity)扩容
private void grow(int minCapacity) {
// 当前数组的容量
int oldCapacity = elementData.length;
// 新容量 = 老容量 + 老容量/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量小于需要申请的容量
if (newCapacity - minCapacity < 0)
// 新容量=需要申请的容量
newCapacity = minCapacity;
// 如果新容量大于MAX_ARRAY_SIZE(= Integer.MAX_VALUE - 8)
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 新容量=计算出的最大容量
newCapacity = hugeCapacity(minCapacity);
// 数组扩容到新容量
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 需要申请的容量小于0 抛异常
throw new OutOfMemoryError();
// 需要申请的容量大于最大容量？是->返回int最大值，否->返回int最大值-8
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
-
private void ensureCapacityInternal(int minCapacity)，如果使用new ArrayList(),当添加第一个元素时，其实容器内已经申请了length=10的容量，添加的元素如果<10,就造成了资源的浪费。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 取最大值作为需要申请的容量
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果申请的容量大于目前容器的容量，去扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
一、增
public boolean add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element)
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
// 把index位置后面的元素全部后移一位
System.arraycopy(elementData, index, elementData, index + 1,size - index);
// index位置赋值新元素
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> c)
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// a=[1,2,3,4]
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
// 匀出位置
// index = 1
// old element = [5,6,7,null,null,null,null]
// new element = [5,6,7,null,null,6,7]
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 塞进去 new element = [5,1,2,3,4,6,7]
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
二、删
-
public E remove(int index),return 移除的那个元素
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o)
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
-
public boolean removeAll(Collection<?> c) 删除c中相同的元素、public boolean retainAll(Collection<?> c) 保留c中相同的元素，相当于取交集
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* @param complement true 保留相同元素 false 保留不同元素
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,elementData, w,size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
三、改
public E set(int index, E element)
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
-
public void replaceAll(UnaryOperator<E> operator)根据定义的规则进行单个元素的转换
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
// 例
public static void main(String[] args) {
ArraysList<String> list = new ArraysList<>();
list.add("1");
list.add("2");
list.add("3");
list.replaceAll(new UnaryOperator<String>() {
@Override
public String apply(String s) {
return s.equals("1") ? "2" : s;
}
});
for (String o : list) {
System.out.print(o);
System.out.print(",");
}
// 输出：[2,2,3]
}
}
四、查
-
public int indexOf(Object o)正序遍历数组比较元素，返回索引
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public boolean contains(Object o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
-
public int lastIndexOf(Object o)倒序遍历数组比较元素，返回索引
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
-
public E get(int index)索引取数组元素
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
网友评论