3-3. 직접 구현하는 배열 리스트(2)

배열리스트 구현 - 제네릭 사용 1

---

• 앞서 만든 MyArrayList는 Object를 입력받기 때문에 아무 데이터나 입력할 수 있고, 또 결과로 Object를 반환함
• 따라서 필요한 경우 다운 캐스팅을 해야하고, 또 타입 안전성이 떨어지는 단점이 있음

package collection.array;

public class MyArrayListV3BadMain {
 	
    public static void main(String[] args) {
 		MyArrayListV3 numberList = new MyArrayListV3();
        
 		// 숫자만 입력 하기를 기대
        numberList.add(1);
        numberList.add(2);
        numberList.add("문자3"); //문자를 입력
		System.out.println(numberList);
        
 		// Object를 반환하므로 다운 캐스팅 필요
		Integer num1 = (Integer) numberList.get(0);
 		Integer num2 = (Integer) numberList.get(1);
        
 		// ClassCastException 발생, 문자를 Integer로 캐스팅
		Integer num3 = (Integer) numberList.get(2);
        
    }
}

• numberList에는 숫자만 입력하기를 기대했지만, Object를 받아서 저장하기 때문에 자바의 모든 타입을 다 저장할 수 있음

  • 따라서 숫자를 입력하다가 실수로 문자를 입력해도 아무런 문제가 되지 않음

• 값을 꺼낼 때 Object를 반환하기 때문에, 원래 입력한 타입으로 받으려면 다운 캐스팅을 해야 함

  • 이때 입력한 데이터 타입을 정확하게 알고 있지 않으면 예외가 발생함
  • 지금처럼 중간에 문자가 들어가면 문제가 될 수 있음

• 참고로 하나의 자료 구조에 숫자와 문자처럼 서로 관계없는 여러 데이터 타입을 섞어서 보관하는 일은 거의 없음
  • 일반적으로 같은 데이터 타입을 보관하고 관리함

• 제네릭을 도입하면 타입 안전성을 확보하면서 이런 문제를 한 번에 해결할 수 있음
  • 제네릭은 자료를 보관하는 자료 구조에 가장 어울림

package collection.array;

import java.util.Arrays;

public class MyArrayListV4<E> {

 	private static final int DEFAULT_CAPACITY = 5;
    
 	private Object[] elementData;
 	private int size = 0;

 	public MyArrayListV4() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

 	public MyArrayListV4(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

 	public int size() {
 		return size;
    }

 	public void add(E e) {
 		if (size == elementData.length) {
			grow();
        }
        elementData[size] = e;
        size++;
    }
    
 	public void add(int index, E e) {
 		if (size == elementData.length) {
 			grow();
        }
 		shiftRightFrom(index);
        elementData[index] = e;
        size++;
    }

 	//요소의 마지막부터 index까지 오른쪽으로 밀기
	private void shiftRightFrom(int index) {
 		for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
    	}
	}

    @SuppressWarnings("unchecked")
 	public E get(int index) {
 		return (E) elementData[index];
    }

 	public E set(int index, E element) {
 		E oldValue = get(index);
        elementData[index] = element;
 		return oldValue;
    }
    
 	public E remove(int index) {
		E oldValue = get(index);
 		shiftLeftFrom(index);
        
        size--;
        elementData[size] = null;
 		return oldValue;
    }

 	//요소의 index부터 마지막까지 왼쪽으로 밀기
	private void shiftLeftFrom(int index) {
 		for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
    }
    
	public int indexOf(E o) {
 		for (int i = 0; i < size; i++) {
 			if (o.equals(elementData[i])) {
 				return i;
            }
        }
 		return -1;
    }
    
 	private void grow() {
 		int oldCapacity = elementData.length;
 		int newCapacity = oldCapacity * 2;
          elementData = Arrays.copyOf(elementData, newCapacity);
    }

    @Override
 	public String toString() {
 		return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" + 
				size + ", capacity=" + elementData.length;
    }
        
}

• MyArrayListV4<E>로 제네릭 타입을 선언함
• Object로 입력받고 출력했던 곳에 타입 매개변수 E로 변경함
  • Object[] elementData는 그대로 유지함
  • 이 부분은 바로 뒤에서 추가로 설명할 예정

package collection.array;

public class MyArrayListV4Main {

 	public static void main(String[] args) {
    
 		MyArrayListV4<String> stringList = new MyArrayListV4<>();
        stringList.add("a");
        stringList.add("b");
        stringList.add("c");
 		String string = stringList.get(0);
 		System.out.println("string = " + string);
        
 		MyArrayListV4<Integer> intList = new MyArrayListV4<>();
        intList.add(1);
        intList.add(2);
        intList.add(3);
 		Integer integer = intList.get(0);
 		System.out.println("integer = " + integer);
        
    }
    
}

실행결과

string = a
integer = 1

• 이제 stringList에는 String 문자열만 보관하고 조회하고, intList에는 Integer 숫자만 보관하고 조회할 수 있음

• 다른 타입의 값을 저장하면 컴파일 오류가 발생함

• 추가로 값을 조회할 때도 위험한 다운 캐스팅 없이 지정한 타입으로 안전하게 조회할 수 있음

• 제네릭을 사용한 덕분에 타입 인자로 지정한 타입으로만 안전하게 데이털르 저장하고, 조회할 수 있게 됨

• 제네릭의 도움으로 타입 안전성이 높은 자료 구조를 만들 수 있었음

2. 배열리스트 구현 - 제네릭 사용 2

---

Object 배열을 사용한 이유

Object[] elementData을 그대로 사용하는 이유

• 제네릭은 런타임에 이레이저에 의해 타입 정보가 사라짐

  • 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없음
  • 제네릭을 기반으로 배열을 생성하는 다음코드는 작동하지 않고, 컴파일 오류가 발생함
  • 참고로 이것이 자바가 제공하는 제네릭의 한계임
  • new E[DEFAULT_CAPACITY]

• 대신에 다음과 같이 모든 데이터를 담을 수 있는 Object를 그대로 사용해야 함

  • new Object[DEFAULT_CAPACITY]

Object[]을 생성해서 사용해도 문제가 없는지 확인

• new MyArrayListV4<String>을 사용한 경우 E가 다음과 같이 처리됨

제네릭 타입 인자 적용 전

Object[] elementData;

void add(E e) {
   elementData[size] = e;
    ...
}

E get(int index) {
 	return (E) elementData[index];
}

제네릭 타입 인자 적용 후

Object[] elementData;

void add(String e) {
   elementData[size] = e;
   ...
}
String get(int index) {
   return (String) elementData[index];
}

• elementData[]에 데이터를 보관하는 add(E e) 메서드를 보면, E 타입으로 데이터를 입력함
  • elementData[]에 데이터를 조회하는 get() 메서드를 보면, 보관할 때와 같은 E 타입으로 데이터를 다운 캐스팅해서 반환함
• 따라서 배열의 모든 데이터는 E 타입으로 보관됨
  • 그리고 get()으로 배열에서 데이터를 꺼낼 때 (E)로 다운 캐스팅해도 보관한 E 타입으로 다운 캐스팅 하기 때문에 아무런 문제가 되지 않음

더 구체적인 예시

• MyArrayListV4를 생성할 때 타입 매개변수 E를 String으로 지정했다면 elementData에는 항상 String이 저장됨

  • add(String e)에서 배열의 모든 데이터는 String 타입으로 보관됨

  • get()에서 데이터를 꺼낼 때 항상 (String)으로 다운 캐스팅 함

  • 저장한 String 타입으로 다운캐스팅 하기 때문에 아무런 문제가 되지 않음

Object는 모든 데이터를 담을 수 있기 때문에 데이터를 담는데는 아무런 문제가 없음

• 다만 데이터를 조회할 때 문제가 될 수 있음
• 이때는 조회한 Object 타입을 지정한 타입 매개변수로 다운캐스팅 해줌

public E get(int index) {
   return (E) elementData[index];
}

• elemetData[index]로 조회한 결과는 Object임
  • 따라서 (E) Object가 됨
• 이렇게 해도 문제가 없음
  • 우리가 add(E e)를 통해 Object elementData[]에 보관한 모든 데이터는 E타입이라는 것이 확실하기 때문
• E가 String인 경우 (String) Object가 됨

정리

---

• 생성자에는 제네릭의 타입 매개변수를 사용할 수 없는 한계가 있음

• 따라서 배열을 생성할 때 대안으로 Object 배열을 사용해야 함

• 하지만 제네릭이 리스트의 데이터를 입력 받고 반환하는 곳의 타입을 고정해줌

• 따라서 고정된 타입으로 Object 배열에 데이터를 보관하고, 또 데이터를 꺼낼 때도 같은 고정된 타입으로 안전하게 다운 캐스팅 할 수 있음

MyArrayList의 단점

배열을 사용한 리스트인 MyArrayList의 단점

• 정확한 크기를 미리 알지 못하면 메모리가 낭비됨
• 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 잇음
• 데이터를 중간에 추가하거나 삭제할 때 비효율적임
  • 이 경우 데이터를 한 칸씩 밀어야 함
  • 이것은 O(n)으로 성능이 좋지 않음
  • 만약 데이터의 크기가 1,000,000건이라면 최악의 경우 데이터를 추가할 때마다 1,000,000건의 데이터를 밀어야 함

ArrayList의 빅오 정리

• 데이터 추가
  • 마지막에 추가 : O(1)
  • 앞, 중간에 추가 : O(n)
• 데이터 삭제
  • 마지막에 삭제 : O(1)
  • 앞 중간에 삭제 : O(n)
• 인덱스 조회 : O(1)
• 데이터 검색 : O(n)

• 배열 리스트는 순서대로 마지막에 데이터를 추가하거나 삭제할 때는 성능이 좋지만, 앞이나 중간에 데이터를 추가하거나 삭제할 때는 성능이 좋지 않음
• 다음 시간에는 이런 단점을 해결한 자료 구조인 LinkedList에 대한 강의 진행할 예정

강의 출처 : 김영한의 실전 자바 - 중급 2편