Java에서 여러 자료구조 구현하기

 

---

Java Collection Framework (JCF)

 

이번 글에서는 Java로 코딩테스트를 볼 때에 자주 쓰이는 여러 자료구조를 구현할 때, 어떤 인터페이스와 어떤 구현 클래스를 사용해야 할지를 정리하려고 한다.

여러 자료구조 역할을 수행하는 인터페이스와 그 인터페이스를 구현하는 여러 구현체들에 대해 완전히 파악해보자!

 

 

Java Collection Framework (JCF) : 여러 개의 데이터를 효율적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스 집합

JCF 덕분에, 자바에서는 리스트, 큐, 스택과 같은 자료구조를 쉽게 구현할 수 있다.

 

각각의 자료구조 역할을 수행하는 인터페이스와 해당 인터페이스를 구현하는 여러 구현 클래스들에 대해 알아보자!

 

---

List

 

List : 순차적으로 데이터를 저장하는 자료구조인 리스트 역할을 수행하는 인터페이스

List 인터페이스를 구현하는 클래스들은 다음과 같다.

• ArrayList
  • 내부적으로 배열을 사용하여 데이터를 저장한다.
  • 값을 조회하는 것이 굉장히 빠르다.
  • 일반적으로 가장 효율이 좋다.
• LinkedList
  • 내부적으로 연결 리스트를 사용하여 데이터를 저장한다.
  • 리스트 중간에서의 데이터 삽입/삭제가 빈번하게 일어나는 경우에 적합하다.
• Vector
  • ArrayList와 비슷하지만, 동기화된 메서드를 제공한다.
  • 멀티스레드 환경에서 안전하게 사용해야 할 때 적합하다.

 

즉, 일반적으로는 ArrayList 클래스를 구현체로 사용하고, 정말 특별한 상황에서는 LinkedList 클래스를 구현체로 사용하면 된다!

 

---

Queue

 

Queue : FIFO( First-In-First-Out ) 특성을 가지는 자료구조인 큐 역할을 수행하는 인터페이스

Queue 인터페이스를 구현하는 클래스들은 다음과 같다.

• ArrayDeque
  • 근본적으로는 덱을 구현하기 위한 클래스지만, 큐와 스택 역할도 수행 가능하다.
  • 데이터 조회/삽입/삭제 전부 성능이 우수하다.
  • 메모리도 적게 사용한다.
• LinkedList
  • 내부적으로 연결 리스트를 사용하여 데이터를 저장한다.
  • 특정 원소 접근 시의 성능이 떨어진다.
• PriorityQueue
  • 우선순위 큐를 구현할 수 있다.

 

즉, 웬만하면 ArrayDeque 클래스를 구현체로 사용하면 된다!

 

---

Stack

 

Stack : LIFO( Last-In-First-Out ) 특성을 가지는 자료구조인 스택 역할을 수행하는 인터페이스

Stack 인터페이스를 구현하는 클래스들은 다음과 같다.

• Stack
  • 가장 기본적인 스택 구현 클래스이다.
  • 인터페이스와 이름이 같다.
  • Vector 클래스를 상속한다.

 

그렇다면, 스택은 Stack 인터페이스와 Stack 구현 클래스를 사용하면 되는 것인가?

위에서 언급했듯이, ArrayDeque도 스택 역할을 수행할 수 있다.

게다가, ArrayDeque가 Stack보다 성능이 더 좋다.

 

즉, 웬만하면 ArrayDeque 클래스를 스택으로 사용하면 된다!

단, 동기화 처리 및 스레드 안전이 중요하다면 Stack을 사용해야 한다.

Stack 클래스는 Vector 클래스를 상속했기 때문에, 동기화 처리가 되어있기 때문이다.

 

---

Map

 

Map : Key-Value 쌍을 저장하는 자료구조 역할을 수행하는 인터페이스

Map 인터페이스를 구현하는 클래스들은 다음과 같다.

• HashMap
  • 해시 테이블을 사용하여 Key-Value 쌍을 저장한다.
  • 효율적으로 동작하기 때문에, 일반적으로 가장 많이 사용된다.
• TreeMap
  • 레드-블랙 트리를 사용하여 Key-Value 쌍을 저장한다.
  • Key 값을 기준으로 데이터를 정렬된 순서로 저장하는 특징을 가진다.
• LinkedHashMap
  • 해시 테이블과 연결 리스트를 사용하여 Key-Value 쌍을 저장한다.
  • 입력한 순서대로 데이터를 저장하는 특징을 가진다.
• ConcurrentHashMap
  • HashMap과 비슷하지만, 멀티 스레드 환경에서 안전하게 사용할 수 있다.
• Hashtable
  • HashMap과 비슷하지만, 멀티 스레드 환경에서 안전하게 사용할 수 있다.
  • 그러나, 성능 상 ConcurrentHashMap보다 좋지 않다.

 

즉, 일반적인 상황에서는 HashMap 클래스를 구현체로 사용하면 된다!

하지만 다음과 같은 특별한 상황에서는 각각의 클래스를 사용하면 된다.

• TreeMap : Key 값을 기준으로 데이터를 정렬된 순서로 저장해야 할 때
• LinkedHashMap : 입력한 순서대로 데이터를 저장해야 할 때
• ConcurrentHashMap : 멀티 스레드 환경에서 안전하게 사용해야 할 때

 

---

Set

 

Set : 중복을 허용하지 않고 데이터를 저장하는 자료구조 역할을 수행하는 인터페이스

Set 인터페이스를 구현하는 클래스들은 다음과 같다.

• HashSet
  • 내부적으로 HashMap을 사용하여 데이터를 저장한다.
  • 효율적으로 동작하기 때문에, 일반적으로 가장 많이 사용된다.
• TreeSet
  • 내부적으로 TreeMap을 사용하여 데이터를 저장한다.
  • 데이터를 정렬된 순서로 저장하는 특징을 가진다.
• LinkedHashSet
  • 내부적으로 LinkedHashMap을 사용하여 데이터를 저장한다.
  • 데이터를 삽입한 순서대로 저장하는 특징을 가진다.

 

즉, 일반적인 상황에서는 HashSet 클래스를 구현체로 사용하면 된다!

하지만 다음과 같은 특별한 상황에서는 각각의 클래스를 사용하면 된다.

• TreeSet : 데이터를 정렬된 순서로 저장해야 할 때
• LinkedHashSet : 데이터를 삽입한 순서대로 저장해야 할 때

 

---

ArrayDeque 메서드

 

스택과 큐를 구현할 때는 일반적인 상황에서는 ArrayDeque가 시간적으로나, 공간적으로나 제일 좋다!

따라서 코딩 테스트에서 ArrayDeque는 꽤 자주 쓰인다.

 

ArrayDeque가 제공하는 메서드를 정리하면 다음과 같다.

 

데이터 삽입

• add, push 계열 : 용량 초과 시 예외를 발생시킨다.
• offer 계열 : 데이터 삽입 성공 시 true를 반환하고, 용량 초과 시 false를 반환한다.

 

데이터 제거(추출)

 

• remove, pop 계열 : 데이터가 없을 시 예외를 발생시킨다.
• poll 계열 : 데이터가 없을 시 null을 반환한다.

 

데이터 조회

 

• get 계열 : 데이터가 없을 시 예외를 발생시킨다.
• peek 계열 : 데이터가 없을 시 null을 반환한다.

 

---

정리

 

지금까지 자바로 여러 자료구조를 구현하는 방법과, 특히 ArrayDeque의 여러 메서드를 살펴보았다.

코딩 테스트 혹은 프로젝트에서 유용하게 써먹도록 하자!

 

 

---

 

 

(참고)

 

https://adjh54.tistory.com/138

https://adjh54.tistory.com/141

https://vanslog.io/posts/language/java/why-use-deque-instead-of-stack/