JCF (Java Collections Framework)

JCF란 무엇인가요?

JCF(Java Collections Framework)는 자바에서 데이터를 저장하고 관리하기 위한 표준화된 클래스와 인터페이스 모음입니다. 데이터를 효율적으로 처리하기 위해 리스트, 집합, 맵, 스택, 큐와 같은 다양한 자료구조를 제공합니다.

JCF의 계층 구조

JCF는 최상위 인터페이스인 Collection과 Map을 기반으로 하며, 주요 인터페이스로 List, Set, Map, Queue가 있습니다.

Collection Interface

• 컬렉션 인터페이스는 List, Set, Queue에 상속한다. 컬렉션 인터페이스의 주요 메소드로는 add(), clear(), contain(), equals(), isEmpty(), iterator(), remove(), stream() 등이 있다.

List Interface

List는 요소를 순서대로 저장하고, 인덱스를 통해 요소에 접근할 수 있는 인터페이스입니다. 중복 요소를 허용합니다.

구현체의 종류는 무엇이 있나요?

• List Interface의 구현체: ArrayList, LinkedList, Vector

  List의 인터페이스 선언과 할당 : List a = new ArrayList();

ArrayList Class

ArrayList에 대해 설명해 주세요

ArrayList는 크기가 가변적인 선형 리스트로, 인덱스를 이용하여 내부 요소를 관리한다는 점이 일반적인 배열과 유사하다. 하지만, 한 번 사이즈가 정해지면 바꿀 수 없는 배열과 달리, ArrayList는 저장 용량(capacity)이라는 것이 존재하여 이 용량을 넘어서면 자동으로 용량을 증가함으로써 추가적으로 요소를 넣을 수 있도록 해 준다.

• 초기용량은 초기 인자값으로 정해지며 넘기지 않을경우 초기용량은 10으로 설정.

1. 요소의 추가
   

• add(object) : O(1), 맨뒤에 요소를 차례차례 추가
• add(index, object) : O(N), index의 위치를 찾고(O(1)) 위치에 객체를 추가한다 이후에 요소들의 index를 하나씩 미룬다(O(N))

2. 요소의 삭제

• remove() : O(1), 맨 뒤의 요소를 삭제
• remove(index) : O(N), index의 위치해 있는 객체를 찾고(O(1)) 위치에 객체를 삭제한다 이후에 요소들의 index를 하나씩 땡긴다(O(N))

3. 요소를 탐색

• contains(object) : 맨 앞부터 탐색을 하므로 시간복잡도는 O(N)이다.

4. 요소의 반환

• get(index) : 인덱스로 직접 접근하여 O(1)이다.

어떻게 인덱스 접근이 O(1)이 되는지
배열에서 특정 인덱스에 접근할 때, 기본 주소 + (인덱스 * 요소 크기)를 사용하여 메모리 위치를 계산합니다. 이 방식은 모든 요소의 위치를 계산할 필요 없이, 단순히 해당 인덱스에 대한 위치만 계산해 바로 접근하므로 추가 연산이 필요하지 않으며 상수 시간에 처리됩니다.

ArrayList는 어떻게 동적으로 사이즈가 늘어나나요?

ArrayList의 용량이 다 차면 기존 용량의 1.5배 크기로 배열을 확장하여 새로운 배열을 생성하고, 기존 배열의 요소를 새로운 배열로 복사합니다. 이 과정은 배열 크기를 동적으로 증가시키기 위해 수행됩니다.

• ArrayList는 요소의 추가시 용량을 확인하고 만약 꽉 찼다면 배열의 크기를 늘립니다.
  • 배열이 다 찼다면 ArrayList는 더큰 새로운 배열을 생성하고 약 1.5배의 크기로 생성합니다.
  • 새로운 크기는 newCapacity = (oldCapacity * 3) / 2 + 1 방식으로 결정합니다.
    • newCapacity = oldCapacity + (oldCapacity >> 1); 비트연산으로 크기를 늘립니다.
  • 기존 배열에 저장된 요소들을 새로운 배열로 복사합니다.

    배열의 크기를 점진적으로 증가시켜 성능 비용을 줄입니다.
    또한 배열 복사가 자주일어나도 비용이 발생하므로 크기를 한번에 크게 늘립니다.

LinkedList에 대해 설명해 주세요.

LinkedList는 노드로 구성된 이중 연결 리스트 구조를 가지고 있으며, 각 노드의 요소는 데이터와 포인터(참조)를 갖고있고 두개의 포인터가 이전 노드와 다음 노드를 가리킵니다.
1. 요소의 추가

• add(object) : O(1), 맨뒤의 요소를 추가
• add(index, object) : O(N), 특정위치(index)에 요소를 추가
  
  • 인자로 받은값으로 Node를 생성 후 이전 노드의 다음 참조를 새로운 Node로 교체한다.
    탐색은 O(N), 교체는 O(1)로 총 시간복잡도 O(N)을 가진다.

2. 요소의 삭제

• remove(index) : O(N), 특정위치(index)에 요소를 삭제
  
• 추가와 마찬가지로 탐색은 O(N), 교체는 O(1)로 총 시간복잡도 O(N)을 가진다.

3. 요소를 탐색

• contains(object) : 맨 앞부터 탐색을 하므로 시간복잡도는 O(N)이다.

4. 요소의 반환

• get(index) : 특정요소에 접근하기 위해서 인덱스에 바로 지정되는것이 아닌 맨 앞부터 탐색(노드의 포인트(참조)값)해야 하므로 시간복잡도는 ArrayList와 달리 O(N)이다.
  

언제 ArrayList를 사용하고, 언제 LinkedList를 사용할까요?

ArrayList: 요소의 빈번한 접근(반환)이 빈번할때 사용합니다.
LinkedList: 삽입과 삭제가 빈번할때 사용합니다.

• ArrayList는 인덱스의 접근으로 빠르기 때문에 추가, 삭제, 읽기가 빠르지만 중간 인덱스의 수정작업에서 재 할당하는 과정이 느립니다. 때문에 수정작업이 빈번하면 지양합니다.
• LinkedList는 인덱스에 접근시 인덱스를 하나하나 다 찾아야 하지만 중간 인덱스 수정시 인덱스의(노드)의 정보만 수정되기 때문에 재 할당 하는 과정에서 효율적입니다.
• ArrayList는 추가, 수정, 삭제시 O(N)입니다. 추가시 이후에 index가 모두 수정되어야 하기때문에 재할당 하는 과정이 O(N) 입니다. 하지만 탐색에서 O(1) 입니다.
• LinkedList는 추가,수정,삭제,탐색 모두 O(N)입니다. index를 찾는건 O(N)이지만 index의 값을 바꾸는건 O(1)만 소요하기 때문입니다.

ArrayList와 Vector는 어떠한 차이가 있나요?

동기화: Vector는 모든 메서드가 synchronized되어 있어 스레드 안전하지만, ArrayList는 동기화되지 않아 단일 스레드 환경에서 성능이 더 우수합니다.
확장 크기: ArrayList는 크기를 1.5배로 확장하고, Vector는 2배로 확장합니다.

최적화 문제 : vector는 모든 메서드에 synchronized 가 되어있습니다
따라서 모든 ArrayList에 사용이 필요한 부분만 동기화(synchronized)를 사용 하여 최적화를 적용하는 것이 유리합니다.

Stack과 Queue가 무엇인가요?

Stack: LIFO (Last In, First Out) 구조로, 가장 나중에 추가된 요소가 가장 먼저 제거됩니다. 주요 메서드로 push, pop, peek 등이 있습니다.

• 웹브라우저의 뒤로가기

Queue: FIFO (First In, First Out) 구조로, 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 주요 메서드로 add, poll, peek 등이 있습니다.

• 대기열(먼저들어온 순서대로 처리하는)

  스택은 어디에 쓰이고 큐는 어디에 쓰이는지 ?

Set이 무엇이고, 구현 클래스가 무엇이 있는지 설명해 주세요.

Set은 중복 요소를 허용하지 않는 컬렉션입니다.
구현 클래스: HashSet (순서 없음), LinkedHashSet (삽입 순서 유지), TreeSet (정렬된 순서 유지)

Set에서 중복 요소를 어떻게 걸러내는지 설명해 주세요.

HashSet은 내부적으로 해시 값을 사용하여 중복을 제거하며, 같은 해시 값을 갖는 요소는 동일한 것으로 간주됩니다. equals 메소드로 해시값이 존재하는지 탐색합니다.

• hashCode() 메서드: 요소가 추가될 때, 먼저 hashCode() 메서드를 호출하여 해시 값을 계산합니다. 이 해시 값이 동일한 경우, 같은 해시 버킷에 저장됩니다.
• equals() 메서드: 해시 값이 같더라도 실제로 동일한 객체인지 확인하기 위해 equals() 메서드를 호출합니다. equals() 메서드가 true를 반환하면 동일한 객체로 간주하여 중복을 제거하고, 새로운 요소를 추가하지 않습니다

TreeSet은 요소를 정렬하여 비교하므로, 동일한 요소가 추가될 경우 중복으로 판단하고 추가하지 않습니다.

HashSet은 32비트 해시값으로 중복을 확인합니다. TreeSet은 TreeSet은 정렬 되기 때문에 해당 노드에 같은 요소가 있다면 충돌

Map이 무엇이고, 구현 클래스가 무엇이 있는지 설명해 주세요.

Map은 키-값 쌍으로 데이터를 저장하는 컬렉션입니다. 키는 중복을 허용하지 않으며, 값은 중복될 수 있습니다. (키값에 해시코드, equals 메서드 존재)
구현 클래스: HashMap (순서 없음), LinkedHashMap (삽입 순서 유지), TreeMap (정렬된 순서 유지), Hashtable (동기화 지원)

HashMap은 어떻게 동작하나요?

HashMap은 해싱을 기반으로 키와 값을 저장합니다. 키의 해시 값을 통해 특정 버킷(bucket)에 저장되며, 충돌이 발생할 경우 체이닝 기법(Linked List)이나 트리(Tree)로 관리합니다.

hash 충돌관리 ? 처음엔 체이닝 기법으로 관리하고 이후에 트리 구조로 관리합니다.

HashMap의 최악의 시간 복잡도를 설명해 주세요.

최악의 시간 복잡도는 충돌이 심해 모든 요소가 하나의 버킷에 체이닝될 경우, O(n)입니다. 이를 방지하기 위해, 자바 8 이후로는 체이닝이 일정 길이를 넘을 경우 트리 구조로 변환하여 최악의 경우를 O(log n)으로 줄입니다.

arrayList처럼 탐색하는걸 막기위해서 ..?