Array vs Linkes List

Array(배열)

정의

• 연속된 메모리 공간에 동일한 타입 데이터를 저장하는 자료 구조

특징

• 인덱스(index)로 O(1) 접근 가능(랜덤 액세스)
• 크기가 고정(일반 배열), 동적 배열(ArrayList)은 자동 확장 가능
• 데이터 삽입/삭제 시, 뒤 요소들을 이동해야 하므로 O(n)

장점

• 접근 속도가 빠름
• 메모리 연속 → 캐시 히트율 높음 - > 실제 실행 속도도 빠름

단점

• 가운데 삽입/삭제 비효율적
• 초기 크기 설정 필요

Linked List(연결 리스트)

정의

• 노드(Node)들이 포인터로 서로 연결된 구조

특징