[Data Structures] 자료 구조의 종류와 선택 기준

Java의 Collection과 Map을 이용해 알고리즘 문제를 해결할 때, 어떤 자료 구조를 사용할지 선택할 때 고려하는 기준을 정리한다.

---

Array

• 배열의 사이즈를 알 수 있는 경우 기본 Array를 사용하는 것이 가장 좋다.
• 배열은 물리 메모리의 연속된 공간을 확보 후 데이터를 저장한다.
• 데이터 접근 시 배열의 시작 지점 메모리 주소를 기준으로 특정 인덱스의 메모리 주소를 연산하는 공식을 사용한다.

Array 배열 내부 데이터의 메모리 주소를 구하는 공식

• [배열의 시작 주소] + ( [요소의 크기] × [인덱스 번호] )
• 배열의 시작 주소 : 0x00000000
• 요소의 크기 : (chat) 1byte,  (int) 4btye, (double) 8byte
• 2번째 인덱스 메모리 주소: 0x00000000 + (4byte × 3) = 0x0000000C 

 

ArrayList

• ArrayList는 Array의 사이즈를 모를 때 사용한다.
• ArrayList는 클래스로 구성되어 있고, Array는 바로 메모리에 바로 접근하기 때문에 Array의 효율이 조금 더 좋다.
• 몇 개의 데이터를 저장할지 확실하지 않지만 같은 타입의 데이터를 일단 저장해야 하는 경우 ArrayList를 사용한다.

 

ArrayDeque

• 맨 앞/뒤에 데이터 삽입/삭제 빈도가 많을 때 사용한다.

 

HashMap

• Array 타입의 DAT 사용이 불가능한 경우 HashMap을 사용한다.
• 전체 순회하며 조회하기 위한 서비스가 아니기 때문에 순회를 해야 하는 경우 다른 자료 구조를 사용해야 한다.

Array 타입의 DAT 사용이 불가능한 경우

• 인덱스 값이 정수가 아닌 다른 값이 필요한 경우 사용한다.
• 저장하려는 값의 개수가 1,000만 개를 넘는 경우 사용한다.