Array vs Linkes List
Array(배열)
정의
- 연속된 메모리 공간에 동일한 타입 데이터를 저장하는 자료 구조
특징
- 인덱스(index)로 O(1) 접근 가능(랜덤 액세스)
- 크기가 고정(일반 배열), 동적 배열(ArrayList)은 자동 확장 가능
- 데이터 삽입/삭제 시, 뒤 요소들을 이동해야 하므로 O(n)
장점
- 접근 속도가 빠름
- 메모리 연속 → 캐시 히트율 높음 - > 실제 실행 속도도 빠름
단점
- 가운데 삽입/삭제 비효율적
- 초기 크기 설정 필요
Linked List(연결 리스트)
정의
- 노드(Node)들이 포인터로 서로 연결된 구조
특징