Set, Queue

Set

• Set 은 순서와 상관없이, 중복되는 것을 방지하고 원하는 값이 포함되어 있는지를 확인하는 것이 주 용도다.

• Set 을 상속받은 클래스는 HashSet, TreeSet, LinkedHashSet 이 포함되어 있다. -> 정렬 때문에 세가지 클래스의 성능 차이가 발생한다.

  • HashSet : 순서가 전혀 필요 없는 데이터를 해시테이블에 저장한다. Set 중 가장 성능이 좋다.

  • TreeSet : 저장된 데이터의 값에 따라서 정렬되는 셋이다. red-block(이진탐색트리) 이라는 트리 타입으로 값이 저장되며 HashSet 보다 약간 성능이 느리다.

    • red-block : 각 노드를 빨강, 검정색으로 구분하여, 데이터를 쉽게 찾을 수 있는 이진트리를 말한다.

  • LinkedHashSet : 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 저장된 순서에 따라서 값이 정렬된다. 대신 성능이 이 셋중에 가장 나쁘다.

Queue 가 필요한 이유(LinkedList 클래스에서 Queue 인터페이스 구현)

• LinkedList 의 자료구조를 간단히 설명하면, A - B - C 의 형태로 이어져있다고 할 때, 한 데이터에서 가장 근접한 자료의 정보 밖에 알지 못한다.

• 배열의 중간에 있는 데이터가 지속적으로 삭제되고, 추가될 경우에는 LinkedList가 배열보다 메모리 공간 측면에서 훨씬 유리하다.

  • Vactor, ArrayList 의 경우에는, 각 위치가 정해져있고 그 위치로 데이터를 찾는다.

  • 그런데 맨 앞의 데이터를 삭제하면, 그 뒤에 있는 값들은 하나씩 앞으로 위치를 이동해야 제대로 된 위치의 값을 가지게 된다.

  • 그에 반해 LinkedList 는 중간에 있는 데이터를 삭제하면, 지운 데이터의 앞에 있는 데이터와 뒤에 있는 데이터를 연결하면 그만이다.

• LinkedList 는 List 인터페이스 뿐 아니라, Queue, Deque 인터페이스도 구현하고 있다.

• Queue 는 FIFO(First In First Out) 의 자료구조로 먼저 들어온 데이터가 먼저 나간다.

• Deque 는 Queue 를 상속받은 인터페이스, 맨 앞에 데이터를 넣거나 빼는 작업, 맨 뒤에 데이터를 빼고 넣는 작업을 수행하는데 용이한 클래스이다.