Java : ArrayList
C++ : Vector
Dynamic Array(ArrayList)
- 내부적으로 배열을 사용하여 데이터를 관리한다.
- 인덱스를 가지고 있어서 데이터 검색에 적합하고 속도가 빠르다.
- 시간 복잡도 : O(1) - 데이터 삽입, 삭제 시에 해당 데이터를 제외한 모든 데이터를 임시 배열을 생성하여 복사하므로 삽입, 삭제가 빈번할 경우 속도가 느리며 부적합하다.
- 시간 복잡도 : O(n) - 동기화를 지원하지 않아 Vector보다 빠르다.
LinkedList
- 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면 된다.
- 데이터 검색 시에는 처음부터 노드를 순회하기에 오래 걸리며 성능이 좋지 않다.
- 시간 복잡도 : O(n) - 데이터의 삽입, 삭제시 불필요한 데이터의 복사가 없어 데이터의 삽입, 삭제 시 유리하다.
- 시간 복잡도 : O(1)
- 하지만, 경우에 따라 다르기도 하다.
- 삽입,삭제를 하기위한 노드를 찾기 위해선 결국 O(n)이 걸리고 삽입, 삭제를 위한 시간 복잡도 까지 계산하면 결국 O(n)이 걸린다.
- 만약, 중간 요소의 삽입, 삭제가 없고 맨 앞과 뒤 삽입, 삭제만 한다면 O(1)이 걸린다. 그렇지 않으면 O(n)이 걸린다.
📌 데이터의 검색이 주가 되는 경우에는 Dynamic Array(ArrayList)가 좋다.
📌 데이터의 삭제,삽입이 빈번하다면 Dynamic Array보단 LinkedList를 사용하는 편이 좋다.
developer