배열과 링크드리스트 속도, 그리고 오버헤드

링크드 리스트와 배열 : 탐색 속도 비교

배열 (Array)

• 장점
  • 인덱스를 사용하여 빠르게 접근이 가능하다.
• 단점
  • 크기제한 : 배열의 크기는 선언할 때 고정되므로 삽입/삭제 시 크기를 동적으로 조절하기 어렵다.
  • 삽입/삭제 오버헤드 : 배열에서 중간에 요소를 삽입하거나 삭제할 경우 해당 요소 뒤의 모든 요소를 이동시켜야 하므로 오버헤드가 발생한다.

링크드 리스트 (Linked List)

• 장점
  • 동적 크기 조절 : 링크드 리스트는 삽입 및 삭제가 용이하며 크기를 동적으로 조절할 수 있다.
  • 효율적인 삽입/삭제 : 링크드 리스트에서는 요소의 삽입과 삭제가 해당 요소의 위치에만 영향을 미치므로 오버헤드가 적다.
• 단점
  • 탐색 속도 : 링크드 리스트는 요소를 찾기 위해 처음부터 순회해야 하므로 배열보다 느린 탐색 속도를 가진다.
    • 이진 탐색을 통해 속도 개선이 가능하지만 리스트가 정렬되어 있어야 하며, 리스트 요소에 대한 임의 접근이 가능해야 한다. 일반적인 경우라면 배열이나 해시 테이블 등의 자료구조가 더 빠른 탐색 속도를 가진다.

오버헤드란?

오버헤드는 어떤 작업을 수행할 때 추가적으로 발생하는 비용을 의미한다. 배열에서의 삽입이나 삭제는 해당 요소 이후의 모든 요소들을 이동시켜야 하므로 이 작업이 발생하는 비용이 오버헤드에 해당한다. 이로 인해 배열에서의 삽입 및 삭제 작업은 많은 자원을 소모하게 된다.

배열
[1, 2, 3, 4, 5]

링크드 리스트
1 -> 2 -> 3 -> 4 -> 5