자료 구조 (2) : 배열(Array, List)

배열

동일한 데이터 타입을 가지는 값을 순서대로 저장하는 자료 구조

 

• 종류(Java 기준)
  • 정적 배열(Array) : 고정된 크기를 가짐
  • 동적 배열(List) : 변경 가능한 크기를 가짐
• 특징
  • 0 ~ n-1까지의 인덱스 사용
  • 연속된 메모리 공간 사용
  •  데이터 타입의 크기와 인덱스를 사용해서 데이터에 O(1)으로 접근 가능

* 데이터 조회 예시

• 배열의 시작 주소가 1000이고 int의 크기는 4바이트 배열은 [10, 20, 30]이라 가정
• 10, 20, 30 각각은 4바이트 공간을 차지(10 : 1000~1003, 20 : 1004~1007, 30 : 1008 ~ 1011)
• 시작 주소 + (인덱스 * 데이터 크기)로 바로 조회 가능(인덱스 2의 값은 1000 + ( 2 * 4) = 1008)

 

• 사용 상황
  
  • 데이터를 순서대로 저장
  • 데이터의 중복을 허용
  • 인덱스를 통해 빠른 조회가 필요
• 시간 복잡도

	Array	List
조회	O(1)	O(1)
검색	O(n)	O(n)
삽입	불가능	O(n)
추가(끝에 삽입)	불가능	O(1)
삭제	불가능	O(n)

 

* 삽입, 추가, 삭제 시 Array는 새로운 크기의 Array를 만들고 복사해서 사용

 

• Array 예시

Index	0	1	2	3	4
Value	11	12	13	14	15

• List 예시

Index	0	1	2	3
Value	11	12	13

 

14 추가 시 비어있는 3 인덱스 공간에 저장

15 추가 시 비어있는 공간이 없으므로 배열의 크기를 2배로 늘린 후 값을 저장

Index	0	1	2	3	4	5	6	7
Value	11	12	13	14	15

 

List 구현 예시

 

public class IntArray {

  private static final int DEFAULT_CAPACITY = 16; // 초기 크기를 16으로 설정 

  public int[] arr;
  public int len = 0;
  private int capacity = 0;

  public IntArray() {
    this(DEFAULT_CAP);
  }

  public IntArray(int capacity) {
    if (capacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + capacity);
    this.capacity = capacity;
    arr = new int[capacity];
  }

  public IntArray(int[] array) {
    if (array == null) throw new IllegalArgumentException("Array cannot be null");
    arr = java.util.Arrays.copyOf(array, array.length);
    capacity = len = array.length;
  }

  public int size() {
    return len;
  }

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

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

  public void set(int index, int value) {
    arr[index] = value;
  }
  
  public int indexOf(int value) {
  	for (int i = 0; i < len; i++) {
    	if (arr[i] == value) return i;
    }
    return -1;
  }

 public boolean contains(int value) {
 	return indexOf(value) != -1;
 }

  public void add(int value) {
    if (len + 1 >= capacity) {
      if (capacity == 0) capacity = 1;
      else capacity *= 2; // 크기를 초과할 시 크기를 2배로 증가
      arr = java.util.Arrays.copyOf(arr, capacity);
    }
    arr[len++] = value;
  }

  public void removeAt(int index) {
    System.arraycopy(arr, index + 1, arr, index, len - index - 1);
    --len;
    --capacity;
  }

  public boolean remove(int value) {
    for (int i = 0; i < len; i++) {
      if (arr[i] == value) {
        removeAt(i);
        return true;
      }
    }
    return false;
  }
}