[자료구조] 자바의 자료구조 개념 정리 - 2

Collection

List

List: 여러 항목을 순서대로 저장하는 자료 구조. 가변적인 크기를 가진 배열이라 할 수 있다.

 

List의 특징으로는 다음과 같다.

• 순서가 존재한다.
  • List의 각 요소들은 특정한 순서를 가지고 있다. 이는 요소들이 추가된 순서를 유지한다는 의미이다.
• 인덱스로 관리한다.
  • 각 항목은 0부터 시작하는 인덱스를 가지고 있어 해당 인덱스를 사용하여 요소에 접근할 수 있다.
• 동적으로 크기가 변경된다.
  • List는 일반적으로 크기를 동적으로 조정할 수 있는 가변적인 자료 구조이다.

public interface List<E> extends Collection<E> {

    // 요소 추가
    boolean add(E element);

    // 인덱스에 요소 추가
    void add(int index, E element);

    // 모든 요소 추가
    boolean addAll(Collection<? extends E> c);

    // 인덱스에 모든 요소 추가
    boolean addAll(int index, Collection<? extends E> c);

    // 리스트 비우기
    void clear();

    // 요소 포함 여부 확인
    boolean contains(Object o);

    // 모든 요소 포함 여부 확인
    boolean containsAll(Collection<?> c);

    // 해당 인덱스의 요소 반환
    E get(int index);

    // 해당 요소의 첫 번째 인덱스 반환
    int indexOf(Object o);

    // 리스트가 비어있는지 확인
    boolean isEmpty();

    // 해당 요소의 마지막 인덱스 반환
    int lastIndexOf(Object o);

    // 리스트 반복자 반환
    ListIterator<E> listIterator();

    // 지정된 인덱스에서 시작하는 리스트 반복자 반환
    ListIterator<E> listIterator(int index);

    // 요소 삭제
    boolean remove(Object o);

    // 인덱스에 해당하는 요소 삭제
    E remove(int index);

    // 컬렉션에 속한 모든 요소 삭제
    boolean removeAll(Collection<?> c);

    // 컬렉션에 포함되지 않은 요소만 남기고 삭제
    boolean retainAll(Collection<?> c);

    // 해당 인덱스의 요소를 주어진 요소로 대체
    E set(int index, E element);

    // 현재 리스트의 크기 반환
    int size();

    // 시작과 끝을 포함한 서브리스트 반환
    List<E> subList(int fromIndex, int toIndex);

    // 배열로 변환
    Object[] toArray();

    // 특정 타입의 배열로 변환
    <T> T[] toArray(T[] a);
}

 

List 구현 클래스

1. ArrayList
   • 내부적으로 동적 배열을 사용한 List의 구현체이다.  
     • 동적배열의 원리: 초기에 일정한 크기로 배열을 할당한 후, 크기가 꽉 찼다면 보다 큰 크기의 새로운 배열을 할당하고 기존 데이터를 새로운 배열로 복사한다.
   • 배열의 크기를 동적으로 조절하여 데이터를 저장하며, 데이터의 추가 및 삭제가 빠르다.
   • 인덱스 기반의 빠른 접근이 가능하며, 데이터의 순서가 중요한 경우에 적합하다.
   • 메모리 공간을 연속적으로 할당하므로 데이터 접근이 빠르지만, 중간에 요소를 삽입 또는 삭제하는 경우에는 오버헤드가 발생할 수 있다.
2. LinkedList
   • 내부적으로 노드들이 서로 링크로 연결된 구조를 사용한 List의 구현체이다.
   • 각 요소가 이전 요소와 다음 요소의 링크를 가지고 있어, 데이터의 삽입 및 삭제가 빠르다.
   • 순차적인 접근보다는 중간에 요소를 추가하거나 삭제하는 경우에 유용하다.
   • 인덱스 기반의 빠른 접근이 어려울 수 있다.
3. Vector
   • Java의 초기버전에 제공된 동기화된 List 구현체이다. 현재는 잘 사용되지 않는다.
   • ArrayList와 유사하게 동적 배열을 기반으로 동작하지만, 모든 메소드가 동기화 되어 있어 멀티 스레드 환경에서 안전하게 사용할 수 있다.

List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
List<String> vector = new Vector<>();

Queue

Queue: 큐(대기열) 자료 구조를 표현한 인터페이스이다. 큐는 먼저 들어간 데이터가 먼저 나오는(FIFO, First-In-First-Out) 원칙에 따라 동작한다.

큐의 한 쪽 끝은 Front로 정하여 삭제 연산만 수행하고, 다른 한 쪽 끝은 Rear로 정하여 삽입 연산만 수행한다. 이때, 큐의 리어에서 이루어지는 삽입 연산을 inQueue, 프론트에서 이루어지는 삭제 연산을 deQueue라 부른다.

ex) 은행 업무, 버스 대기 줄, 프로세스 관리, BFS, 캐시 구현

 

public interface Queue<E> extends Collection<E> {

    // 요소를 큐에 추가하고, 성공적으로 추가되면 true를 반환
    // 큐의 공간이 부족하면 예외를 발생시킴
    boolean add(E e);

    // 요소를 큐에 추가하고, 성공적으로 추가되면 true를 반환
    // 큐의 공간이 부족하면 false를 반환
    boolean offer(E e);

    // 큐의 맨 앞에 있는 요소를 제거하고 반환
    // 큐가 비어있으면 예외를 발생시킴
    E remove();

    // 큐의 맨 앞에 있는 요소를 제거하고 반환
    // 큐가 비어있으면 null을 반환
    E poll();

    // 큐의 맨 앞에 있는 요소를 반환 (제거하지 않음)
    // 큐가 비어있으면 예외를 발생시킴
    E element();

    // 큐의 맨 앞에 있는 요소를 반환 (제거하지 않음)
    // 큐가 비어있으면 null을 반환
    E peek();
 }

Deque: Queue를 상속받은 인터페이스로서, 양쪽 끝에서 요소의 삽입과 삭제 연산을 지원하는 더블 엔드 큐(double-ended queue)를 나타낸다. 따라서 front, rear에서 모두 요소를 추가하거나 제거할 수 있다.

 

Queue 구현 클래스

1. LinkedList
   • Queue와 Deque 인터페이스를 모두 구현한다.
   • 양방향 연결 리스트로 구현되어 있어 큐의 앞과 뒤에서 모두 효율적으로 요소를 추가하거나 제거할 수 있다.
2. ArrayDeque
   • 동적으로 크기가 조절되는 배열을 기반으로한 데크이다.
   • 큐의 앞과 뒤쪽에서 빠르게 요소를 추가하거나 삭제할 수 있다.
3. PriorityQueue
   • 우선 순위 큐를 구현한 클래스이다.
   • 요소는 우선순위에 따라 정렬되며, 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 제거된다.
4. BlockingQueue(Interface)
   • 멀티 스레드 환경에서 사용할 수 있는 동기화된 큐 인터페이스
   • 구현체로 LinkedBlockingQueue, ArrayBlockingQueue, PriorityBlockingQueue 등이 있다.
5. ConcurrentLinkedQueue
   • (non-blocking) 알고리즘이 사용된 동적 연결 리스트를 기반으로 하는 구현체이다.
   • 멀티스레드 환경에서 안전하게 사용할 수 있도록 설계되었다.

Queue<String> linkedListQueue = new LinkedList<>();
Queue<String> arrayDequeQueue = new ArrayDeque<>();
Queue<Integer> priorityQueue = new PriorityQueue<>();
BlockingQueue<String> linkedBlockingQueue = new LinkedBlockingQueue<>();
Queue<String> concurrentLinkedQueue = new ConcurrentLinkedQueue<>();

 

Set

Set: 중복된 요소를 허용하지 않는 집합을 나타낸다.

• 순서가 정의되지 않는다.
  • 요소들의 순서를 유지하지 않는다. 따라서 요소의 삽입 순서를 보장하지 않는다. 특정 구현체인 TreeSet과 LinkedHashSet는 내부적으로 정렬이나 삽입 순서를 기억하지만, Set 인터페이스 자체는 순서를 정의하지 않는다.
• 고유한 해시코드를 가지고 있다.
  • 각 요소가 고유한 해시코드를 가지고 있어야 한다. 이는 HashSet과 같은 해시 기반의 Set 구현체에서 중요하다. 중복을 판단하고 빠른 검색을 위해 내부적으로 해시 테이블을 사용한다.
• 빠른 검색 속도
  • 주로 검색 속도가 중요한 경우에 사용된다.
• 인덱스로 관리되지 않는다.
  • 인덱스로 관리되지 않아 인덱스를 파라미터로 갖는 메소드가 존재하지 않는다.

public interface Set<E> extends Collection<E> {

    // 요소를 세트에 추가
    // 이미 세트에 존재하는 경우 추가되지 않으며 false를 반환
    boolean add(E e);

    // 지정된 요소를 세트에서 제거
    boolean remove(Object o);

    // 세트에서 지정된 요소를 제거하고, 성공적으로 제거되면 true를 반환
    boolean contains(Object o);

    // 세트가 비어있는지 여부를 반환
    boolean isEmpty();

    // 세트에 있는 요소의 개수를 반환
    int size();

    // 세트의 모든 요소를 제거
    void clear();

    // 지정된 컬렉션의 모든 요소를 세트에 추가
    // 성공적으로 하나 이상의 요소를 추가하면 true를 반환
    boolean addAll(Collection<? extends E> c);

    // 세트에서 지정된 컬렉션에 포함된 요소를 제거
    // 성공적으로 하나 이상의 요소를 제거하면 true를 반환
    boolean removeAll(Collection<?> c);

    // 세트에 지정된 컬렉션에 포함된 요소만 남기고 다른 요소들은 제거
    // 성공적으로 하나 이상의 요소를 제거하면 true를 반환
    boolean retainAll(Collection<?> c);

    // 세트에서 지정된 요소들과 일치하는 모든 요소를 제거
    // 성공적으로 하나 이상의 요소를 제거하면 true를 반환
    boolean removeIf(java.util.function.Predicate<? super E> filter);

    // 세트에 있는 요소를 나타내는 스트림을 반환
    // 순서는 정의되어 있지 않다.
    Stream<E> stream();

    // 세트에 있는 요소를 나타내는 병렬 스트림을 반환
    // 순서는 정의되어 있지 않다.
    Stream<E> parallelStream();
}

Set의 구현체

1. HashSet
   • 가장 일반적으로 사용되는 구현체이다.
   • 내부적으로 HashMap을 사용하여 요소를 저장하며, 중복된 요소를 허용하지 않는다.
   • 순서를 보장하지 않는다.
2. TreeSet
   • 이진 검색 트리를 사용하여 요소를 저장하는 Set 구현체이다
   • 요소는 정렬된 순서로 저장되며, Comparable 또는 Comparator를 사용하여 정렬 기준을 지정할 수 있다.
3. LinkedHashSet
   • 해시 테이블과 연결 리스트를 사용하여 요소를 저장하는 Set구현체이다.
   • 삽입 순서를 보장하므로 요소의 순서가 삽입된 순서와 일치한다.

 

Map

Map:
Collection 인터페이스와는 다르게 "키-값" 쌍을 저장하는 자료구조로, 각 키는 고유해야 하며, 각 키에 대응하는 값이 있다. Java에서는 java.util.Map인터페이스를 기반으로 다양한 구현체를 제공한다.

 

• 키-값 쌍의 저장
  • Map은 키와 값의 쌍을 저장한다. 각 키는 유일해야 하며, 키에 대응하는 값은 중복될 수 있다.
• 키에 대한 순서가 정의되지 않음
  • 키-값 쌍의 순서를 정의하지 않는다. 즉, 키나 값이 삽입된 순서를 기억하지 않는다.
• 키와 값의 제네릭 지원
  • 제릭 인터페이스로, 특정 타입의 키와 값에 대한 유연성을 제공한다.

public interface Map<K, V> {

    // 맵에 주어진 키와 값의 쌍을 추가하고, 기존 값이 이미 있을 경우 이전 값을 반환
    V put(K key, V value);

    // 맵에서 주어진 키에 해당하는 값을 반환
    // 키가 존재하지 않을 경우 null을 반환
    V get(Object key);

    // 맵에서 주어진 키에 해당하는 값을 제거하고 해당 값을 반환
    // 키가 존재하지 않을 경우 null을 반환
    V remove(Object key);

    // 맵에 주어진 키가 존재하는지 여부를 반환
    boolean containsKey(Object key);

    // 맵에 주어진 값이 하나 이상 존재하는지 여부를 반환
    boolean containsValue(Object value);

    // 맵이 비어있는지 여부를 반환
    boolean isEmpty();

    // 맵에 저장된 키-값 쌍의 개수를 반환
    int size();

    // 맵의 모든 키를 포함하는 Set을 반환
    Set<K> keySet();

    // 맵의 모든 값들을 포함하는 Collection을 반환
    Collection<V> values();

    // 맵의 모든 키-값 쌍을 포함하는 Set을 반환
    Set<Map.Entry<K, V>> entrySet();

    // 맵의 모든 키-값 쌍을 다른 맵에 추가
    void putAll(Map<? extends K, ? extends V> m);

    // 맵의 모든 키-값 쌍을 제거하여 맵을 비운다.
    void clear();

    // 키-값 쌍을 나타내는 인터페이스
    interface Entry<K, V> {
        // 키를 반환
        K getKey();

        // 값을 반환
        V getValue();

        // 값의 새로운 값을 설정
        V setValue(V value);
    }
}

 

 

Map의 구현체

1. HashMap
   • 해시 테이블을 사용하여 키-값의 쌍을 저장하며, 빠른 검색 속도를 제공한다.
   • 순서를 보장하지 않는다.
2. TreeMap
   • 이진 검색 트리를 사용하여 키-값 쌍을 저장하는 구현체이다.
   • 키에 대한 정렬이 이루어지므로, 키의 순서에 따라 순회할 수 있다.
   • 키는 Comparable 인터페이스를 구현하거나 Comparator를 지정하여 정렬된다.
3. LinkedHashMap
   • 해시 테이블과 연결 리스트를 사용하여 키-값 쌍을 저장하는 Map 구현체이다
   • 삽입 순서를 보장하므로 키-값 쌍이 삽입된 순서대로 순회할 수 있다.
4. HashTable
   • HashMap과 유사하지만, 동기화된 메서드로 구성되어 있어 스레드 안전성을 제공한다.
   • Java 1.0부터 제공되었으며, 일반적으로는 ConcurrentHashMap과 같은 더 효율적인 대안이 존재한다.
5. ConcurrentHashMap
   • 동시성을 고려하여 설계된 Map 구현체이다.
   • 여러 스레드에서 동시에 안전하게 접근할 수 있도록 최적화되어 있다.