자료구조 Linear List (Dynamic Array)

출처: Wikipedia

 

ArrayList는 연속된 메모리 공간에 데이터를 저장하는 동적 배열 구조이다

인덱스를 기반으로 빠르게 접근할 수 있으며 크기가 가변적이라는 특징을 가진다

 

핵심 동작 원리

데이터는 배열 기반으로 저장되며, 내부 용량을 초과하면 더 큰 배열을 새로 생성하고, 기존 데이터를 복사한 뒤 참조를 갱신한다

 

삽입, 삭제, 검색에 대한 성능

연산 종류	Best	Worst
삽입	O(1)	O(n)
삭제	O(1)	O(n)
검색	O(1)	O(n)

 

삽입

• 마지막에 추가할 때는 O(1)
• 앞이나 중간에 삽입 시 뒤 요소를 밀어야 하므로 O(n)
• 내부 배열이 꽉 찼을 때는 재할당 비용 포함 → O(n)

삭제

• 마지막 요소는 바로 제거 가능하므로 O(1)
• 앞이나 중간 요소 삭제 시 뒤 요소를 당겨야 하므로 O(n)

검색

• 인덱스를 알고 있을 경우 O(1)
• 값을 기준으로 찾을 경우 선형 탐색 → O(n)

 

---

Reference

Dynamic array - Wikipedia

C# Reference Source(List<T>) - Github