public class ArrayList implements List{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity){
super();
this.elementData = new Object[initialCapacity];
}
public ArrayList(){
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 최대 array í¬ê¸°
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity){
int oldCapacity = elementData.length;
// ì–¼ë ˆ í¬ê¸°ì— 2배를 ëŠ˜ë ¤ì¤Œ
int newCapacity = oldCapacity + (oldCapacity >> 1);
if(newCapacity-minCapacity < 0){
newCapacity = minCapacity;
}
// 최대 ARRAY í¬ê¸°ë¥¼ 넘ìŒ
if(newCapacity-MAX_ARRAY_SIZE > 0){
newCapacity = MAX_ARRAY_SIZE;
}
// í¬ê¸°ë¥¼ ëŠ˜ë ¤ì„œ Array copy
// 그냥 java.util ì— Arrays í´ëž˜ìŠ¤ 사용
elementData = java.util.Arrays.copyOf(elementData,newCapacity);
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
return elementData(index);
}
public boolean add(E e){
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public E remove(int index) {
E oldValue = 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){
if (o == null){
for(int i=0; i < size; i++){
if(elementData[i] == null){
fastRemove(i);
return true;
}
}
}else{
for(int i=0; i < size; i++){
// LinkedList ì—서는 hashCode비êµ(==) 하지만
// ArrayList ì—서는 ë‚´ìš©ì´ ê°™ì€ì§€(equals) 를 한다.
if(o.equals(elementData[i])){
fastRemove(i);
return true;
}
}
}
return false;
}
private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0){
// ì›ë³¸,ì½ì–´ì˜¬ë¶€ë¶„,ë³µì‚¬í• ëŒ€ìƒ,ì¹´í”¼í• ìœ„ì¹˜,ì–¼ë§ˆë§Œí¼ ì½ì–´ì˜¬ì§€
// elementData를 index+1 부터 numMoved ë§Œí¼ ì½ì–´ì„œ index ë¡œ elementData ì— ì¹´í”¼
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
}
public Iterator iterator(){
return new ListItr(0);
}
private class ListItr implements ListIterator {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
public ListItr(int index){
cursor = index;
}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
int i = cursor;
if (i >= size)
{
}
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
{
}
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
{
}
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
}
}
}