배열이 인덱스를 지정했을 때 빠른이유

메모리상에서 “배열의 시작 주소 + (인덱스 * Nbytes)”로 바로 접근할 수 있기 때문이다. 반면 반복문으로 찾는 경우 처음-끝까지 찾아가는 O(N)의 시간이 필요하다.

시간 복잡도

• 데이터 추가
  • 마지막 : O(1)
  • 처음/중간 : O(N)
• 데이터 삭제
  • 마지막 : O(1)
  • 처음/중간 : O(N)
• 데이터 조회 : O(1)
• 데이터 검색 : O(N)

한계점

• 현재 ArrayList의 크기를 초과하면 (보통) 1.5배 사이즈를 늘린 후 데이터를 넣는다. 그럼 빈공간이 생기겠지?
• 첫, 가운데, 끝에 넣는 위치에 따라서 시간복잡도가 크게 달라진다. 만약 1,000,000건이라면 이만큼 다 뒤로 땡겨야함.

제네릭 + 배열리스트

• 코드

1. 생성자에는 Object 만 사용할 수 있다.
   • JVM은 클래스/객체 정보를 메모리에 올릴 때 T, E와 같은 제네릭에 대해서는 모른다.
   • 따라서 대안으로 Object만 사용한다. 하지만, 어차피 클래스 단에서 <T>과 다른 메서드에서 제네릭을 매개변수로 선언한다면 그 클래스는 제네릭으로 지정한 타입만 들어갈 것이다.
2. 고정된 타입으로 안전하게 다운캐스팅되며 자료구조와 제네릭이 어울리는 이유이다.

언제 좋나?