Array(또는 리스트)는 가장 많이 사용하는 데이터 구조 중 하나이다.
그래서 내부 구현 방법을 알고 써야 써도 괜찮은 상황과 더 효율적인 다른 구조를 써야할 상황을 구분 가능하다.
기본 배열(Array)는 초기화할 때 크기가 지정되고 그 크기로 고정된다.
데이터 크기를 미리 알기 어려운 상황도 많아 미리 크기를 지정하는 것은 사실 불편하다.
Resizing Array
- 저장된 데이터 양에 따라 크기를 자동 조정하는 자료구조
- 기본 배열처럼 index로 원소 접근 가능
내부적으로 구현된 방법:
(1) Linked List: 새로운 노드 추가
(2) 기본 배열 사용: 미리 크기 N의 배열 준비, 더 많은 공간이 필요하면 더 큰 배열 만들어 기존 데이터 복사
기본 배열을 사용하여 구현하는 경우, 연속된 메모리를 사용하므로 다음 노드의 위치가 명확하여 이에 대한 레퍼런스를 저장할 필요가 없고, 디스크 - 메모리 - 캐시로 읽어올 때 모든 노드가 메모리에서 인접해 있으므로 같은 블록에 속해 읽어오는 시간이 빠르다.
그리고 Index가 있으면 임의 위치 원소라도 저장된 위치 바로 계산해 빠르게 접근 가능하다.
가끔 새 배열을 만들고 기존 원소를 복사할 필요가 있으나 평균적으로 원소를 추가하는 것 역시 상수시간에 가능하다.
임의 위치의 원소를 추가/삭제하는 것은 Index 삭제할 위치 뒤의 원소를 한칸씩 이동시켜야 하므로 O(N)이다.
기존 배열 사용한 resizing array 구현 방법에서 Resize 하는 비용은 크지 않나?
원소가 가득 찼을 때 2배 크기 배열 만들고, 기존 원소 복사한다고 가정
새 배열 만드는 비용: O(1)
기존 원소 복사 비용: 1 + 2 + 4 + .... + N = 2 * N - 1 = O(N)
기존 배열 사용한 resizing array 구현 방법 Detail: 초기화 & Doubling
원소 추가: 가득 차면 2N 크기 배열 만들어 기존 원소 복사
원소 삭제: 원소 수가 N/4개 되면 불필요한 메모리 낭비를 줄이기 위하여 N/2 크기 배열 만들어 기존 원소 복사
크기 축소 임계치를 N/2가 아닌 N/4로 정한 이유:
N/2로 줄어들었다가 다시 + 1되면 또 재할당해야하므로 재할당을 반복해서 할 일이 생길 수 있게 되므로 이러한 일을 방지하기 위해 N/4로 정함
Resizing Array 보다 다른 자료구조가 더 효율적인 경우
-
Queue(FIFO) 필요한 경우
Array 가장 뒤에 추가 + Array 가장 앞 원소 삭제 기능 필요(O(N)이 아닌 방법 필요)
임의 위치 원소를 index로 접근하는 기능은 불필요 -
Resizing array를 queue로 사용하면
추가: O(1)
삭제: O(N) -
Linked List로 구현한 Queue 전용 클래스 사용하면 pop비용 O(1)
- Stack의 경우는 pop() 과 추가 모두 O(1)
