배열 표현 방식의 공간 낭비 문제
배열(Array)은 크기가 고정된 자료구조이기 때문에, 저장할 데이터의 양이 시간에 따라 계속 변하는 경우에는 공간을 매우 비효율적으로 사용하게 됩니다. 데이터를 저장하기 위해 미리 넉넉한 크기의 배열을 할당해 두어야 하며, 이 과정에서 실제로 필요한 용량보다 더 많은 메모리가 낭비될 수 있습니다.
배열 두 배 확장 기법의 한계
배열이 가득 찼을 때 크기를 늘리는 대표적인 방법은 배열 두 배 확장(Array Doubling) 기법입니다. 예를 들어 현재 배열의 크기가 8192이고 이 배열이 꽉 차 있다면, 크기가 16384인 새 배열을 생성한 뒤 기존 배열의 8192개 요소를 모두 새 배열로 복사하고, 마지막으로 기존 배열을 해제(deallocate)합니다.
그런데 여기서 중요한 문제가 발생합니다. 기존 배열을 해제하기 전까지는 크기가 16384인 새 배열과 크기가 8192인 기존 배열이 동시에 메모리를 점유하고 있으므로, 순간적으로 8192의 약 세 배에 해당하는 메모리가 필요하게 됩니다. 즉, 확장 작업 자체가 상당한 메모리 부담을 유발하는 셈입니다.
여러 리스트가 하나의 배열을 공유하는 방식
이러한 낭비를 줄이는 대안으로, 여러 개의 리스트를 저장할 때 각 리스트마다 새로운 배열을 따로 만드는 대신 하나의 커다란 배열을 여러 리스트가 함께 공유하는 방법을 사용할 수 있습니다. 이렇게 하면 배열 확장 시 발생하는 중복 메모리 점유를 줄이고, 전체적인 메모리 활용 효율을 높일 수 있습니다.
단일 배열 다중 리스트의 단점
물론 이 방식이 항상 좋은 것은 아닙니다. 하나의 배열에 여러 리스트를 담으면 메모리는 절약되지만 다음과 같은 문제점이 있습니다.
- 삽입 연산의 비용 증가: 특정 리스트에 새로운 요소를 삽입할 때 공간 확보를 위해 다른 리스트에 속한 요소들을 이동시켜야 할 수 있습니다. 이로 인해 삽입 연산이 훨씬 비싸지게 됩니다.
- 구현의 복잡성: 여러 리스트의 경계와 요소 위치를 관리해야 하므로, 일반적인 배열 표현 방식보다 구현 난이도가 상당히 높아집니다.
결론적으로, 단일 배열에 여러 리스트를 저장하는 방식은 메모리 효율이라는 분명한 장점이 있지만, 삽입 성능 저하와 구현 복잡성이라는 trade-off를 반드시 고려해야 합니다. 데이터의 변경 빈도와 연산 패턴을 분석하여 상황에 맞는 표현 방식을 선택하는 것이 중요합니다.