데이터를 저장하는 자료 구조

Array

가장 기본적인 자료 구조로 논리적 자료구조, 물리적 자료구조의 순서가 동일하다.

| 배열의 크기 | 배열 초기화 시 사이즈 고정 ✨ N사이즈만큼 배열 고정 | int[] arr = new int[N]; | | --- | --- | --- | | 접근 방법 | 인덱스를 통해서 접근 | arr = {10,20,30,40,50} arr[i] arr[0] = 10, arr[1] = 20, arr[2] = 30, arr[3] = 40, arr[4] = 40 | | 저장 타입 | 동일한 타입의 요소 끼리만 저장 가능 | arr = new int[]{2, 3, "str", 2.34}; → 저장 불가

• Incompatible types. Found: 'java.lang.String', required: 'int’
• Incompatible types. Found: 'double', required: 'int’ | | 메모리 할당 | 연속적인 메모리 공간에 요소 저장 | |
• 찾고자 하는 값(index) 을 알고 있다면 시간복잡도는 BIG-O(1) : 검색
• 최악의 경우에는 시간복잡도 BIG-O(N) : 삽입, 삭제, 크기 구하기

ArrayList

내부적으로 배열을 사용해서 데이터를 관리한다.

<aside> ✨ ArrayList에서 기존의 크기를 초과하면 어떻게 복사되는지?

• 기존 배열 사이즈 + (배열 사이즈 / 2) 의 배열에 원소 복사. 만약 데이터의 양이 많으면 복사가 많이 일어나기 때문에 성능 저하가 일어날 수 있다.

• ArrayList 는 Array와 달리 빈 공간을 허용하지 않기 때문에 삭제가 일어나면 요소들을 앞으로 당기고, 삽입이 일어나면 뒤로 미는 작업이 이루어 진다.

• 배열은 heap 메모리에 저장되고 사용되지 않으면 GC에 의해 회수된다. </aside>

• 최악의 경우에는 시간복잡도 BIG-O(N) : 삽입, 삭제, 크기 구하기

• BIG-O(1) : 검색

LinkedList