이 글은 학부 수업을 들으면서 개인적으로 정리한 글입니다. 잘못된 내용이 있다면 댓글로 말씀 부탁드립니다!
Introduction
C언어로 프로그래밍을 공부하면서 가장 처음 접하게 되는 기본적인 배열(Array)은 초기화 시 자료형과 크기를 지정한다. 배열의 크기를 지정해두기 때문에, 데이터의 입력이 얼마나 들어오는지 미리 알기 어려운 경우에는 배열 크기 설정에 어려움을 겪는다.
이런 어려움을 해결하기 위해 다음 특징을 갖는 Resizing Array를 사용한다:
- 저장된 데이터의 크기에 따라 Array의 크기를 재조정하는 자료 구조
- index로 원소 접근 가능
Python의 List, C++의 vector, Java의 ArrayList가 그 대표적인 예시이다. 이를 활용해 사용자는 데이터의 입력이 얼마나 들어오는지 미리 예측하지 못하더라도 편리하게 데이터 추가, 삭제할 수 있다.
구현 방식에 따른 성능
Resizing Array를 구현하는 방법으로는
1.Linked List를 사용한 구현
2.Array를 사용한 구현
이 중 1.은 우리가 흔히 아는 방법이고, 2.는 크기 N의 배열이 가득차면, 더 큰 배열을 만들어 기존의 데이터를 복사하는 방식이다. (반대로 삭제의 경우에도 불필요한 메모리 낭비를 줄이기 위해 축소가 일어난다.)
두 구현 방식에 따른 성능 차는 다음과 같다.
(*) 마지막에 원소를 추가할 때마다, Resize가 일어나는 것이 아니기 때문에, 평균적인 비용은 ~1이 된다. [1]
위의 표에서 확인할 수 있듯, Array를 사용해 구현하는 편이 일반적으로 더 빠르다.
(하지만 어떻게 사용할 지에 따라 Linked List를 사용하는 것이 나은 경우도 있다.)
참고 자료
[1] https://medium.com/swlh/time-complexity-analysis-of-dynamic-data-structure-3b79fe9bc721