Java 자료구조 Collection과 Map

자바에서 많이 쓰는 자료구조는 크게 2개로 나눌 수 있습니다. Collection과 Map 인터페이스(interface)입니다. 여러 종류의 자료구조가 있는 만큼 해당 작업에 적합한 자료구조를 선택하고 사용하는 것이 중요합니다. 그러기 위해서는 어떠한 특징들, 장단점을 가지고 있는 알아보도록 하겠습니다.

미리 알면 좋은 것들

• Java interface와 class
• Java Iterable
• Big O notation

자료구조 분류

인터페이스들을 구현한 클래스들은 아래와 같은 자료구조로 만들어졌습니다. 해당 자료 구조에 따라 특성이 다릅니다.

Interface	Resizable Array	Linked List	Hash Table	Hash Table + Linked List	Balanced Tree
Set			HashSet	LinkedHashSet	TreeSet
List	ArrayList	LinkedList
Queue/Deque	ArrayDeque	LinkedList
Map			HashMap	LinkedHashMap	TreeMap

자료구조에 따른 성능 비교

	Resizable array	Linked list	Hash Table(+Linked List)	Balanced tree
Indexing	Θ(1)	Θ(n)	Θ(1)	Θ(log n)
Insert/delete at beginning	Θ(n)	Θ(1)	Θ(n)	Θ(log n)
Insert/delete at end	Θ(1) amortized	Θ(1)	Θ(1) amortized	Θ(log n)
Insert/delete in middle	Θ(n)	search time + Θ(1)	Θ(n)	Θ(log n)
Wasted space (average)	Θ(n)[5]	Θ(n)	Θ(√n)	Θ(n)

• Resizable Array
  • Primitive type Array 를 사용하기 때문에 get/set에 성능이 좋음.
  • Array의 크기를 키우는 과정에서 많은 자원을 사용함. Linked List보다 add가 느림.
  • 공간적 효율이 가장 좋음.
• Linked List
  • Double Linked List를 사용하기 때문에 Array보다 add가 빠름.
  • 요소를 찾기 위해서는 모두 찾아야 하기 때문에 Array보다 get/set이 느림.
• Hash Table, Hash Table with Linked List
  • Hash Table을 사용하여 탐색하기 때문에 Linked List보다 get이 빠름.
  • Linked List로 Table을 구성할 경우에 순서를 유지할 수 있지만 탐색 속도가 느림.
• Balanced Tree
  • Hash를 트리에 저장하여, 대용량에서 빠른 Indexing과 Insert/Delete가 가능하다.
  • Insert/Delete 과정에서 불필요한 재배열 연산이 필요하다.

위에 나열한 성능 비교는 절대적이지 않습니다. 해당 데이터에 형태나, 연산에 따라 최적의 자료구조가 다르기 때문에 자료구조의 특성을 잘 이해하고 적용하는 것이 중요합니다.

Java 자료구조

컬렉션(Collection)

JAVA에 대표적인 자료구조 모음집 Collection Framework입니다. Interface로 구성되어 있으며, 자주 사용하는 List, Set, Queue 인터페이스가 여기에 속합니다. 또 Collection은 Iterable 인터페이스를 상속 받고 있습니다. 아래 그림에서 자세한 상속 관계들을 찾을 수 있습니다.

Java Collection Framework 구조

위 그림에 해당하는 내용은 아래 코드를 통해서 클래스와 인터페이스의 관계를 확인할 수 있다.

// LikedList 클래스 정의 일부
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
}

// HashSet 클래스 정의 일부
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    ...
}

맵(Map)

JAVA Collection Framework에는 속하지 않지만 많이 쓰는 자료구조 중 하나 이다.

Map은 Collection Framework가 아니다.

public interface Map<K,V> {
    // Query Operations
    ...
}

자료구조 비교

• List
  • 아무 위치에 추가/삭제/선택이 가능
  • 순서가 있고, 자료 중복 가능
• Queue
  • 제한된 추가/삭제/선택이 가능
  • 선입선출(FIFO)의 자료구조
• Set
  • 순서와 상관 없는 데이터의 집합
  • 자료 중복 불가능
• Map
  • Key, Value 쌍으로 추가/삭제/선택이 가능

사용 예시

public static void main(String[] args) {

    List<Integer> arrayList = new ArrayList<>();
    List<Integer> linkedList = new LinkedList<>();

    Queue<Integer> arrayQueue = new ArrayDeque<>();
    Deque<Integer> arrayDeque = new ArrayDeque<>();
    Queue<Integer> linkedListQueue = new LinkedList<>();
    Deque<Integer> linkedListDeque = new LinkedList<>();

    Set<Integer> hashSet = new HashSet<>();
    Set<Integer> linkedHashSet = new LinkedHashSet<>();
    Set<Integer> sortedSet = new TreeSet<>();

    Map<String, String> hashMap = new HashMap<>();
    Map<String, String> linkedHashMap = new LinkedHashMap<>();
    Map<String, String> treeMap = new TreeMap<>();
}