가장 심플하고 어려운 질문. 사람마다 전부 다 다른 대답을 한다. (그러므로 부족하거나 보충할만한 내용이 있다면 댓글을 달아주세요 😉)
배열과 리스트중에 무조건 좋은 쪽이 존재하진 않는다.
프로그래밍에서 많은 선택지들은 트레이드-오프 관계를 띈다. 성능 - 안정성 같은 관계가 하나의 예시이다. 하나를 고르면 하나는 적당히 포기해야 한다.
배열 vs 리스트도 비슷하다. 배열의 장점, 리스트의 장점 중 어느것을 고르고 포기할것인지 선택해야 한다.
어떤 상황에서 어떠한 데이터를 다루냐에 따라 유리한 선택지가 달라지므로 유리한 선택지를 결정하기 위해선 각 기능들의 차이와 장단점을 이해하고 있어야 한다.
어느쪽이 이기냐 라는 질문에서 ”배열과 연결리스트의 장단점과 차이” 라는 질문으로 바꾸고 차이점을 나열해보자.
가장 먼저 접근할 수 있는 차이는 시간복잡도일 것이다.
랜덤 엑세스
액세스가 많은 상황의 경우 배열을, 삽입/제거가 많은 경우는 리스트를 선택해야 한다.
시간복잡도가 같더라도 여러 요인에 따라 성능이 몇 배씩 차이가 난다.
예를 들어 배열과 리스트의 원소 삽입/삭제 에서 배열은 O(n), 리스트는 O(1) 의 시간복잡도를 가지지만 원소의 개수가 15개 정도 이하인 경우에는 배열이 훨씬 빠르다.
배열은 추가적인 메타데이터를 거의 필요로 하지 않는다, 하지만 리스트는 각 노드마다 next같은 포인터가 필요하다. 즉 리스트는 최대 2~3배의 더 많은 메모리를 소비해야 한다.
배열의 메모리 배치는 연속적이다. (바로 다음 주소에 다음 값이 존재함)
하지만 리스트의 메모리 배치는 비연속적이다. (다음 값이 어느 위치에 존재할지 알 수 없음)
메모리 배치가 연속적이고, 비연속적이면 뭐가 다를까?
위는 cpu-z 라는 cpu의 스펙을 보는 프로그램이다. Cache의 descript를 보면 “64-byte line size” 라는 글귀를 볼 수 있다.
이것이 캐시 라인 이라고 부르는 것인데, 저 cpu의 캐시는 데이터를 쓰고 읽어올 때 1바이트, 4바이트씩 읽고 쓰는것이 아닌 무조건 64바이트씩 쓰고 읽는다는 것이다.
거의 대부분 개인용 cpu가 저렇다.
다시 메모리 연속성으로 돌아와서, 메모리가 연속적으로 배치되어 있다면, 무엇이 좋을까?
만약 내가 4바이트 int로 된 배열을 사용한다고 생각해보자. arr[0] 칸을 읽는다. cpu는 한 칸인 4바이트를 캐시에서 가져와 읽을 것이다. 하지만 캐시는 4바이트만 읽는것이 아니다. 캐시라인 범위인 64바이트, 즉 arr[0] ~ arr[15] 범위를 모조리 한 번에 읽는다.
배열은 한 번 읽으면 16칸을 한 번에 읽고, 리스트는 비-연속적이므로 한 번 읽으면 훨씬 적은 칸을 읽는다.
배열과 리스트의 시간복잡도가 같다고 하더라도 메모리가 연속적인 배열이 훨씬 빠르게 되는 것이다.
비연속적인 메모리는 접근 패턴이 일정하지 않다. 연속적인 배열은 첫 칸부터 마지막 칸 까지 순회한다면 접근 패턴이 일정하다.
현대 Hardware Cache Prefetcher는 메모리 접근 패턴이 일정하다면 다음 접근할 메모리를 예측해 미리 가져올 수 있다.
연결리스트는 하나의 문제가 더 있다. 노드 하나 당 malloc과 free를 수행해야 하는 것이다.