[자료구조] Java Collections Framework 필수 개념과 활용법

자료구조와 알고리즘

알고리즘과 코딩 테스트를 준비할 때, 자료구조는 반드시 이해하고 넘어가야 하는 핵심 개념입니다. 자료구조는 데이터를 저장하고 조직화하는 방식으로, 알고리즘은 이 데이터를 처리하는 절차입니다. 문제 해결을 위해 적절한 자료구조를 선택하는 것을 효율적인 알고리즘을 구현하는 데 필수적입니다. 특히, Java 컬렉션 프레임워크는 문제를 해결할 때 적절한 자료구조를 선택하는 것은 효율적인 알고리즘을 구현하는 데 중요한 역할을 합니다.

자료구조의 기본 분류

자료구조는 크게 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Nonlinear Data Structure)로 나뉩니다.

• 선형 자료구조(Linear Data Structure)
  • 데이터가 일렬로 연결된 형태입니다.
  • 선형 자료구조에는 대표적으로 리스트(List), 스택(Stack), 큐(Queue), 덱(Deque)이 있습니다.
• 비선형 자료구조(Nonlinear Data Structure)
  • 데이터가 일렬로 나열되지 않고, 여러 요소가 복잡하게 연결된 형태를 가집니다.
  • 비선형 자료구조에는 대표적으로 그래프(Graph)와 트리(Tree)가 있습니다.
• 기타 자료구조
  • 선형 또는 비선형으로 분류되지 않는 집합(Set) 자료구조가 있습니다.
  • 보통 기타 자료구조 또는 집합 자료구조라고 합니다. 집합의 경우 데이터가 연결되지 않은 독립적인 형태를 취합니다.

Java Collections Framework

• Java : 자바 언어에서
• Collections : 일정 타입의 데이터[정보]를 수집해서
• Framework : 문제를 해결하기 위한 구조

Java Collections Framework는 자바 언어에서 다양한 자료구조를 구현하기 위해 제공되는 라이브러리입니다. 이 프레임워크는 데이터 수집, 저장, 검색, 조작을 효율적으로 처리할 수 있는 여러 클래스와 인터페이스로 구성됩니다. Collections Framework는 크게 세 가지 주요 인터페이스로 구성됩니다.

• List : 순서가 있는 데이터 컬렉션을 다룹니다.  ArrayList, LinkedList, Vector 등이 이에 해당합니다.
• Queue : 데이터가 들어간 순서대로 처리되는 큐 구조를 다룹니다. PriorityQueue, Deque 등이 대표적입니다. 
• Set : 중복되지 않는 데이터를 저장하는 컬렉션입니다. HashSet, LinkedHashSet, TreeSet 등이 포함됩니다.

위 그림에서 알 수 있듯이 인터페이스끼리 다중 상속이 가능하며, Collection을 구현한 클래스 및 인터페이스들은 모두 Java.util 패키지 내에 구현되어 있으며, 필요에 따라 여러 자료구조를 혼합하여 사용할 수도 있습니다.

Java의 대표 자료구조

Java에서는 성능을 고려해 효율적인 알고리즘을 구현하기 위해 다양한 자료구조를 제공합니다.

다음은 Java에서 자주 사용되는 대표적인 자료구조들입니다.

자료구조	주요 클래스	장점	단점
List	ArrayList	읽기 빠름, 동적 크기 지원	삽입/삭제 느림
	LinkedList	삽입/삭제 빠름, 메모리 효율적	읽기 느림, 메모리 사용량 증가
	Vector	동기화 지원, 스레드 안전성	동기화로 인한 성능 저하
	Stack	후입선출(LIFO) 구조, 메서드 제공 단순	특정 위치 접근이 느림
Set	HashSet	중복 제거, 빠른 검색	순서 보장 안됨
	LinkedHashSet	중복 제거, 입력 순서 유지	추가 메모리 사용
	TreeSet	정렬된 순서 유지, 검색 효율적	삽입/삭제 성능 저하
Queue	PriorityQueue	우선순위 기반 정렬, 효율적 큐 처리	삽입/삭제 제한적
	ArrayDeque	빠른 큐/덱 연산, 동적 크기 지원	동기화 지원 안됨
Map	HashMap	빠른 검색, Key-Value 구조	순서 보장 안됨
	LinkedHashMap	입력 순서 유지, 빠른 검색	메모리 사용 증가
	TreeMap	정렬된 순서 유지, 범위 검색 용이	삽입/삭제 성능 저하

StreamAPI와 연계

Java 8에서 도입된 Stream API를 통해 컬렉션을 더욱 효율적으로 다룰 수 있습니다.

예를 들어, List나 Set을 Stream으로 변환해 필터링, 매핑 등의 작업을 쉽게 처리할 수 있습니다.

// Stream filter
List<String> names = Arrays.asList("Kim", "Lee", "Park", "Choi");
List<String> filteredNames = names.stream()
                                  .filter(name -> name.startsWith("K"))
                                  .collect(Collectors.toList());
// Kim, Park

// Stream sort
List<Integer> numbers = Arrays.asList(3, 5, 1, 4, 2);
List<Integer> sortedNumbers = numbers.stream()
                                     .sorted()
                                     .collect(Collectors.toList());
// 1, 2, 3, 4, 5

부록 [Map은 Collection인가?]

아래 링크에서 Collections API에 대한 FAQ에서 왜 Map이 Collection Interface를 상속하지 않는지 설명합니다.

docs.oracle.com/javase/8/docs/technotes/guides/collections/designfaq.html#a14

Java Collections API Design FAQ

Map Interface [원문]

• Why doesn't Map extend Collection?
  • This was by design. We feel that mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface (or vice versa). Collection could be made to extend Map, but this raises the question: what are the keys? There's no really satisfactory answer, and forcing one leads to an unnatural interface.
  • Maps can be viewed as Collections (of keys, values, or pairs), and this fact is reflected in the three "Collection view operations" on Maps (keySet, entrySet, and values). While it is, in principle, possible to view a List as a Map mapping indices to elements, this has the nasty property that deleting an element from the List changes the Key associated with every element before the deleted element. That's why we don't have a map view operation on Lists.
  • If a Map is a Collection, what are the elements? The only reasonable answer is "Key-value pairs", but this provides a very limited (and not particularly useful) Map abstraction. You can't ask what value a given key maps to, nor can you delete the entry for a given key without knowing what value it maps to.

Map Interface [해설]

• 맵이 컬렉션을 확장하지 않는 이유는 무엇인가요? 
  • 이는 의도된 것입니다. 저희는 매핑은 컬렉션이 아니고 컬렉션은 매핑이 아니라고 생각합니다. 따라서, Map이 Collection 인터페이스를 확장하는 것은 의미가 없으며(또는 그 반대의 경우도 마찬가지입니다), Collection이 Map을 확장하도록 만들 수는 있지만 핵심이 무엇인가라는 의문이 생깁니다. 만족스러운 답은 없으며, 억지로 만들면 부자연스러운 인터페이스로 이어집니다.
  • 맵은 키, 값 또는 쌍의 컬렉션으로 볼 수 있으며, 이 사실은 맵의 세 가지 '컬렉션 보기 작업'(keySet, entrySet 및 값)에 반영되어 있습니다. 원칙적으로 인덱스를 요소에 매핑하는 맵으로 목록을 볼 수 있지만, 목록에서 요소를 삭제하면 삭제된 요소 이전의 모든 요소와 연결된 키가 변경된다는 불쾌한 속성이 있습니다. 그렇기 때문에 목록에는 맵 보기 작업이 없습니다.
  • 맵이 컬렉션인 경우 요소는 무엇인가요? 유일하게 합리적인 대답은 "키-값 쌍"이지만, 이는 매우 제한적인(그리고 특별히 유용하지 않은) 맵 추상화를 제공합니다. 주어진 키가 어떤 값에 매핑되는지 물어볼 수도 없고, 어떤 값에 매핑되는지 알지 못하면 주어진 키에 대한 항목을 삭제할 수도 없습니다.

Map Interface 결론

자주 묻는 질문 중 하나는 "Map은 Collection에 속하는가?"입니다. 이에 대한 답변은 "아니요"입니다.

이는 설계상 Map이 Collection 인터페이스를 상속하지 않도록 의도되었기 때문입니다.

• Map과 Collection의 차이점
  • 단일 데이터 처리: Collection 인터페이스를 구현하는 클래스들은 일반적으로 단일 데이터를 다루는 반면, Map은 Key-Value 쌍을 다룹니다.
  • 반복 가능성: Map은 구조상 Key와 이에 대응되는 Value를 가진다는 특징 때문에 Iterable 인터페이스를 적용하기 어렵습니다.
  • 상속 모델링: Java에서 상속은 특정 공통성을 모델링하는 것인데, Map과 Collection은 기본적으로 다른 개념이므로 상속하는 것이 자연스럽지 않습니다.

이러한 이유로, Map은 별도의 인터페이스로 유지되며, Collection 인터페이스와는 구분됩니다.

Ref.

https://st-lab.tistory.com/142

http://javabeans.asia/