dynamic array resizing에 대해서.

알고리즘쪽을 파다보니 재미있는게, 예전에 알았던 자료 구조도 구현 방식등에 대해서 다시 되짚어 볼 수 있는게 좋은데. (그간 생각하던 구현 방식과 다른 방식도 종종 나와서.)

보통 메모리 문제 때문에 불확실한 데이타 크기를 가지는 데이타 구조는 LinkedList를 사용하는게 유리하다고 생각했는데, 내용중에, 배열을 사용하고, 배열이 다 차면 그크기를 늘리는 (새롭게 더 큰 배열을 만들어서 기존 배열 내용을 복사해서 대처 하는것) 방식 (Array Resize)를 봤다.  일반적인 방식이기는 하지만 메모리 소모량이나 배열 복사 속도 때문에 그다지 바람직하다고 생각 안하고 있었는데, JDK내의 Map 클래스의 구현 부분을 보니, 실제로 Map 클래스에서도  array resize를 사용하고 있다.

(출처 : http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.addEntry%28int%2Cjava.lang.Object%2Cjava.lang.Object%2Cint%29 )

꽉 막혀서 생각할 것이 아니라, 이런 방식도 융통성 있게 고려를 해봐야겠다.