Skip to main content

Collection Framework

  • 기존 (JDK1.2 이전)에는 서로 다른 컬렉션 클래스를 사용해야 됬어서 각자의 방식을 사용해야 했으나, 이 후에는 Collection Framework를 구축함으로써 표준화된 방식으로 여러 컬렉션을 다룰 수 있게 되었고 객체지향적으로 설계 되었기 떄문에 사용법을 익히기에도 편리하며 재사용성이 높은 코드를 작성할 수 있다.

컬렉션 프레임워크의 핵심 인터페이스​

  • 크게 List, Set, Map 3가지 타입(인터페이스)가 존재.
  • 컬렉션 프레임워크의 실제 소스코드를 분석하는 것이 객체지향적인 설계능력을 향상시키는데 도움이 될 것임.
  • Collection 인터페이스는 저장된 데이터를 읽고, 추가하고, 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의하고 있음.
  • List 인터페이스는 ‘중복을 허용’하면서 ‘저장순서가 유지’되는 컬렉션을 구현하는데 사용.
  • Set 인터페이스는 ‘중복을 허용하지 않고’ ‘저장순서가 유지되지 않는’ 컬렉션을 구현하는데 사용.
  • Map 인터페이스는 ‘키와 값’을 하나의 쌍으로 묶어서 저장하는 컬렉션을 구현하는데 사용.

ArrayList​

  • List 인터페이스를 구현 → 중복 허용, 데이터 저장 순서 유지.

  • Object배열을 이용해서 데이터를 순차적으로 저장.

  • 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경하는 작업은 효율이 떨어진다.

    • 용량을 변경하는 작업이 효율이 떨어지는 이유는, 기존의 크기에서 더 늘어날 경우, 기존에 할당받은 공간에 붙여서 늘리는 것이아니라 늘어난 크기의 메모리 공간을 새로 할당 받고 기존의 공간을 가비지 컬렉터가 제거하는 식으로 작동되기 때문이다.

    나는 항상 ArrayList를 사용할 때 선언 시, 크기는 설정을 항상 하지 않았는데 해야하는 것이 맞는 것인가? 아니면 지금은 가비지 컬렉터 성능 등이 좋아져서 크게 이슈가 아닌 것일까? 혹은 크기를 선언 시 정하지 않으면 적당한 크기로 알아서 할당해주는 걸까 ?

  • 데이터 삭제의 경우 해당 값을 삭제하고 이후의 데이터를 순서대로 한칸 씩 위로 복사한다.

  • 해당 코드들을 직접 살펴보자. 오랜 경력의 프로그래머들에 의해서 작성된 것이기 때문에 프로그래밍 실력을 향상시키는데 많은 도움이 될 것임.

LinkedList​

  • 생성, 삭제 - O(1) / Array(array, arrayList)의 단점을 커버한다. Array는 크기를 변경할 수 없고(그렇기에 크기를 늘리려면 새로운 배열을 생성하거나 최초에 널널하게 생성하여 메모리 낭비를 초래한다.), 비순차적인 데이터의 추가 또는 삭제에 시간이 많이걸리지만(그 뒤의 값들의 위치를 변경해주어야하기 때문에) LinkedList는 이를 보완한다.
  • index 연산(읽기) 느림 - O(n) , 불연속적으로 연결된 것이기 때문에 앞에서부터 순서대로 조회해 나가야됨.
    • Array의 경우에는 연속적으로 연결되어있기 때문에 배열의 주소값 + n(index)*데이터타입의크기가 해당 값의 주소값이 되어 바로 찾을 수 있다.
  • 물리적 위치와 논리적 위치가 다름.(node 단위로 다음 node의 address만 알면되므로) 따라서 불연속적으로 존재하는 데이터를 서로 연결한(link) 형태이다.
  • 각 요소들은 자신과 연결된 다음 요소에 대한 참조와 데이터로 구성.
  • 다음 요소에 대한 참조만 보관하기에 이전요소에 대한 접근이 어려운데 이를 보완한 것이 doubleLinkedList이다. (이전 요소의 참조를 추가로 보관함.)
  • doubleLinkedList에서 첫 값과 마지막 값을 연결한 것이 doubleCircularLinkedList.

Stack과 Queue​

  • ArrayList, LinkedList 둘다 사용하여 구현가능
    • 단 스택은 순차적으로 저장이 가능한 ArrayList가 적합하며 큐는 앞에 값을 꺼내야하는 경우가 생기기 때문에 LinkedList가 적합하다. (스택을 LinkedList로 구현하면 마지막 값을 조회하는 것이 ArrayList보다 비효율적일 것이며, 큐를 ArrayList로 구현하면 맨앞 값을 꺼낼 때마다 데이터를 앞당겨줘야하므로 비효율적이다.)
  • LIFO / FIFO
  • 자바에서 스택은 Stack 클래스로 구현하여 제공하고 있지만 Queue는 인터페이스로 정의만 해놓았다. 대신 구현한 클래스들이 있어서 이 들 중 하나를 선택하여 사용하면 된다.
    • LinkedList도 Queue를 구현한 클래스여서 Queue의 기능이 모두 있다. 이외에도 PriorityQueue, ArrayDeque 등이 있음.
  • PriorityQueue - 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게된다. 배열을 저장공간으로 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장함.
  • Deque(Double-Ended Queue) - 양쪽 끝에 추가/삭제가 가능하다.

Iterator, ListIterator, Enumeration​

  • 컬렉션(Collection)에 저장된 요소에 접근하는데 사용되는 인터페이스들. ( iterator()메소드로 Collection의 Iterator 객체를 가져온 뒤, hasNext, next, remove 메소드로 주로 반복문과 함께 순차 접근하는 식으로 사용할 수 있다.)
  • Enumeration은 Iterator의 구버전, LIstIterator는 Iterator의 향상된 버전.
  • 이처럼 공통 인터페이스를 정의해서 표준을 정의하고 구현하여 표준을 따르도록 함으로써 코드의 일관성을 유지하여 재사용성을 극대화. (객체지향 프로그래밍의 중요한 목적)
  • Map인터페이스를 구현한 컬렉션 클래스는 keySet(), entrySet()을 통해 키와 값을 따로 set으로 얻은 후 iterator()메소드사용 가능.

Arrays​

  • 배열을 다루는데 유용한 메서드 정의. Arrays에 저장된 메소드는 모두 static.
  • copyOf(), copyOfRange()
  • fill(), setAll()
  • sort(), binarySearch()
  • equals(), toString()
  • asList()
  • parallelXXX(), spliterator(), stream()

Comparator와 Comparable​

  • 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있는 인터페이스
  • Comparable은 기본 정렬기준을 구현하는데 사용하고 Comparator는 다른 기준으로 정렬하고자할 때 Comparator를 구현하여 적용하는 식으로 사용할 수 있다.
  • Comparator ( compare(a, b); ) / Comparable ( compareTo(a); )

HashSet​

  • Set 인터페이스를 구현한 가장 대표적인 컬렉션.
  • 중복된 요소를 저장하지 않기 때문에 이미 저장되어있는 요소를 추가하면 false를 반환한다.
  • 저장순서를 유지하지 않으며 유지하고자 하면 LinkedHashSet을 사용할 수 있다.
    • 그러면 저장이 어떤 기준으로 되는 것일까? 혹은 조회시 어떤 기준으로 순서가 정해지는 것일까?

TreeSet​

  • 이진 검색 트리의 형태로 데이터를 저장하는 컬렉션.
  • 이진 검색 트리는 정렬, 검색, 범위검색에 높은 성능을 보임.
  • TreeSet은 이진 검색 트리의 성능을 향상시킨 ’레드-블랙 트리’로 구현되어 있다.
  • 이진 검색 트리
    • 트리 자료구조 기반.
    • 최대 2개의 자식노드를 가짐.
    • 왼쪽 자식은 부모보다 값이 작으며, 오른쪽 자식노드는 부모노드보다 값이 크다. (같은 경우는?)
  • 단일 값 검색과 범위 검색, 정렬에 강점이 있으나, 저장위치를 찾아서 저장하고 삭제 시 트리를 재구성하게 되는 상황이 생길 수 있으므로 추가/삭제에는 링크드 리스트 보다 시간이 더 걸린다.
  • 이미 저장할 때 정렬된 상태로 저장되기 때문에 조회시 따로 정렬할 필요는 없다.
  • subSet() - 범위검색 시 사용.

Tree ( BST )​

  • inoder, preorder, postorder
  • treeset, treemap (in JDK)

HashMap, HashTable​

Hash​

  • 검색을 위한 자료구조
  • 충돌을 방지하기위한 알고리즘.
  • 키값을 hash func에 넣어 value가 저장되어있는 실제 인덱스를 알 수 있다.
  • 파이썬의 딕셔너리도 해시기반의 방식이라 보면됨.
  • HashSet, HashMap (in JDK)
  • 해시 함수를 어떻게 만드느냐에따라 충돌을 줄일 수 있고 하다.

TreeMap​

Collections​

정리 & 요약​