배열 vs 연결리스트

메모리에 놓이는 방식이 다르고, 거기서 모든 차이가 나옵니다.

연속이라는 성질이 O(1) 접근을 주고, 그 대가로 중간 삽입에 시프트를 요구합니다. 연결이라는 성질은 그 반대입니다.

흔한 실수: 표만 외워 "삽입이 많으면 연결 리스트"라고 답하는 것. 실무에서는 캐시 효율 때문에 수천 개 이하에서는 배열이 이기는 경우가 많습니다.

접근과 수정이 정반대입니다.

배열은 시작 주소에 인덱스를 곱해 더하면 위치가 나오므로 한 번에 갑니다. 대신 중간에 넣으면 뒤를 모두 밀어야 합니다. 연결 리스트는 반대로 포인터만 바꾸면 되지만, 그 자리에 가려면 처음부터 세어 가야 합니다.

흔한 실수: 연결 리스트의 중간 삽입을 그냥 O(1)이라고 답하는 것. 노드를 이미 들고 있을 때만 O(1)이고, 인덱스로 찾아야 하면 탐색 O(n)이 먼저 붙습니다.

연속 배치를 유지해야 하므로 빈 자리를 만들려면 뒤쪽을 모두 밀어야 합니다.

[10, 20, 30, 40] 의 앞에 5 를 넣는다
  40, 30, 20, 10 을 한 칸씩 뒤로 옮긴다   <- n번
  0번 자리에 5 를 넣는다

옮기는 개수가 삽입 위치에 따라 달라집니다. 맨 뒤는 0번, 맨 앞은 n번이고 평균은 n의 절반입니다. 상수를 버리면 O(n)입니다.

흔한 실수: 맨 뒤 추가도 O(n)이라고 답하는 것. 여유 공간이 있으면 O(1)이고, 용량이 찼을 때만 새 배열로 복사해 O(n)입니다. 확장이 배수로 일어나므로 여러 번 추가하면 분할상환 O(1)이 됩니다.

방금 접근한 데이터와 그 주변을 곧 다시 쓸 가능성이 높다는 성질입니다. CPU는 이 성질을 믿고 64바이트 캐시 라인 단위로 미리 가져옵니다.

배열은 공간 지역성이 좋습니다. int 배열이면 라인 하나에 16개가 함께 실려 와서, 순회 중 캐시 미스가 16번에 한 번만 납니다. 연결 리스트는 노드가 흩어져 있어 접근마다 새 라인을 가져올 수 있습니다.

L1 캐시는 1ns 안팎이고 메모리는 100ns 안팎이라 이 차이가 수십 배로 벌어집니다.

흔한 실수: 지역성을 메모리 사용량 문제로 설명하는 것. 얼마나 쓰느냐가 아니라 다음에 쓸 것이 이미 캐시에 있느냐의 문제입니다.

삭제할 노드를 이미 가리키고 있고, 그 삭제가 잦은 경우입니다.

공통점은 인덱스로 찾지 않는다는 것입니다. 인덱스로 찾아야 하면 탐색 O(n)이 붙어 이득이 사라집니다.

흔한 실수: "삽입과 삭제가 많으면 연결 리스트"로 뭉뚱그리는 것. 위치를 어떻게 얻는지가 실제 기준입니다.

읽기가 많으면 ArrayList, 앞쪽 삽입과 삭제가 많으면 LinkedList가 이론상 유리합니다. 실무에서는 대부분 ArrayList를 씁니다.

LinkedList가 이기는 구간이 좁은 이유는 노드마다 포인터 두 개와 객체 헤더가 붙어 메모리를 3배 안팎 쓰고, 노드가 흩어져 있어 순회할 때마다 캐시 미스가 나기 때문입니다.

흔한 실수: "중간 삽입이 많으니 LinkedList"라고 답하는 것. 삽입 위치를 인덱스로 찾는 코드라면 탐색 비용이 삽입 이득을 넘습니다.