[Java Collection Framework] 2. 컬렉션(Collection), 리스트(List), ArrayList, LinkedList, Vector

Collection 인터페이스

collection 계층 구조의 root interface로 object의 집합을 의미
List, Queue, Set이 이를 구현

✅ 주요 메소드

1. List 인터페이스

✅ 주요 메소드

🔽 메소드 공부하면서 생긴 궁금증

Q. 각각 new 생성자를 통해 생성한 ArrayList 객체가 같은 값, 같은 순서의 요소를 갖고 있을 때,
     hashCode값이 같은 이유가 뭘까?

- hashCode는 각 객체에 고유한 속성값을 주기 위해 존재하며 보통은 메모리 주소를 기반으로 함
- 하지만 'ArrayList'는 hashCode 메소드를 override하여 리스트의 컨텐츠를 기반으로 값을 반환(메모리 주소가 아닌!)
- ArrayList에서는 이터레이터를 통해 리스트의 요소들을 순서대로 추출한 값을 기반으로 해시코드를 계산
- 따라서, 순서가 같고 들어 있는 값이 똑같다면 다른 메모리 주소를 갖고 있더라도 똑같은 해시코드를 갖게 됨

 

Q. toArray()와 toArray(T[] a)의 명확한 차이?
반환 값으로 보면 같아보일 수 있지만 toArray()는 Object 타입으로 변환되는 반면, toArray(T[] a)에서는 내가 원하는 명확한 배열 타입을 지정해줄 수 있음
Object[] objects = numbers.toArray();
Integer[] integers = numbers.toArray(new Integer[0]);

1-1. ArrayList 클래스

✅ 특징

1. 사이즈가 변화 가능한 배열

- ArrayList는 내부적으로 배열을 사용하여 원소(element)를 저장
- 기본 생성시, 일정한 크기의 배열을 생성 (기본 크기는 10이며, 생성시에 initialCapacity가 주어지면 해당 용량만큼의 배열 생성)
- 원소 추가시 내부 배열 크기 확인 ➡️ 배열 크기가 작으면 새로운 배열 생성 및 이전 배열 복사 ➡️ 값 추가 과정을 거쳐 시간복잡도 증가

- 원소 삭제시에는 배열의 크기를 줄이지 않고 빈 인덱스를 허용하는 형태이기 때문에 삭제 작업에서는 효율적

2. 빠른 접근 가능
- index를 사용하여 원소에 대한 빠른 접근 가능 (내부적으로 배열을 사용하기 때문에 가능)

3. 객체 타입 저장 가능

- 제네릭 타입을 지원하여 모든 타입의 객체를 저장할 수 있음

4. Thread-safe하지 않음

- 동기화하지 않으므로 여러 스레드가 동시에 엑세스 하는 상황에서는 별도의 동기화처리가 필요함
   (Collections.synchronizedList()메소드 사용하여, 한 스레드가 해당 리스트를 사용할 때는 다른 스레드에서 접근하지 못하도록 함)

1-2. LinkedList 클래스

✅ 특징

1. 원소의 삽입, 삭제에 유리
- Deque와 List 인터페이스를 구현한 이중 연결 리스트로, 노드(원소)의 앞과 뒤를 다른 노드(원소)들과 연결하여 저장
- 사이즈가 정해져있지 않으므로 원소를 추가하거나 제거할 때 크기를 조정할 필요 없어 더 효율적임

2. 원소의 접근, 검색, 순회에 불리

- 인덱스로 접근을 요청하더라도 순차적으로 노드를 탐색해야 하기 때문에 ArrayList에 비해 시간복잡도 증가

- 노드의 연결 정보를 저장하고 있는 포인터를 많이 사용하여 메모리 사용량이 크며, 포인터를 참조하는데 걸리는 오버헤드도 발생

3. Thread-safe하지 않음
- ArrayList와 마찬가지로 동기화되지 않으므로 여러 스레드가 동시에 엑세스하는 상황에서는 별도 동기화처리 필요함
- iterator는 생성된 후 리스트가 구조적으로 수정되면 ConcurrentModificationException을 던져 해당 스레드가 안전하게 종료될 수 있도록 하나, 비동기적인 동시 수정 상황에서 확실히 보장할 수는 없으므로 버그를 검출하는데 사용하는 정도로만 의존할 것

🍓 ArrayList VS LinkedList

	ArrayList	LinkedList
내부 구조	배열	이중 연결 리스트
접근 시간복잡도	O(1)	O(n)
삽입/삭제 시간복잡도	O(n)	O(1) - 처음, 마지막 노드 O(n) - 중간 노드
메모리 사용량	작음	큼
순회	빠름	느림
검색	빠름	느림

🔽 공부하면서 생긴 궁금증

Q. ArrayList와 LinkedList 중 정렬이 빠른 것은?
- 둘 다 Collections.sort()를 통해 정렬 가능하나, 각기 다른 정렬 알고리즘 사용
- ArrayList: 퀵 소트 알고리즘 사용(Arrays.sort()와 같은)하며 최악의 경우 O(n^2)의 복잡도를 가짐
- LinkedList: 내부적으로 List의 모든 요소를 배열로 복사, 그 배열을 정렬한 다음 다시 List로 복사하므로 추가적인 메모리가 사용되며, 속도도 더 느려짐

1-3. Vector 클래스

✅ 특징

1. 사이즈가 변화 가능한 배열
- ArrayList와 마찬가지로 배열을 생성하고, 인덱스를 사용하여 원소에 접근 가능
2. Thread-safe함
- Vector의 메소드들은 사용될 때 Lock 기능을 사용하여 다른 스레드가 해당 메소드에 접근하는 것을 차단
- 안전하게 요소를 추가, 삭제, 수정, 검색할 수 있음

🍓 Vector VS ArrayList

	Vector	ArrayList
Thread-safe	O	X
배열 크기 증가	크기를 초과할 경우 용량을 2배씩 늘림 - 대용량 데이터 처리시 유리	크기를 초과할 경우 용량을 50%씩 늘림
Iterators	Fail-fast - 다른 스레드에서 요소를 추가, 삭제할 때 ConcurrentModificationException 발생
자료 구조	배열
성능	동기화 오버헤드 때문에 비스레드 환경에서는 ArrayList보다 느림	동기화가 필요 없기 때문에 비스레드 환경에서 Vector보다 빠름

예상 면접 질문

Q. 컬렉션 프레임 워크에 대해 설명해주세요.

다수의 데이터를 쉽고 효과적으로 관리할 수 있는 표준화된 방법을 제공하는 인터페이스, 클래스 집합을 의미합니다.
자바 컬렉션 인터페이스를 상속받은 인터페이스로 List, Set, Queue가 있고, 추가적으로 Map 인터페이스까지 합하여 보통 자바 컬렉션 프레임워크라고 표현합니다.
Map은 데이터간 순환을 하지 않고, 단일 데이터가 아닌 Key-Value의 쌍데이터를 처리하기 때문에 컬렉션 인터페이스를 상속받지 않고 있지만, 데이터를 관리한다는 측면에서 유사한 기능을 가지므로 컬렉션 프레임워크 안에 포함하여 부릅니다.

 

Q. Array와 LinkedList의 차이는?

1. 직접 접근
- Array: Random Access, 즉 인덱스를 통해 요소에 직접 접근 가능하여 시간복잡도는 O(1)
- LinkedList: Sequential Access, 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 함 O(N)

2. 삽입, 삭제
- Array: 인덱스를 모를 경우 검색 필요하며 중간 요소일 경우 위치를 조정하는 작업도 존재해 시간복잡도 O(N)

- LinkedList: 처음, 마지막 요소일 경우 O(1)이나 중간 요소일 경우 탐색 과정으로 인해 시간복잡도 O(N)

3. 메모리 할당

- Array: 정적 메모리 할당으로 선언 시 컴파일 타임에 할당
- LinkedList: 동적 메모리 할당으로 새로운 요소가 추가될 때 런타임에 메모리 할당

 

Q. ArrayList가 Array보다 느린 이유는?

1. ArrayList는 동적으로 크기를 조정할 수 있어야 하기 때문에 원소를 추가하는 과정에서 배열을 복사하고 조정하는 작업이 추가됨
2. Array는 primitive type만 저장하지만 ArrayList는 객체를 저장하므로 각 요소를 참조할 때 추가 오버헤드가 발생