List 인터페이스
List 인터페이스는 앞서 정복 1탄에서 설명한 Collection 인터페이스의 하위 인터페이스 중 하나입니다.
이러한 List 인터페이스는 ArrayList, LinkedList, Vector, Stack과 같은 다양한 구현체들을 가지고 있으며 다음과 같은 특징을 지니고 있습니다.
- 저장 순서가 유지되는 컬렉션을 구현하는데 사용
- 같은 요소의 중복 저장을 허용
- 배열과 마찬가지로 index로 요소에 접근이 가능함
- 배열과 달리 리스트는 자료 크기가 고정이 아닌 데이터 양에 따라 동적으로 늘어났다 줄어들었다 할 수 있다.
- 요소 사이에 빈공간을 허용하지 않아, 삽입 삭제를 할때마다 배열의 이동이 일어난다
오늘 이 글에서는 ArrayList에 대해 상세히 다루어 보고, 그다음 시리즈에서 LinkedList,Stack등 다른 구현체들에 대해서도 다루어 보겠습니다!
ArrayList
ArrayList란 크기가 동적으로 조절되는 배열을 말합니다. 이러한 ArrayList의 특징에 대해 살펴보겠습니다!
- 연속적인 데이터의 리스트(데이터는 연속적으로 리스트에 들어있어야 하며, 중간에 빈 공간이 있으면 안된다)
- ArrayList는 내부에 Object[] 배열을 이용해서 요소를 저장
- 배열을 이용하기 때문에 인덱스를 통해 요소에 빠르게 접근 가능(조회에 강점을 가짐)
- 크기가 고정되어 있는 배열과 달리 데이터 적재량에 따라 가변적으로 공간을 늘이거나 줄인다.
- 그러나 배열 공간이 꽉 찰때 마다 배열을 copy하는 방식으로 늘리므로, 이 과정에서 지연이 발생하게 된다.
- 데이터를 리스트 중간에 삽입/삭제 하는 경우, 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 자동으로 이동하기에 삽입 삭제 동작이 느리다.
이러한 ArrayList와 Array의 차이에 대해 살펴보면서 조금 더 깊게 이해해 보겠습니다!
우선 둘의 공통점은 인덱스를 통해 접근 속도가 빠르다는 점입니다.
ArrayList또한 내부적으로 array를 사용하여 데이터를 저장하기 때문에, 메모리상에 연속적으로 배치되며, 인덱스를 통한 빠른 접근(O(1))이 가능합니다.
반면 배열은 요소가 중간에 비어있어도 되지만, ArrayList의 경우에는 비어있는 공간을 허용하지 않습니다!
또한 배열은 처음 선언한 배열의 크기를 변경할 수 없습니다(정적 할당)
반면 리스트의 크기는 고정적이지 않고, 가변적이며 이를 동적 할당이라고 부릅니다.
이러한 배열과 ArrayList를 사용할때는 어떤 점들을 주의해야할까요??
배열의 경우에는 배열의 크기를 변경할 수 없기 때문에, 처음에 너무 큰 크기로 설정하면 메모리 낭비가 될 수 있고, 너무 작은 크기로 설정해주었을 경우 공간이 부족해질수있으니 초기 사이즈 설정이 중요하겠죠??
ArrayList의 경우에는 객체로 데이터를 다루기 때문에 배열에 비해 차지하는 메모리가 커집니다.
예를들어 기본형 타입인 int 타입의 경우엔 크기가 4byte이지만, Wrapper 클래스인 Integer는 32bit JVM 환경 기준, 객체의 헤더(8Byte), 원시 필드(4byte), 패딩(4Byte)으로 인해 최소 16Byte의 크기를 차지하며, 이러한 객체 데이터를 다시 주소로 연결하기 때문에 16 플러스 알파의 공간을 차지하게 되는 것이죠!
ArrayList 관련 연산 속도
밑의 표는 최악의 경우를 고려한 Big-O 복잡도를 기준으로 작성된 표입니다!
삽입 연산의 경우
ArrayList에 데이터를 삽입하는 경우엔 어디에 삽입하냐에 따라 시간 복잡도가 다르게 나타납니다.
만약 현재 ArrayList내의 내부 배열의 크기의 여유가 있고, 맨 끝에 추가하기만 하는 경우엔 O(1)의 시간복잡도를 가집니다.
하지만 ArrayList 내부 배열이 꽉차서 현재 값을 추가하려면, 배열의 크기를 늘리고, 기존 배열의 element들을 복사해 와야 하기 때문에 O(N)의 시간복잡도를 가집니다.
만약 인덱스의 값이 배열의 처음이거나 중간인 경우엔 어떨까요??
이 경우에는 해당 index의 뒤쪽에 존재하는 모든 element들을 우측으로 한칸씩 옮겨 빈공간을 만들어야 하므로, 시간복잡도는 O(N)에 비례하게 됩니다.
삭제의 경우
ArrayList의 경우 인덱스나 (remove(int index) 객체 (remove(Object o))를 통해 값을 제거할 수 있습니다.
인덱스를 통해 데이터를 삭제하는 경우, 해당 인덱스의 데이터를 삭제하고 index 뒤쪽의 element들을 앞으로 한칸씩 이동하므로 시간복잡도는 배열의 원소 갯수인 N에 비례합니다(O(n)).
객체를 통해 데이터를 삭제할려는 경우, 앞에서부터 순차적으로 해당 객체와 동일한 객체인지를 판단하게 됩니다. 시간복잡도는 삭제와 마찬가지로 O(n)에 비례하게 됩니다!
이번 글에서는 List인터페이스와 이에 대한 구현체인 ArrayList에 대해 알아보았습니다! 이해하시는데 도움이 되었으면 좋겠네요
혹시 잘못된 내용이 있다면 지적 부탁드립니다, 언제나 환영합니다 ^^
다음 글에서는 LinkedList에 대해 상세히 알아보겠습니다
참고
자바의 정석
https://inpa.tistory.com/entry/JCF-🧱-Collections-Framework-종류-총정리#priorityqueue_클래스
https://chunsubyeong.tistory.com/81
'JAVA' 카테고리의 다른 글
| Collection Framework 정복 4탄 - Heap, PriorityQueue, Deque (0) | 2023.05.26 |
|---|---|
| Collection Framework 정복 3탄 - LinkedList (0) | 2023.05.23 |
| Collection Framework 정복 1탄 - Collection Framework란? (0) | 2023.05.22 |
| Wrapper Class, AutoBoxing && UnBoxing에 대해 정복하기! (0) | 2023.05.17 |
| StringBuffer,StringBuilder의 개념 및 차이점 정복하기 (0) | 2023.05.17 |
