[코딩 테스트 합격자 되기 : 자바 편] 5. 배열(Array), ArrayList 기본 문법 개념 정리

---

5-1 배열 개념

• 인덱스와 값을 일대일 대응해 관리하는 자료구조
• 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근 가능

⇒ 빠른 탐색 가능

⇒ 이러한 접근 방식을 임의 접근(random access)라고 함

 

배열 선언

int [] arr = {0,0,0};
int [] arr = new int[3]; // 결과값 동일

• 자바에는 배열과 유사한 기능 가진 ArrayList 자료 구조 존재
• 아래의 포스팅 참고하여 배열과 ArrayList 차이 알기
• https://yujinius45.tistory.com/77

[Java] 자바에서 배열(Array)과 ArrayList의 비교 분석 차이점

• 정확한 데이터의 개수를 알 수 있다면 배열, 개수 정확히 모르면 ArrayList 사용
• (ArrayList도 초기 크기 결정되나 동적으로 변하는 것처럼 구현되어 있음)

배열과 차원

• 배열은 차원과 무관하게 메모리에 연속 할당 된다.
• 메모리의 낮은 주소 ⇒ 높은 주소 방향으로 연속 할당
• 자바에서 1차원 배열은 하나의 객체
• 2차원 배열은 1차원 배열 객체의 배열로 표현
• 즉, 2차원 배열은 1차원 배열 객체가 여러 개 있는 것 ⇒ 따라서 2차원 배열은 메모리에 데이터가 반드시 연속적으로 저장되지 않을 수 있음 ★
  • 아래의 그림을 보면 더 쉽게 이해 가능하다.

5-2 ArrayList 사용법

• 크기가 동적으로 변경되는 배열 필요할 때 ArrayList 활용

ArrayList에 데이터 추가

맨 끝에 데이터 추가 : add()

ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]

다른 컬렉션의 데이터로부터 초기화

• ArrayList의 생성자의 매개변수로 컬렉션을 넘기면, 매개변수로 넘긴 컬렉션에 담긴 데이터로 초기화 가능

ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]

ArrayList<Integer> list2 = new ArrayList<>(list);
System.out.println(list2); // [1, 2]

인덱스를 통해 접근 : get()

ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]

System.out.println(list.get(1)); // 2

특정 위치(인덱스) 데이터 삭제 : remove()

ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]

list.remove(list.size() -1); // 끝에 있는 데이터 삭제
System.out.println(list)' // [1]

★ remove() 주의사항

• 데이터를 삭제하는 위치에 따라 데이터를 복사하는 연산 필요
• 시간 복잡도가 O(N)까지 증가할 수 있기 때문에 주의

기억해야 할 배열, ArrayList 연관 메서드

: length, Arrays.sort, Arrays.toString, Arrays.toList, size, isEmpty, Collections.sort

int [] arr = {1, 2, 4, 5, 3};
// 1. 배열의 전체 데이터 개수를 가진 length 변수
System.out.println(arr.length); // 5 
// 2. 배열의 모든 데이터를 정렬하는 Arrays 클래스의 sort() 메서드 오름차순
Arrays.sort(arr); // 정렬 [1, 2, 3, 4, 5]
// 3. 배열의 모든 데이터를 String으로 변환하는 Arrays 클래스의 toString 메서드
System.out.println(Arrays.toString(arr)); // 출력 [1, 2, 3, 4, 5]

// 4. List로 전환하는 Arrays.toList(arr)
ArrayList<Integer> list = new ArrayList<>(Arrays.toList(1, 2, 4, 5, 4));
// 5. ArrayList의 전체 데이터 개수를 반환하는 size()
System.out.println(list.size()); // 5
// 6. ArrayList의 저장된 데이터가 없는지 여부 판단 isEmpty()
Sytem.out.println(list.isEmpty()); // false
// 7. ArrayList의 모든 데이터를 정렬하는 Collections 클래스의 sort()메서드
Collections.sort(list); // 정렬 [1, 2, 3, 4, 5]
System.out.println(list); // 출력 [1, 2, 3, 4, 5]

• sort() 메서드에 정렬하려는 대상 외에 다른 인수를 전달하지 않으면 전체 데이터를 오름차순으로 정렬. 특정 범위 ⇒ From인덱스, To인덱스 지정

5-3 ArrayList의 효율성

• 배열 연산의 시간 복잡도 & 효율성

배열 연산의 시간 복잡도

• 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단번에 접근 간으
• 따라서 데이터에 접근하기 위한 시간 복잡도 O(1)
• 삭제 연산 == 추가 연산 시간복잡도

맨 뒤 삽입 경우

• 다른 데이터 영향 X ⇒ O(1)

맨 앞 삽입 경우

• 기존 데이터를 한 칸씩 뒤로 밀어야 함 ⇒ 미는 연산 필요
• 데이터 개수 N개로 일반화 ⇒ O(N)

중간 삽입

• 중간 삽입하고 그 뒤의 요소들 다 밀어야 함
• 현재 삽입한 데이터 뒤에 있는 데이터 개수 만큼 미는 연산
• 밀어야 하는 데이터 개수가 N개면 O(N)

배열은 특정한 경우에 데이터 추가&삭제 비용 많이 발생

 

배열을 선택할 때 고려할 점

• 데이터 자주 접근, 읽기 ⇒ 배열 좋은 성능
  • 배열 활용 ⇒ 임의 접근 가능 ⇒ 간선 여부도 시간 복잡도 O(1)로 판단 가능
  • BUT 배열은 메모리 공간을 충분히 확보해야 한다는 단점
• EX) 그래프 표현
• ☆ 배열은 임의 접근이라는 특성이 있어 데이터에 인덱스로 바로 접근할 수 있어 데이터에 빈번하게 접근하는 경우 효율적이지만, 메모리 낭비가 발생할 수 있음

1. 할당할 수 있는 메모리 크기 확인

• 배열로 표현하려는 데이터 너무 많으면 런타임 배열 할당에 실패할 수 있음

2. 중간에 데이터 삽입이 많은지 확인

• 배열은 선형 자료 구조
• 중간이나 처음에 데이터 빈번하게 삽입하면 시간 복잡도 높아져 실제 시험에서 시간 초과

 

리마인드

1. 배열은 임의 접근(random access)으로 배열의 모든 위치에 바로 접근 가능
2. 중간에 데이터를 삽입할 일이 많다면 배열 비효율적, 다른 방법 고안하기

---

해당 글은 다음 책을 참고하여 공부하며 정리한 글입니다. 

https://ebook-product.kyobobook.co.kr/dig/epd/ebook/E000006973689