[섹션2] 컬렉션 프레임워크 - ArrayList

 

 

배열과 인덱스

배열의 특징

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

 

간단 정리

 

• int는 4byte를 차지한다.
• 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)
• arr[1]: x100 + (4byte * 0)
• arr[2]: x100 + (4byte * 1)

 

배열의 검색

• 배열에 들어 있는 데이터를 검색할 때는 하나씩 비교를 해야한다.
• 배열 안에 있는 데이터를 하나씩 확인해야 하기 때문에 배열의 크기가 클 수록 시간이 오래걸린다.
• 배열의 순차 검색은 배열에 들어있는 데이터의 크기 만큼 연산이 필요하다.

 

빅오(O) 표기법

• 알고리즘의 정확한 실행 시간이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.

• O(1) - 상수시간: 입력 데이터의 크기에 상관없이 알고리즘의 실행 시간이 일정하다.
• O(n) - 선형 시간: 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.
• O(n^2) - 제곱 시간: 입력 데이터 크기의 제곱에 비례하여 증가.
  • 이중 루프를 사용할 때 나타남.
• O(log n): 이진탐색
• O(n log n): 선형 로그 시간, 효율적인 정렬 알고리즘.

 

배열의 특징2 - 데이터 추가

• 배열의 마지막 부분부터 밀어야 데이터를 유지할 수 있다.

직접 구현하는 배열 리스트1 - 시작

 

직접 구현하는 배열 리스트2 - 동적 배열

 

직접 구현하는 배열 리스트3 - 기능 추가

 

직접 구현하는 배열 리스트4 - 제네릭1

 

직접 구현하는 배열 리스트5 - 제네릭 2