Class12(자료구조)

2023. 01. 18. 수업내용 정리

자료구조

자료구조

• 자바에서 자료구조는 어떠한 데이터를 쉽게 가공/처리하기 위해 사용한다.
  
  

  Collection

• Collection(인터페이스, java.util.Collection) 자료구조는 순서가 있는 데이터 혹은 데이터의 집합에 대한 단일 구조를 가진다.

  
  
  

  List

  • List(인터페이스, java.util.List) 자료구조는 순서가 있는 데이터를 다루기 위해 사용한다.
    • 메서드
      • add(T t) : 매개변수 T 타입의 객체 t를 List의 끝(마지막 자리)에 추가한다.
      • add(int i, T t) : 매개변수 T 타입의 객체 t를 List의 i번째 인자가 될 수 있도록 추가한다.
      • addAll(Collection<? extends T> c) : 매개변수 c가 가지는 모든 인자를 끝에 추가한다.
      • addAll(int i, Collection<? extends T> c) : 매개변수 c가 가지는 모든 인자 중 첫번째 인자가 i번째 인자가 될 수 있도록 모두 추가한다.
      • clear() : List 객체가 가지고 있는 모든 인자를 제거한다.
      • contains(Object o) : List 객체가 가지고 있는 인자 중 매개 변수 o와 equals() 메서드 비교 결과가 true인 것을 가지고 있는가에 대한 여부 (boolean)를 반환한다.
      • containsAll(Collection<? extends T>c) : 매개 변수인 c가 가진 모든 인자를 호출 대상이 되는 List 객체가 모두 가지고 있는지에 대한 여부(boolean)를 반환한다. 가지고 있는가에 대한 여부는 contains와 동일하다.
      • get(int i) : i번째 인자를 반환한다.
      • indexOf(Object o) : List 객체가 가지고 있는 인자 중 매개 변수 o와 equals() 비교 결과가 true인 첫번째 인자의 순번(int)을 반환한다.
      • isEmpty() : 인자가 있는가 없는가에 대한 여부(boolean)을 반환한다.
      • iterator() : List 객체가 가지고 있는 인자를 반복할 수 있는 반복자(Iterator<T>)를 반환한다.
      • lastIndxOf(Object o):List객체가 가지고 있는 인자 중 매개 변수 o와 equals() 비교 결과가 true인 마지막 인자의 순번(int)을 반환한다.
      • remove(int i) : List 객체가 가지고 있는 인자 중 그 순번이 i인 인자를 제거한다. 후행하는 인자의 순번은 당겨진다.
      • removeAll(Collection<?> c) : List객체가 가지고 있는 인자 중 c가 가진 인자와 equals() 비교 결과가 true인 모든 인자를 제거한다.
      • set(int i, T t): List 객체가 가지고 있는 인자 중 i번째 인자의 값을 매개 변수인 t로 바꾼다. 바뀌어진 이전 T타입의 객체를 반환한다.
      • size() : List 객체가 가지고 있는 인자의 개수를 반환한다.
      • toArray() : List 객체가 가지고 있는 인자들을 Object[] 타입으로 반환한다.
      • toArray(T[] ts) : List 객체가 가지고 있는 인자들을 T[] 타입의 객체에 대입하여 반환한다.
    • 하위 타입
      • ArrayList<T>(클래스,java.util.List) 자료구조는 인자 사이에 연결 고리 없이, 데이터에 접근할 수 있어, 인자에 접근하는 속도는 빠른 대신, 데이터를 추가하거나 삭제하는 속도가 느리다.
        • 인덱스를 통한 데이터 접근의 시간 복잡도: O(1)
        • 데이터의 삽입 및 삭제에 대한 시간 복잡도 : O(n)
      • LinkedList<T>(클래스,java.util,LinkedList) 자료구조는 각 인자가 인접한 인자를 기억하고 있는 형식이어서 인자에 접근하는 속도는 느린 대신, 데이터를 추가하거나 삭제하는 속도가 빠르다.
        • 인덱스를 통한 데이터 접근의 시간 복잡도 : O(n);
        • 데이터의 삽입 및 삭제에 대한 시간 복잡도 : O(1);
      • Vector<T>(클래스,java.util.Vector) 자료구조는 동기화된(Synchronized) ArrayList<T>와 같다.
      • Stack<T>(클래스,java.util.Stack) 자료구조는 주로 선입후출의 기능(push(), pop())을 사용하기 위해 사용한다.

  
  
  

  Set

  • Set(인터페이스, java.util.Set) 자료구조는 순서가 없는, 집합적인 데이터를 다루기 위해 사용한다.
    • 메서드
      • add(T t) : 매개변수인 t를 Set의 인자로 추가한다.
      • addAll(Collection<? extends T> c) : 매개변수 c가 가지는 모든 인자를 추가한다.
      • clear() : 모든 인자를 제거한다.
      • contains(Object o) : Set 객체가 가지고 있는 인자 중 매개 변수 o와 equals() 메서드 비교 결과가 true인 것을 가지고 있는가에 대한 여부 (boolean)를 반환한다.
      • containsAll(Collection<? extends T>c) : 매개 변수인 c가 가진 모든 인자를 호출 대상이 되는 Set 객체가 모두 가지고 있는지에 대한 여부(boolean)를 반환한다. 가지고 있는가에 대한 여부는 contains와 동일하다.
      • isEmpty() : 인자가 있는가 없는가에 대한 여부(boolean)을 반환한다.
      • iterator() : Set 객체가 가지고 있는 인자를 반복할 수 있는 반복자(Iterator<T>)를 반환한다.
      • remove(T t) : Set 객체가 가지고 있는 인자 중 매개 변수 t와 equals() 호출 결과가 true인 인자를 제거한다.
      • removeAll(Collection<?> c) : Set객체가 가지고 있는 인자 중 c가 가진 인자와 equals() 비교 결과가 true인 모든 인자를 제거한다.
      • size() : Set 객체가 가지고 있는 인자의 개수를 반환한다.
      • toArray() : Set 객체가 가지고 있는 인자들을 Object[] 타입으로 반환한다.
      • toArray(T[] ts) : Set 객체가 가지고 있는 인자들을 T[] 타입의 객체에 대입하여 반환한다.
    • 하위 타입
      • HashSet(클래스, java.util.HashSet)자료구조는 순서가 없는, 집합적인 데이터를 다루기 위해 사용한다.
      • ScoredSet(인터페이스,java.util.ScoreSet)집합적인 데이터를 정렬하여 다루기 위해 사용한다.
        • 하위 타입
          • TreeSet(클래스,java.util.TreeSet)집합적인 데이터를 정렬하여 다루기 위해 사용한다.

Map

• Map(인터페이스, java.util.Map) 자료구조는 순서와 관계 없고, 키와 값 쌍(Key-Value-Pair)으로 이루어진 데이터를 다룰때 사용한다.
  • 객체 메서드
    • clear() : 가지고 있는 키와 값 쌍을 모두 제거한다.
    • containsKey(Object o) : 가지고 있는 쌍 중에 키가 전달된 o와 동일한 쌍이 있는가의 여부(boolean)를 반환한다.
    • containsValue(Object o) : 가지고 있는 쌍 중에 값이 전달된 o와 동일한 쌍이 있는가의 여부(boolena)를 반환한다.
    • get(Object o) : 가지고 있는 쌍 중에 키가 전달된 o와 같은 쌍의 V타입의 객체인 값을 반환한다.
    • getOrDefault(Object o, V v) : 가지고 있는 쌍 중에 키가 전달된 o와 같은 쌍이 있다면 그 값을, 없다면 전달받은 v를 반환한다.
    • keySet(): 가지고 있는 쌍들의 키만 모아 Set<K> 타입의 객체로 반환한다.
    • put(K k, V v) : 키가 k이고 값이 v인 키-값 쌍을 추가한다. 단, 이미 존재하는 쌍 중에 키가 k와 같은 쌍이 있다면 기존 쌍의 값을 새로운 값으로 대체하고 대체된 값을 반환한다.
    • putAll(Map<? extneds K, ? extends V>m) : Map 타입의 매개변수 m이 가지고 있는 모든 키-값 쌍을 호출 대상이 되는 Map의 인자로 복사한다.
    • putIfAbsent(K k, V v): 키가 k이고, 값이 v인 키-값 쌍을 추가한다. 단, 키 k로 접근한 쌍이 없거나, 그 값이 null인 경우에는 추가를 하고 null을 반환하며, 이미 존재한다면 v를 반환한다.
    • remove(Object o) : 가지고 있는 키-값 쌍 중 키가 o와 equals()에 대해 true인 쌍을 제거한다.
    • replace(K k, V v) : 가지고 있는 키-값 쌍 중 키가 k와 동일한 쌍에 대한 값을 v로 지정하고 대체된 V타입의 객체를 반환한다. 만약, 키가 k와 동일한 쌍이 없다면 아무 것도 하지 않고 null을 반환한다.
    • size() : 가지고 있는 키-값 쌍의 개수(int)를 반환한다.
    • values() : 가지고 있는 키-값 쌍의 값들을 가지는 Collection<V> 객체를 반환한다.
  • 하위 타입
    • HashMap(클래스, java.util.HashMap)자료구조는 순서와 관계 없고, 키와 값 쌍(Key-Value-Pair)으로 이루어진 데이터를 다룰 때 사용한다. 동기화를 보장하지 않는다.
    • Hashtable(클래스,java.util.Hashtalbe)자료구조는 순서와 관계 없고, 키와 값 쌍(Key-Value-Pair)으로 이루어진 데이터를 다룰 때 사용한다. 동기화를 보장한다.
    • `
    • (인터페이스,java.util.SortedMap`)자료구조는 엄밀히 얘기하면 키-값 쌍에는 순서가 없지만 키의 해시값을 기준으로 정렬을 하기 때문에 키-값 쌍을 키 기준으로 정렬하기가 쉽다.
      • 하위 타입
        • TreeMap(클래스,java.util.TreeMap)자료구조는 SortedMap 인터페이스를 구현한 대표 클래스이다.