확장을 매 원소마다 하는 게 아니라 일정 크기를 잡아놓고 초과하려 할 때 한 번에 확 늘리는 식이라 그에 대한 오버헤드는 작다고 봅니다. 링크드 리스트가 오히려 포인터로 계속 관리를 해야 하기에 더 느리고 공간을 많이 먹지 않을까 싶네요.

흐음.. ArrayList와 같은 동적 배열은

grow rate라는 게 있어서요. 예를 들어서 기존에 1000이라는 공간이 할당되어 있을 때

grow rate가 1.5라면 1500으로 확장되고요.

2라면 2000으로 확장되죠.

아마 걱정하는 부분은 동적 배열에서 add 연산 한 번 수행할 때 마다 드는 시간이 O(n)이 되지 않겠느냐.. 인 거 같은데요.

초과할 때마다 공간이 하나씩 늘게 하면 그럴 수도 있겠다만..

내부적으로 그러지 않으니까 너무 걱정 안 하셔도 되고요.

List가 효과적인 경우에는 (더블 링크드 리스트)

중간에 있는 원소를 삭제하거나, 중간에 원소를 추가해야 할 때가 있겠네요.