컬렉션 프레임워크 - ArraryList

배열의 특징

배열과 인덱스

• 배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라 한다.
• 자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공한다.

 

배열의 특징

• 배열에서 자료를 찾을 때 인덱스(index)를 사용하면 매우 빠르게 자료를 찾을 수 있다.
• 인덱스를 통한 입력, 변경, 조회의 경우 한번의 계산으로 자료의 위치를 찾을 수 있다.

 

 

공식: 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)

배열에서 인덱스를 사용하는 경우 데이터가 아무리 많아도 한 번의 연산으로 필요한 위치를 찾을 수 있다.

 

배열의 검색

• 배열에 들어있는 데이터를 찾는 것을 검색이라 한다.
• 배열의 순차 검색은 배열에 데이터가의 크기만큼 연산이 필요하다. 배열의 크기가 n이면 연산도 n만큼 필요하다.

---

 

 

빅오(O) 표기법

빅오(Big O) 표기법은 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 이는 특히 알고리즘이 처리해야 할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나나탠다. 여기서 중요한 것은 알고리즘의 정확한 실행 시간을 검색하는 것이 아니라, 데이터 양의 증가에 따른 성능 변화 추세를 이해하는 것이다.

 

 

빅오 표기법의 예시

• O(1) - 상수 시간: 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정하다.
  • 예) 배열에서 인덱스를 사용하는 경우
• O(n) - 선형 시간: 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.
  • 예) 배열의 검색, 배열의 모든 요소ㅡㄹ 순회하는 경우
• O(n²) - 제곱 시간: 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다.
  • 예) 보통 이중 루프를 사용하는 알고리즘에서 나타남
• O(log n) - 로그 시간 : 알고리즘의 실행 시간이 데이터 크기의 로그에 비례하여 증가한다.
  • 예) 이진 탐색
• O(n log n) - 선형 로그 시간
  • 예) 많은 효율적인 정렬 알고리즘

 

배열의 순차 검색의 경우

• 최적의 경우: 배열의 첫번째 항목에서 바로 값을 찾으면 O(1)이된다.
• 최악의 경우: 마지막 항목에 있거나 항목이 없는 경우 전체 요소를 순회한다. 이 경우 O(n)이 된다.
• 평균의 경우: 평균적으로 보면 보통 중간쯤 데이터를 발견하게 된다. 이 경우 O(n/2)가 되지만, 상수를 제외해서 O(n)으로 표기한다. 최악과 비교를 위해 O(n/2)으로 표기하는 경우도 있다.

 

배열 정리

• 배열의 인덱스 사용: O(1)
• 배열의 순차 검색: O(n)

 

---

데이터 추가

배열에 데이터를 추가할 때 위치에 따른 성능 변화

• 배열의 첫번재 위치에 추가
  • 배열의 첫번재 위치를 찾는데는 인덱스를 사용하므로 O(1)이 걸린다.
  • 모든 데이터를 배열의 크기만큼 한 칸씩 이동해야 한다. 따라서 O(n) 만큼 연산이 걸린다.
  • O(1 + n) → O(n)이 된다.
• 배열의 중간 위치에 추가
  • 배열의 위치를 찾는데는 O(1)이 걸린다.
  • index의 오른쪽에 있는 데이터를 모두 한 칸씩 이동해야 하다. 따라서 평균 연산은 O(n/2)이 된다.
  • O(1 + n/2) →  O(n)이 된다.
• 배열의 마지막 위치에 추가
  • 이 경우 배열이 이동하지 않고 배열의 길이를 사용하면 마지막 인덱스에 바로 접근할 수 있으므로 한번의 계산으로 위치를 찾을 수 있고, 기존 배열을 이동하지 않으므로 O(1)이 된다.

 

배열의 한계

배열은 가장 기본적인 자료 구조이고, 특히 인덱스를 사용할 때 최고의 효율이 나온다. 하지만 이런 배열에는 큰 단점이 있다. 바로 배열의 크기를 배열을 생성하는 시점에 정해야 한다는 점이다.

 

---

직접 구현하는 배열 리스트

시작

배열의 경우 다음 2가지 불편함이 있다.

• 배열의 길이를 동적으로 변경할 수 없다.
• 데이터를 추가하기 불편하다. 

List 자료 구조

순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다.

• 배열: 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다
• 리스트: 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있다.

 

ArrayList의 단점

• 정확한 크기를 미리 알지 못하면 메모리 낭비가 된다. 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 있다.
• 데이터를 중간에 추가하거나 삭제할 때 비효율적이다.
• 이 경우 데이터를 한 칸씩 밀어야한다. 이것은 O(n)으로 성능이 좋지 않다.
• 만약 데이터의 크기가 1,000,000건이라면 최악의 경우 데이터를 추가할 때 마다 1,000,000건의 데이터를 밀어야 한다.

 

ArrayList의 빅오 정리

• 데이터 추가
  • 마지막에 추가: O(1)
  • 앞, 중간에 추가: O(n)
• 데이터 삭제
  • 마지막에 삭제: O(1)
  • 앞, 중간에 삭제: O(n)
• 인덱스 조회: O(1)
• 데이터 검색: O(n)

 

배열 리스트는 순서대로 마지막에 데이터를 추가하거나 삭제할 때는 성능이 좋지만, 앞이나 중간에 데이터를 추가하거나 삭제할 때는 성능이 좋지 않다.

 

 

 

 

 

 

 

 

 

 

 

출처 - 김영한의 실전 자바 중급 1편