array, linked list 순회 시의 시간복잡도

안녕하세요 meeryuyu님.

array가 linked list보다 나은 경우에 대해 제가 '데이터를 반복문을 통해서 빠르게 순회할 때 array가 더 낫다고 표현을 했는데, 사실 meeryuyu님께서 말씀하신대로 단순 순회할 때 두 자료구조간에 시간복잡도 차이가 나지 않습니다.

다만 cpu에서 데이터를 처리할 때 메모리에 저장된 데이터 위치에 따라 성능 차이가 발생할 수 있습니다.

먼저, 배열의 경우 메모리에서 연속적인 공간을 차지합니다. 이는 CPU 캐시의 효율성을 높여줍니다. CPU 캐시는 작은 용량이지만, 매우 빠른 속도를 가진 메모리로, 주로 자주 사용되는 데이터를 저장하는 데 사용됩니다. 그래서 배열과 같이 연속된 메모리 공간에 위치한 데이터를 순회하면서 읽는 경우, 한 번에 여러 데이터를 캐시에 올려 읽기 때문에 효율이 높습니다.

반면, 연결 리스트는 각 노드가 메모리의 임의의 위치에 할당되므로, 메모리가 연속적이지 않습니다. 이로 인해 데이터를 순회할 때마다 캐시 미스가 발생할 확률이 높아집니다. 이러한 캐시 미스가 발생하면, CPU는 메인 메모리에서 데이터를 불러와야 하며, 이 과정은 상당히 비용이 큰 작업입니다. 그래서 동일한 개수의 데이터를 순회하는 경우, 배열이 연결 리스트보다 더 빠른 성능을 보일 수 있습니다. 이러한 이유로, 데이터를 반복문을 통해 순회하는 경우 배열이 연결 리스트보다 더 효율적인 경우가 있을 수 있습니다.

하지만 실제 우리가 느끼는 수준의 차이는 절대 아니기 때문에 제가 했던 말은 엄밀히 보면 맞는 말이지만, 과하게 느껴질 수 있는 표현 같습니다. 그래서 이런 차이가 있다는 사실만 인지하고 너무 깊게 생각 안하셔도 될 것 같습니다!!

더 질문이 있으시면 언제든 질문주세요:)