[Java 복습] 직접 구현해보는 ArrayList

자료 구조

배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료구조라 한다.

자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공하고 있다.

 

 

배열의 특징

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

 

• 공식: 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)
  • arr[0]: x100 + (4byte * 0): x100
  • arr[1]: x100 + (4byte * 1): x104
  • arr[2]: x100 + (4byte * 2): x108

배열의 경우 인덱스를 사용하면 한번의 계산으로 매우 효율적으로 자료의 위치를 찾을 수 있다. 

인덱스를 통한 입력, 변경, 조회 모두 한번의 계산으로 필요한 위치를 찾아서 처리할 수 있다. 

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

 

 

배열의 크기와 검색 연산

배열의 크기가 n이면 연산도 n만큼 필요하다.

배열의 순차 검색은 배열에 들어있는 데이터의 크기 만큼 연산이 필요하다.

• 배열의 크기 1: arr[0] 연산 1회
• 배열의 크기 2: arr[0], arr[1] 연산 2회
• 배열의 크기 3: arr[0], arr[1], arr[2] 연산 3회
• 배열의 크기 10: arr[0], arr[1], arr[2] ... arr[9] 연산 10회
• 배열의 크기 n: arr[0], arr[1], arr[2] ... arr[n] 연산 n회

 

 

빅오(O) 표기법

 

 

빅오(Big O) 표기법은 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 

이는 특히 알고리즘이 처리해야 할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다. 

여기서 중요한 것은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.

 

빅오 표기법의 예시

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

빅오 표기법은 매우 큰 데이터를 입력한다고 가정하고, 데이터 양 증가에 따른 성능의 변화 추세를 비교하는데 사용한
다. 쉽게 이야기해서 정확한 성능을 측정하는 것이 목표가 아니라 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비
교를 하는 것이 목적이다.

 

 

배열의 한계

배열은 가장 기본적인 자료 구조이고, 특히 인덱스를 사용할 때 최고의 효율이 나온다. 

하지만 이런 배열에는 큰 단점이 있다. 바로 배열의 크기를 배열을 생성하는 시점에 미리 정해야 한다는 점이다.

배열처럼 처음부터 정적으로 길이가 정해져있는 것이 아니라, 동적으로 언제든지 길이를 늘리고 줄일 수 있는 자료 구조
가 있다면 편리할 것이다.

 

 

 

배열 리스트

 

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

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

데이터를 추가하는 경우 직접 오른쪽으로 한 칸씩 데이터를 밀어야 한다. (이런 코드를 직접 작성해야 한다.)
배열의 이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조를 List(리스트)라 한다.

 

 

List 자료 구조

순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다.
일반적으로 배열과 리스트는 구분해서 이야기한다. 

리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변할 수 있다.

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

 

 

ArrayList 단점

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

 

 

 

ArrayList의 빅오 정리

 

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

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

추가하거나 삭제할 때는 성능이 좋지 않다. 이런 단점을 해결한 자료 구조인 링크드 리스트( LinkedList )에 대해 알아보자.