배열과 연결리스트

📌 배열과 연결리스트의 비교

 ' 자료 구조' 는 프로그램의 제대로 된 동작, 지연 시간, 사용 메모리, 기타의 측면에서 최선의 성능을 제공하도록 선택하는데 있어 필수적입니다.
어떤 자료 구조를 사용할 지를 결정하는데 적합한 지표로 시간 복잡도(time complexity)가 있습니다.

시간 복잡도(time complexity) : 특정한 작업을 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식.

• 배열
  배열은 '연속된 자료 구조' 입니다. 배열의 전체 크기에 상관없이 동일한 수식 하나로 모든 원소에 바로 접근할 수 있기 때문에 데이터 접근 시간이 항상 일정합니다.
  빅오(Big-O) 표기법으로 나타내면 O(1) 입니다.
  배열은 정적(static) 배열과 동적(dynamic) 배열로 나눌 수 있습니다. 정적 배열은 스택(stack) 영역에 할당되어 함수를 벗어나면 자동으로 해제가 이루어 지고, 동적 배열은 힙(heap) 영역에 할당되어 직접 해제가 필요합니다.

• 연결 리스트
  연결 리스트는 '연결된 자료 구조' 입니다. i 번째 원소에 접근하기 위해선 i 번 이동해야하기 때문에 노드 개수에 비례하여 시간 복잡도 O(n) 이 됩니다.
  새로운 원소를 삽입하려면 새로운 노드를 생성하고 각 노드의 next 포인터를 수정합니다.

배열과 연결 리스트에서의 모든 원소를 거치는 작업은 이론적으론 같은 시간 복잡도를 가지지만, 실제로는 연결 리스트의 성능이 조금 떨어집니다.

📌 배열과 연결 리스트의 시간 복잡도

🔸 참고. 코딩테스트를 위한 자료 구조와 알고리즘 with C++