티스토리 뷰

자바에서 많이 쓰는 자료구조는 크게 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를 트리에 저장하여, 대용량에서 빠른 IndexingInsert/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<>();
}
댓글
댓글쓰기 폼