[Data Structure] Array & List
Array 배열
특징
- 연속된 메모리 공간에 할당
- 무작위 접근(Random Access) 가능
- 정적 배열
- 지역성을 가짐
- 탐색에 효율적
- C의 Array
- Java의 Array
장점
- 인덱스를 통한 검색에 빠른 성능을 보여줌
- 연속적 메모리 공간에 할당되어 순차 접근도 빠름
단점
- 한 데이터를 삭제 하더라도 처음 할당 된 사이즈만큼 데이터가 없더라도 메모리를 차지하고 있어서 메모리 재사용이 불가능
- 정적이므로 배열의 크기를 정해주어야 함
- 삽입 삭제 시 요소들을 이동해야 해서 비효율적
- 선언시 지정한 배열의 크기를 변동 불가
List 리스트
특징
- 불연속 적으로 메모리 공간을 할당
- 포인터를 통한 접근
- 동적 배열
- 추가, 삭제에 효율적
- Python의 List
- Java의 ArrayList
장점
- 삽입 삭제 시 전후 노드의 참조 관계만 수정하면 되어 효율적
- 동적이므로 크기가 정해져 있지 않음
- 메모리의 재사용 가능
- 포인터를 통한 접근
- 불연속적이므로 메모리 관리의 편리
단점
- 검색이 비효율적
- 포인터를 통해 다음 데이터의 위치를 가르키고 있어 추가적인 메모리 공간 발생
Array (배열)
저장할 데이터의 크기가 정해져 있고,
추가적인 삽입 삭제가 적고,
특정 위치의 데이터를 조회하는 작업이 많다면 유리
List (리스트)
저장할 데이터의 개수가 미정이고,
삽입 삭제가 많이 일어나며,
특정 위치의 데이터를 조회하는 경우가 별로 없다면 유리
