Java로 자료구조 이해하기 1편(Array와 ArryaList의 차이점)

Java로 자료구조 이해하기 1편(Array와 ArryaList의 차이점)

모든 내용은 자바를 기반으로 설명 합니다.
Collection 클래스를 기반으로 자료구조를 알아보는 시리즈 입니다.
하지만 그 전에 Array와 ArrayList는 어떻게 다른지에 대해 간단하게 정리하고 가겠습니다.

Array는 뭐고 ArrayList는 뭐야?

Array

Array는 배열을 의미 합니다. 기본적인 배열에 대한 설명은 배제 했습니다.
구조에 대해서만 설명 하겠습니다.
아래 그림을 보면, 배열은 메모리에 순차적으로 생성 됩니다. 즉, 연속된 주소를 가집니다.

따라서, 접근성이 매우 좋습니다. 순차적으로 나열되어 있기 때문에 간단한 연산으로 접근할 수 있기 때문입니다.
시작주소 + index * byte 의 수식을 사용하면 바로 원하는 주소로 접근할 수 있습니다.
하지만 단점이면서 장점인 점도 존재 합니다. 바로 추가 및 삭제 시 입니다.
먼저 중간에 추가를 하려면 뒤에 있는 배열을 모두 뒤로 밀어 주어야 합니다. 이 작업은 모든 요소를
이동 시켜야 하기 때문에 굉장히 오랜 시간이 걸립니다. 반대로 삭제를 하게 되면, 빈공간이 남게 됩니다.
빈 공간으로 두어도 되지만, 메꾸고 싶다면, 추가와는 반대로 모든 요소를 당겨야 합니다.
이 것이 단점입니다.
장점으로는 마지막 index에 위치한 요소의 추가 삭제는 접근 자체가 빠르기 때문에 추가 및 삭제를 하고, 아무런 작업이 필요 없습니다.
즉, 당기거나 미는 작업이 없다는 의미입니다.
정리를 하면,

• 장점
  1. 연속된 주소를 가지기 때문에 접근성이 좋다.
  2. 마지막 index에 추가 및 삭제 시 빠르다.
• 단점
  1. 중간에 추가 및 삭제 시 느리다. 직접 구현 해야 함.
  2. Generic 타입을 사용할 수 없기 때문에 다형성이 가능 해진다.
     Object[] arr = new Long[10]; 과 같이 선언이 가능하다는 것인데, Long 타입 이외의 타입이 들어가는 것을
     런타임에서 알 수 있기 때문에 좋지 않다.
• 특징
  1. Primitive type 과 Object 모두 가질 수 있다.
  2. Generic 타입은 가질 수 없다.
  3. 배열의 크기를 선언 시 지정해야 한다.
     사이즈 불변.

List

자바에서 List를 인터페이스 입니다. Collection 인터페이스 아래 있는 인터페이스 입니다.
물론 중간에 더 많은 클래스들이 존재 하지만 중요한 요소는 현재 아닙니다.
자세한 내용은 이후에 List에 대해 설명할 때 할 예정이니 상속 관계는 대충 보시면 됩니다.

ArrayList

• ArrayList의 장점

  1. 배열을 기반으로 하기 때문에 접근성이 좋다.
  2. 마지막 index에 추가 및 삭제 시 빠르다.
  3. 배열에 없는 추가 및 삭제 기능이 있다.
  4. 사이즈가 동적이다.

• ArrayList의 단점

  1. 데이터 추가 삭제 시 메모리를 재할당 하므로, 배열 보다는 느리다.

• ArrayList의 특징

  1. Primitive type 불가, Object만 가능
  2. Generic type 가능
  3. 배열의 크기가 동적
  4. 배열의 크기가 동적이지만 예상이 가는 범위 내라면 초기에 지정해주는 것이 속도 면에서 유리하다.
  5. 배열을 편리하게 사용 하다록 제공된 클래스이다.

ArrayList는 특별한 상황이 아니면 배열을 대신하여 사용합니다.
배열을 편리하게 사용하기 위해 나온 클래스이기 때문입니다.

근데 ArrayList는 배열 크기가 초과 했을 때 어떻게 자동으로 생성할까?

ArrayList에는 추가 기능이 있다고 하였는데요. 그렇다고 배열 크기가 초과 했을 때 어떤 구조를 가지고, 구현이 되어 있을까요?
간단합니다. 정말로 간단합니다.
그림과 같이

1. 기존 배열의 1.5배되는 크기의 새로운 배열을 생성
2. 기존 배열의 요소를 -> 새로운 배열로 복사
3. 참조 변경

끝!! 아주 간단하게 3단계를 거쳐 동적인 배열 크기 생성이 가능하게 됩니다.

Array와 ArrayList 차이 정리

Array

• 사이즈 정적
• Primitive type, Object type
• Generic 불가
• 초기화 시 메모리 할당
• 편의 기능 x

ArrayList

• 사이즈 동적
• Object type
• Generic 가능
• 런터임 시 add와 같은 기능 사용 시 메모리 재할당하여 배열 보다는 속도가 느림. 접근성은 동일함
• 편의 기능 o