JAVA Collections Framework

컬렉션 프레임워크 Collections Framework

• 다수의 객체(컬렉션)를 다루기 위한 표준화된 프로그래밍 방식
• 많은 데이터를 쉽고 편리하게 다룰 수 있는(저장, 삭제, 검색, 정렬) 다양한 클래스를 제공
  • ex) Vector, ArrayList, HashSet...
    
    
    

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

    1. List

• 순서가 있는 데이터의 집합. 중복 O
• 구현 클래스 : ArrayList, LinkedList, Stack, Vector ...

  2. Set

• 순서를 유지하지 않는 데이터의 집합. 중복 X
• 구현 클래스 : HashSet, TreeSet ...
• List와 Set의 공통 부분을 추출하여 정의한 것이 Collection 인터페이스*

  3. Map

• key와 value가 쌍으로 이루어진 데이터의 집합
• 순서는 유지되지 않고, 키는 중복을 허용하지 않고 값은 중복을 허용한다
• 구현 클래스 : HashMap, TreeMap, HashTable, Properties ...
  
  

---

컬렉션 프레임워크의 클래스

ArrayList

• 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일하나 Vector는 자체적으로 동기화 처리가 되어있다는 점에서 차이가 있음
• 저장순서가 유지되고 중복을 허용함
• 데이터의 저장공간으로 배열을 사용 -> 모든 종류의 객체 저장 가능
• Object[]로 autoboxing에 의해 기본형이 참조형으로 자동 변환됨

  list.add(1); 
  // list.add(new Integer(1));

배열의 장단점

• 구조가 간단하고 데이터를 읽는 데 걸리는 시간(access time)이 짧다
• 연속적이므로 배열 요소의 주소를 쉽게 알 수 있다

---

• 크기를 변경할 수 없다
  • 크기를 변경해야 하는 경우 새로운 배열을 생성하고 데이터를 복사해야 함
  • 크기 변경을 피하기 위해 큰 배열을 생성하면 메모리가 낭비됨
• 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다
  • 데이터를 추가하거나 삭제하기 위해 다른 데이터를 옮겨야 하기 때문
  • 단, 순차적인 데이터의 추가(끝에 추가)나 삭제(끝부터 삭제)는 빠르다

LinkedList

• 베열의 단점을 보완
• 불연속적으로 존재하는 데이터를 연결(link)
  • 데이터의 삭제 : 단 한 번의 참조 변경만으로 가능
  • 데이터의 추가 : 한 번의 Node 객체 생성과 두 번의 참조 변경만으로 가능
• 단, 데이터 접근성이 나쁘다는 단점이 있음(바로 다음 요소가 아닌 다른 요소에 대해)

   class Node {
     Node next;
     Object obj;
   }

  • dobuly linked list : 이중 연결 리스트로 접근성 향상
    • java에서 채택하고 있는 LinkedList 방식

      class Node {
      Node next;
      Node previous;
      Object obj;
      }

    • doubly circular linked list : 이중 원형 리스트
      • 마지막 요소가 첫 번째 요소를 참조하고 있음
        

ArrayList와 LinkedList의 성능 비교

1. 순차적으로 데이터를 추가/삭제 : ArrayList
2. 비순차적으로 데이터를 추가/삭제 : LinkedList
3. 접근 시간(Access Time) : ArrayList
   • 인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

     ArrayList는 읽기(접근시간)이 빠른 반면 변경(데이터의 추가, 삭제)은 느리다. 단, 순차적인 추가 삭제는 더 빠르다. 성능을 높이려고 배열의 크기를 크게 할 시 비효율적인 메모리 사용이 발생한다.
     Linked List는 읽기(접근시간)은 느린 반면 변경(데이터의 추가, 삭제)은 빠르다. 단, 데이터가 많을수록 접근성이 떨어진다.

---

스택과 큐

스택 Stack

• LIFO(Last In First Out) 구조. 마지막에 저장된 것을 제일 먼저 꺼낸다
• push() 추가 pop() 삭제 peek() 조회
• 활용 : 수식 계산, 수식 괄호 검사, 워드 프로세스의 undo/redo, 웹브라우저 뒤로가기

  큐 Queue

• FIFO(First In First Out) 구조. 제일 먼저 저장한 것을 제일 먼저 꺼낸다
• offer() 추가 poll() 삭제 peek() 조회
• LinkedList는 Queue 인터페이스를 구현한 클래스다
• 활용 : 최근 사용 문서, 인쇄작업 대기목록, 버퍼(buffer)

---

Iterator, ListIterator, Enumeration

• 컬렉션에 저장된 데이터에 접근하는데 사용되는 인터페이스
• Enumeration은 Iterator의 구버전
• ListIterator는 Object previous()로 양방향 접근이 가능하여 Itreator의 접근성을 향싱시킴
• boolean hasNest() 확인 Object next() 읽기

Iterator

• 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것

  • 선언된 컬렉션 클래스(List, Set)가 변경되어도 조회하는 코드를 변경할 필요가 없음 (다형성의 원칙)

• 컬렉션에 iterator()를 호출하여 Iterator를 구현한 객체를 얻어서 사용

  List list = new ArrayList();
  Iterator it = list.iterator();
  
  while(it.hasNext()) {
    System.out.println(it.next()); // return Object
  } 

• Iterator는 일회용이기 때문에 사용하고 나면 다시 재할당해주어야 한다

• Map에는 iterator() 메소드가 없기 떄문에 ketSet(), entrySet(), values() 메소드를 이용하여 Collection을 반환받아 사용해야 한다

  Map map = new HashMap();
  ...
  Iterator it = map.entrySet().iterator();

  
  
  

  ---

  
  

Arrays

• Methods

  • toString() 출력 deepToString() 다차원 배열 출력
  • copyOf(), coptOfRange() 복사

    int[] arr= {0, 1, 2, 3, 4};
    // 새로운 배열을 생성하여 반환
    int[] arr2 = Arrays.copyOf(arr, 3); // arr2 = [0, 1, 2]
    int[] arr3 = Arrays.copyOfRange(arr, 1, 4); // arr3 = [1, 2, 3]

  • fill(), setAll() 채우기

    int[] arr = new int[5];
    Arrays.fill(arr, 9); // arr = [9, 9, 9, 9, 9]
    Arrays.setAll(arr, (i) -> (int) Math.ramdom() * 5 + 1); //arr = [4, 2, 4, 3, 3]

  • sort() 정렬 binarySearch() 이진탐색(정렬된 배열에서만 가능)
  • equals() 비교 deepEquals() 다차원 배열 비교

  
  
  

  ---

  
  

Comparator와 Comparable

• 객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스

  • Comparable 기본 정렬 기준을 구현하는데 사용
  • Comparator 기본 정렬 기준 외에 다른 기준으로 정렬하고자 할 때 사용

  
  
  

  ---

  
  

HashSet

• 순서가 없고 중복을 허용하지 않는 Set 인터페이스를 구현한 대표적인 컬렉션 클래스

• 순서를 유지하려면 LinkedHashSet 클래스를 사용

• 정렬하기 위해서는 list로 형변환해주어야 함 Collections.sost(List list)

• Hashset은 객체를 저장ㅈ하기 전에 같은 객체가 기존에 존재하는지 확인해서 있으면 저장하지 않고 없으면 저장한다

  • boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출

  • equals()와 hashCode()가 오버라이딩 돼있어야 함

    public static void main(String[] args) {
    HashSet = set = new HashSet();
    
    set.add("abc");
    set.add("abc");
    set.add(new Person("David", 19));
    set.add(new Person("David", 19));
    
    System.out.println(set);
    }
    
      class Person {
        String name;
        int age;
    
        Persin(String name, int age) {
          this.name = name;
          this.age = age;
        }
    
        @Override
        public int hashCode() {
          return Objects.hash(name, age); 
        }
    
        @Override
        public boolean equals(Object obj) {
          if (!(obj instanceof Person)) return false;
    
          Person p = (Person) obj;
          return this.name.equals(p.name) && this.age == p.age;
        }
    
        public String toString() {
          return name + ":" + age;
        }
      }
      

    [David:19, abc]
    // `equals()`와 `hashCode()`가 오버라이딩되어있지 않은 경우
    // [David:19, David:19, abc]

  TreeSet

  • 이진 탐색 트리(binary search tree)로 구현. 범위 검색과 정렬에 유리한 컬렉션 클래스
    • 이진 트리의 한 종류로 부모보다 작은 값은 왼쪽 큰 값은 오른쪽에 저장
    • 데이터 많아질수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)
  • 이진 트리는 모든 노드가 최대 2개의 하위 노드를 가짐
  • 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

    class TreeNode {
      TreeNode left;
      Object element;
      TreeNode right;
    }

  • HashSet보다 데이터의 추가, 삭제에 시간이 더 걸림

  트리 순회(tree traversal)

  • 이진트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다
  • 전위(preorder), 후위(postorder) 순회법이 있으며 중위(inorder) 순회하면 오름차순으로 정렬된다