자료구조 (JAVA 기준)

문제 모음

1. Collection F/W vs Collection's' class
2. Collection Framework의 구성
3. List의 구현체와 차이점
4. Set의 구현체와 차이점
5. Map의 구현체와 차이점
6. Red-Black 트리란?

---

해답

Q) Collection F/W vs Collections class

Collection 프레임워크는 다수의 데이터를 쉽고 효과적으로 처리할 수 있도록 표준화된 방법을 제공하는 자료구조와 알고리즘의 모임입니다.

Collections class는 Collection을 다루는 정적 메서드들을 제공하는 클래스입니다. 정적 메서드들을 제공하기 때문에 인스턴스를 생성하지 않고도 사용할 수 있습니다.

Q) Collection Framework의 구성

Collection framework의 가장 핵심적인 인터페이스로는 List, Set, Map이 있습니다. List와 Set은 Collection 인터페이스의 하위 인터페이스이고 Map은 이 둘과의 구조상의 차이로 Collection을 상속받지 않고 별도로 정의됩니다. List는  중복을 허용하고 순서가 있는 데이터 집합이고, Set은 중복을 허용하지 않는 데이터 집합이며, Map은 key-value 구조로 이루어진 데이터 집합이며 key는 중복을 허용하지 않고 value는 중복을 허용합니다.

Q) List의 구현체와 차이점

• ArrayList: 빠르고 크기 조절이 가능한 배열이며, 단방향 포인터 구조로 자료에 대한 순차적인 접근이 가능한 것이 장점입니다.
• LinkedList: 양방향 포인터로 데이터의 삽입, 삭제가 빈번할 경우 자주 쓰입니다. 
• Vector: ArrayList와 동작 방식은 비슷하나 동기화를 제공하기 때문에 thread-safe합니다.
  • Stack: LIFO 구조로 동작하는 Vector class의 자식 클래스입니다.

Q) Set의 구현체와 차이점

• HashSet: 순서를 유지하지 않는 구현체로 가장 빠른 임의의 접근 속도를 가집니다.
• LinkedHashSet: 삽입된 순서대로 데이터를 관리하며 중복을 허용하지 않습니다.
• TreeSet: Red-Black 트리를 이용해 오름차순으로 데이터를 정렬하는 Set입니다.

Q) Map의 구현체와 차이점

• HashMap: 동기화가 보장되지 않으나 그만큼 더 좋은 성능을 보입니다. Key와 value 값에 null 값이 허용되며 속도는 빠르나 안정성과 신뢰성이 낮습니다.
  • LinkedHashMap: FIFO 방식으로 순차적 조회를 가능하게합니다.
• HashTable: 동기화가 때문에 느리지만 동기화 lock을 이용해서 무결성을 보장합니다. 또한 key와 value에 null 값이 허용되지 않기 때문에 안정성과 신뢰성을 더욱 높입니다.
• TreeMap: Red-Black 트리를 이용해 오름차순으로 데이터를 정렬하는 Map입니다.  

Q) Red-Black 트리란?

레드 블랙 트리는 이진 트리 중에서도 성능을 향상시킨 트리로, 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줍니다.