컬렉션 프레임워크 보충자료

1. 자료구조란?

• 정의: 데이터를 구조화하여 효율적으로 저장하고 처리하는 방법.

• 기본 자료구조:

  • 배열: 고정된 크기의 연속적인 메모리 공간.

  • 리스트: 동적으로 크기를 변경할 수 있는 자료구조.

---

2. 빅오 표기법 (Big-O Notation)

(1) 빅오 표기법이란?

• 정의: 알고리즘의 성능을 대략적으로 나타내는 표기법으로, 데이터의 양이 증가할 때 처리 시간(또는 메모리 사용량)이 어떻게 변화하는지를 나타냅니다.

• 목적:

  • 알고리즘의 효율성을 비교.

  • 데이터 크기가 커질 때 성능을 예측.

---

(2) 주요 빅오 표기법

표기법	설명	예제
O(1)	상수 시간: 데이터 크기와 관계없이 일정 시간	인덱스 접근 (arr[0])
O(n)	선형 시간: 데이터 크기에 비례	배열 검색, 요소 순회
O(n^2)	이차 시간: 이중 루프	중첩 for문
O(log n)	로그 시간: 이진 탐색처럼 데이터 크기를 반씩 줄임	이진 탐색 (binary search)
O(n log n)	선형 로그 시간: 효율적인 정렬 알고리즘	병합 정렬 (merge sort)

---

3. 배열과 리스트

(1) 배열

• 정의: 고정된 크기의 연속적인 메모리 공간에 데이터를 저장.

• 특징:

  • 장점: 인덱스를 사용하여 빠르게 접근 가능. (O(1))

  • 단점: 크기가 고정되어 데이터를 동적으로 추가/삭제할 수 없음.

배열 예제

public class ArrayExample {
    public static void main(String[] args) {
        int[] arr = new int[5]; // 크기 고정
        arr[0] = 10;
        arr[1] = 20;

        // 배열 출력
        for (int i = 0; i < arr.length; i++) {
            System.out.println("Element at index " + i + ": " + arr[i]);
        }
    }
}

실행 결과

Element at index 0: 10
Element at index 1: 20
Element at index 2: 0
Element at index 3: 0
Element at index 4: 0

---

(2) 리스트

• 정의: 동적으로 크기를 변경할 수 있는 데이터 구조.

• 특징:

  • 장점: 크기가 고정되지 않아 데이터를 동적으로 추가/삭제 가능.

  • 단점: 요소에 접근할 때 배열보다 느림 (O(n)).

리스트 예제

import java.util.ArrayList;

public class ListExample {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(); // 동적 리스트
        list.add(10); // 데이터 추가
        list.add(20);
        list.add(30);

        // 리스트 출력
        for (int i = 0; i < list.size(); i++) {
            System.out.println("Element at index " + i + ": " + list.get(i));
        }

        // 요소 삭제
        list.remove(1); // 인덱스 1의 요소 삭제

        System.out.println("After removal: " + list);
    }
}

실행 결과

Element at index 0: 10
Element at index 1: 20
Element at index 2: 30
After removal: [10, 30]

---

4. 빅오 표기법 예제

(1) O(1) - 배열의 인덱스 접근

public class BigOConstant {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        System.out.println("Element at index 2: " + arr[2]); // O(1)
    }
}

실행 결과

Element at index 2: 30

---

(2) O(n) - 배열의 전체 순회

public class BigOLinear {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};

        for (int num : arr) { // O(n)
            System.out.println("Number: " + num);
        }
    }
}

실행 결과

Number: 10
Number: 20
Number: 30
Number: 40
Number: 50

---

(3) O(log n) - 이진 탐색

import java.util.Arrays;

public class BigOLogarithmic {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int target = 30;

        int index = Arrays.binarySearch(arr, target); // O(log n)
        System.out.println("Index of " + target + ": " + index);
    }
}

실행 결과

yaml코드 복사Index of 30: 2

---

(4) O(n^2) - 이중 루프

public class BigOQuadratic {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};

        for (int i = 0; i < arr.length; i++) { // 외부 루프
            for (int j = 0; j < arr.length; j++) { // 내부 루프
                System.out.println("(" + arr[i] + ", " + arr[j] + ")");
            }
        }
    }
}

실행 결과

(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)

---

5. 배열과 리스트 비교

특징	배열	리스트 (ArrayList)
크기	고정	동적
데이터 접근	인덱스를 사용해 빠름 (O(1))	인덱스를 사용하지만 배열보다 느림 (O(n))
추가/삭제	불가능	가능 (O(1) 또는 O(n))
메모리 관리	정적 메모리 할당	동적 메모리 할당

6. ArrayList

(1) ArrayList란?

• 정의: 순서가 있고 중복을 허용하는 자료구조.

• 특징:

  • 내부적으로 배열을 사용하여 데이터 관리.

  • 데이터를 동적으로 추가/삭제 가능.

  • 인덱스로 접근이 가능하며, 검색 속도가 빠름 (O(1)).

  • 중간/앞쪽에 데이터를 삽입하거나 삭제할 경우 배열 요소를 이동해야 하므로 성능 저하 (O(n)).

---

(2) 배열 기반의 ArrayList 구현 예제

코드 예시

import java.util.Arrays;

class CustomArrayList {
    private int[] data;
    private int size;

    public CustomArrayList() {
        data = new int[10]; // 초기 크기
        size = 0;
    }

    // 데이터 추가
    public void add(int value) {
        if (size == data.length) {
            resize();
        }
        data[size++] = value;
    }

    // 특정 인덱스 데이터 삭제
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1]; // 요소 이동
        }
        size--;
    }

    // 요소 가져오기
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        return data[index];
    }

    // 크기 반환
    public int size() {
        return size;
    }

    // 배열 크기 늘리기
    private void resize() {
        data = Arrays.copyOf(data, data.length * 2); // 기존 배열의 2배 크기로 확장
    }
}

public class CustomArrayListExample {
    public static void main(String[] args) {
        CustomArrayList list = new CustomArrayList();
        list.add(10);
        list.add(20);
        list.add(30);

        System.out.println("Element at index 1: " + list.get(1)); // 20
        list.remove(1); // 인덱스 1 데이터 삭제
        System.out.println("Size after removal: " + list.size()); // 2
    }
}

실행 결과

Element at index 1: 20
Size after removal: 2

---

7. LinkedList

(1) LinkedList란?

• 정의: 노드(Node)를 기반으로 데이터를 저장하는 연결 리스트 자료구조.

• 특징:

  • 각 노드는 데이터를 저장하고 다음 노드에 대한 참조(포인터)를 가짐.

  • 배열과 달리 중간/앞쪽 삽입/삭제가 효율적 (O(1)).

  • 단점: 인덱스로 접근 불가하며, 순차적으로 검색해야 하므로 검색 속도는 느림 (O(n)).

---

(2) LinkedList 구현 예제

코드 예시

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class CustomLinkedList {
    private Node head;
    private int size;

    public CustomLinkedList() {
        head = null;
        size = 0;
    }

    // 데이터 추가
    public void add(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // 데이터 삭제
    public void remove(int value) {
        if (head == null) {
            return;
        }
        if (head.data == value) {
            head = head.next;
        } else {
            Node current = head;
            while (current.next != null && current.next.data != value) {
                current = current.next;
            }
            if (current.next != null) {
                current.next = current.next.next;
            }
        }
        size--;
    }

    // 리스트 출력
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 크기 반환
    public int size() {
        return size;
    }
}

public class CustomLinkedListExample {
    public static void main(String[] args) {
        CustomLinkedList list = new CustomLinkedList();
        list.add(10);
        list.add(20);
        list.add(30);
        list.printList(); // 10 -> 20 -> 30 -> null

        list.remove(20); // 20 삭제
        list.printList(); // 10 -> 30 -> null
    }
}

실행 결과

10 -> 20 -> 30 -> null
10 -> 30 -> null

---

8. ArrayList와 LinkedList의 다형성 활용

(1) List 인터페이스

• 정의: ArrayList와 LinkedList는 모두 List 인터페이스를 구현.

• 장점:

  • List 인터페이스를 사용하면, 데이터 구조를 변경할 때 코드 수정 최소화 가능.

코드 예시

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PolymorphismExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(); // ArrayList 사용
        list.add(10);
        list.add(20);
        list.add(30);
        System.out.println("Using ArrayList: " + list);

        list = new LinkedList<>(); // LinkedList로 변경
        list.add(40);
        list.add(50);
        list.add(60);
        System.out.println("Using LinkedList: " + list);
    }
}

실행 결과

Using ArrayList: [10, 20, 30]
Using LinkedList: [40, 50, 60]

---

9. List 인터페이스 주요 메서드

메서드	설명
boolean add(E e)	요소를 리스트의 끝에 추가
void add(int index, E e)	지정된 위치에 요소 추가
E get(int index)	지정된 인덱스의 요소 반환
E remove(int index)	지정된 위치의 요소 삭제
boolean remove(Object o)	지정된 객체 삭제
int size()	리스트의 크기 반환
boolean contains(Object o)	리스트에 특정 요소가 포함되어 있는지 확인
int indexOf(Object o)	리스트에서 특정 요소의 첫 번째 인덱스 반환
void clear()	리스트의 모든 요소 제거
boolean isEmpty()	리스트가 비어 있는지 확인

---

10. 자바 List의 특징

(1) ArrayList의 특징

1. 기본 Capacity

   • ArrayList는 내부적으로 배열을 사용하며, 초기 **Capacity(용량)**은 기본적으로 10입니다.

   • 만약 데이터가 용량을 초과하면, 기존 크기의 50%만큼 증가하여 새로운 배열을 생성하고 데이터를 복사합니다.

코드 예시: Capacity 확인

import java.util.ArrayList;

public class ArrayListCapacityExample {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(10); // 초기 용량 설정
        for (int i = 1; i <= 15; i++) {
            list.add(i); // 15개의 데이터를 추가
        }
        System.out.println("ArrayList size: " + list.size());
    }
}

실행 결과

ArrayList size: 15

1. 중간 데이터 추가 성능

   • 배열 기반 구조이므로 중간에 데이터를 추가할 때 기존 데이터를 이동해야 합니다.

   • 하지만 고속 메모리 복사 연산을 사용하여 데이터 복사가 빠르게 이루어집니다.

코드 예시: 중간 데이터 추가

import java.util.ArrayList;

public class ArrayListInsertExample {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(4);
        
        // 중간에 데이터 추가
        list.add(2, 3); // 인덱스 2에 숫자 3 삽입
        System.out.println("ArrayList after insertion: " + list);
    }
}

실행 결과

ArrayList after insertion: [1, 2, 3, 4]

---

(2) LinkedList의 특징

1. 이중 연결 구조

   • LinkedList는 이중 연결 리스트로 구현되어 있어, 각 노드는 이전 노드와 다음 노드를 참조합니다.

   • 이를 통해 역방향 이동 및 양방향 순회가 가능합니다.

2. 역방향 조회

   • 인덱스를 기반으로 조회할 경우, 중간점을 기준으로 최적화:

     • 인덱스가 리스트 크기의 절반 이하: 처음부터 조회.

     • 인덱스가 리스트 크기의 절반 초과: 마지막 노드에서 역방향으로 조회.

3. 마지막 노드 참조

   • 마지막 노드에 대한 참조가 있으므로, 마지막에 데이터 추가 시 O(1) 성능을 제공합니다.

코드 예시: LinkedList 역방향 조회

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        // 역방향 조회
        System.out.println("Last element: " + list.getLast());
        System.out.println("Second last element: " + list.get(list.size() - 2));
    }
}

실행 결과

Last element: 5
Second last element: 4

---

(3) ArrayList와 LinkedList 비교

특징	ArrayList	LinkedList
내부 구조	배열 기반	이중 연결 리스트
중간 데이터 추가/삭제	O(n) (데이터 이동 발생)	O(1) (노드 참조 변경)
인덱스 기반 조회	O(1) (빠름)	O(n) (인덱스 기준 최적화된 방향으로 조회)
메모리 효율성	크기 초과 시 새 배열 생성 후 데이터 복사 필요	노드 간 참조 추가로 메모리 사용량 많음
마지막 데이터 추가	O(1) (항상 배열 끝에 추가)	O(1) (마지막 노드 참조 사용)

---

11. List와 Set

(1) List와 Set의 차이

특징	List	Set
순서	요소의 순서를 유지	순서를 보장하지 않음
중복 허용	중복 요소 허용	중복 요소 허용하지 않음
접근 방식	인덱스를 통한 접근 가능	인덱스가 없으며 요소 검색 중심
사용 예시	장바구니 목록, 작업 리스트	회원 ID 집합, 고유 항목 집합
대표 구현체	ArrayList, LinkedList	HashSet, TreeSet

---

(2) Set의 문제점: O(n) 복잡도

• 데이터를 하나씩 추가할 때마다 **O(n)**이 걸림.

• 중복을 확인하기 위해 모든 요소를 비교해야 하기 때문.

코드 예시: 단순 Set 구현

import java.util.ArrayList;

class SimpleSet {
    private ArrayList<Integer> data;

    public SimpleSet() {
        data = new ArrayList<>();
    }

    public void add(int value) {
        if (!data.contains(value)) { // 중복 체크
            data.add(value);
        }
    }

    public boolean contains(int value) {
        return data.contains(value);
    }

    public void printSet() {
        System.out.println(data);
    }
}

public class SimpleSetExample {
    public static void main(String[] args) {
        SimpleSet set = new SimpleSet();
        set.add(10);
        set.add(20);
        set.add(10); // 중복 추가 시도
        set.printSet(); // [10, 20]
    }
}

실행 결과

[10, 20]

---

12. 해시 알고리즘과 HashSet

(1) 해시 알고리즘

• 해시 알고리즘은 데이터의 고유한 해시코드를 생성하여 데이터를 저장하는 방식.

• 핵심 아이디어:

  1. 배열의 크기만큼 나머지 연산(%)을 사용해 해시코드를 인덱스로 변환.

  2. 값이 충돌할 경우, 해시 버킷(배열 안의 배열)을 사용하여 동일한 인덱스에 여러 값을 저장.

  3. 각 버킷 내부에서는 전체 데이터를 비교해야 하므로 최악의 경우 O(n) 복잡도가 발생.

---

(2) 해시 알고리즘 예제

코드 예시: 해시를 사용하는 간단한 Set 구현

import java.util.LinkedList;

class HashSetExample {
    private LinkedList<Integer>[] table;
    private int size;

    public HashSetExample(int capacity) {
        table = new LinkedList[capacity];
        size = 0;
    }

    private int hash(int value) {
        return Math.abs(value) % table.length; // 해시코드 계산
    }

    public void add(int value) {
        int index = hash(value);

        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }

        if (!table[index].contains(value)) { // 중복 방지
            table[index].add(value);
            size++;
        }
    }

    public boolean contains(int value) {
        int index = hash(value);
        return table[index] != null && table[index].contains(value);
    }

    public void printSet() {
        for (LinkedList<Integer> bucket : table) {
            if (bucket != null) {
                System.out.print(bucket + " ");
            }
        }
        System.out.println();
    }
}

public class HashSetImplementationExample {
    public static void main(String[] args) {
        HashSetExample set = new HashSetExample(5);
        set.add(10);
        set.add(15);
        set.add(20);
        set.add(15); // 중복 추가 시도
        set.printSet(); // 출력 예: [10] [15, 20]
    }
}

실행 결과

[10] [15, 20]

---

(3) HashSet의 특징

• HashSet은 데이터를 저장하기 위해 해시 알고리즘을 사용.

• 모든 객체는 **hashCode**를 제공해야 하며, 이는 기본적으로 Object.hashCode()를 통해 구현됩니다.

---

13. hashCode와 equals 재정의

(1) hashCode와 equals의 필요성

• hashCode:

  • 객체를 해시코드로 변환하여 버킷의 위치를 결정.

  • 기본적으로 Object.hashCode()는 객체의 참조값을 기반으로 계산.

  • 재정의 필요: 동일한 데이터를 가진 객체가 동일한 해시코드를 가지도록 하기 위해.

• equals:

  • 해시코드가 같더라도 실제 데이터가 동일한지 확인.

  • 재정의 필요: 데이터 비교를 위해.

---

(2) hashCode와 equals 재정의 예제

코드 예시

import java.util.HashSet;

class User {
    private int id;
    private String name;

    public User(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int hashCode() {
        return id * 31 + name.hashCode(); // 고유 해시코드 생성
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        User user = (User) obj;
        return id == user.id && name.equals(user.name);
    }

    @Override
    public String toString() {
        return "User{id=" + id + ", name='" + name + "'}";
    }
}

public class HashCodeEqualsExample {
    public static void main(String[] args) {
        HashSet<User> userSet = new HashSet<>();
        userSet.add(new User(1, "Alice"));
        userSet.add(new User(2, "Bob"));
        userSet.add(new User(1, "Alice")); // 중복 객체

        System.out.println(userSet); // 중복 제거된 결과 출력
    }
}

실행 결과

[User{id=1, name='Alice'}, User{id=2, name='Bob'}]

---

14. List와 Set의 차이점 요약

특징	List	Set
중복 허용	허용	허용하지 않음
순서 유지	유지	유지하지 않음
대표 구현체	ArrayList, LinkedList	HashSet, TreeSet
접근 속도	빠름 (O(1) - 인덱스)	검색 중심, HashSet은 평균적으로 O(1)
사용 예시	장바구니, 작업 리스트	회원 ID 집합, 고유 항목 집합

15. HashSet, LinkedHashSet, TreeSet

(1) HashSet

HashSet 특징

• 정의: Set 인터페이스를 구현하며, 요소의 유일성을 보장.

• 특징:

  • 순서 없음.

  • 평균적으로 빠른 성능 (O(1)).

  • 중복되지 않는 데이터를 저장하는 데 적합.

• 사용 예시:

  • 회원 ID 집합, 고유 식별자 저장 등.

코드 예시

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple"); // 중복 추가 시도

        System.out.println(set); // 중복 없이 저장
    }
}

실행 결과

[Banana, Cherry, Apple]

---

(2) LinkedHashSet

LinkedHashSet 특징

• 정의: HashSet을 기반으로 요소의 순서를 유지하는 구현체.

• 특징:

  • 데이터 유일성 보장 + 입력 순서 유지.

  • **O(1)**의 성능을 유지하면서 순서를 보장.

  • 내부적으로 해시 테이블과 이중 연결 리스트를 사용.

  • LinkedHashSet은 HashSet보다 약간 무겁고 메모리 사용량이 높음.

코드 예시

import java.util.LinkedHashSet;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple"); // 중복 추가 시도

        System.out.println(set); // 입력 순서 유지
    }
}

실행 결과

[Apple, Banana, Cherry]

---

(3) TreeSet

TreeSet 특징

• 정의: Set 인터페이스를 구현하며, 이진 탐색 트리를 기반으로 정렬된 데이터를 저장.

• 특징:

  • 오름차순 정렬로 저장.

  • 내부적으로 균형 이진 탐색 트리(Red-Black Tree)를 사용.

  • 조회/추가/삭제 모두 O(log n) 성능을 보장.

  • 중복되지 않는 데이터를 정렬된 상태로 저장하는 데 적합.

코드 예시

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(50);
        set.add(10);
        set.add(30);
        set.add(20);
        set.add(10); // 중복 추가 시도

        System.out.println(set); // 오름차순 정렬된 결과
    }
}

실행 결과

[10, 20, 30, 50]

---

16. Map

(1) Map 특징

• 정의: 키-값 쌍으로 데이터를 저장하는 자료 구조.

• 특징:

  1. 키:

     • 유일해야 함 (Set으로 반환 가능).

     • 중복 허용되지 않음.

  2. 값:

     • 중복 가능 (Collection으로 반환 가능).

  3. 타입 지정:

     • 키와 값의 타입을 각각 명시해야 함.

---

(2) Map 예제

HashMap

• HashMap은 순서를 유지하지 않으며, 평균적으로 O(1) 성능을 보장.

코드 예시

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);
        map.put("Alice", 28); // 중복 키, 값 덮어쓰기

        // 키와 값 출력
        System.out.println("Keys: " + map.keySet()); // 키: Set 타입
        System.out.println("Values: " + map.values()); // 값: Collection 타입

        // 특정 키의 값 가져오기
        System.out.println("Alice's age: " + map.get("Alice"));
    }
}

실행 결과

Keys: [Alice, Bob, Charlie]
Values: [28, 30, 35]
Alice's age: 28

---

LinkedHashMap

• 입력 순서 유지를 제공하며, HashMap과 비슷한 성능을 가짐.

코드 예시

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        // 입력 순서 유지
        System.out.println(map);
    }
}

실행 결과

{Alice=25, Bob=30, Charlie=35}

---

TreeMap

• 키를 기준으로 정렬된 데이터를 저장.

• 성능: O(log n).

코드 예시

import java.util.TreeMap;
import java.util.Map;

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("Charlie", 35);
        map.put("Alice", 25);
        map.put("Bob", 30);

        // 키를 기준으로 정렬
        System.out.println(map);
    }
}

실행 결과

{Alice=25, Bob=30, Charlie=35}

---

17. List, Set, Map 요약

특징	List	Set	Map
데이터 저장 방식	순서대로 저장	중복 없는 데이터 저장	키-값 쌍으로 데이터 저장
중복 허용	허용	허용하지 않음	키: 허용하지 않음, 값: 허용
순서 보장	보장	보장하지 않음 (HashSet), 보장 (LinkedHashSet)	키의 정렬 여부에 따라 다름 (TreeMap)
사용 예시	작업 리스트	회원 ID 집합	사용자 정보 저장 (키-값 쌍)

18. HashMap, LinkedHashMap, TreeMap

(1) HashMap

HashMap 특징

• 정의: Set과 유사하지만, 데이터를 **키-값(Map 형식)**으로 저장.

• 특징:

  • 순서 보장 없음.

  • 키 기준으로 해시코드를 작성하여 해시 인덱스를 생성.

  • 중복 키를 허용하지 않으며, 동일한 키가 삽입되면 기존 값이 덮어써짐.

• 사용 시 주의:

  • 키의 유일성을 보장하기 위해, **hashCode와 equals**를 올바르게 구현해야 함.

코드 예시

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Alice", 28); // 기존 키에 값 덮어쓰기

        System.out.println(map); // 순서 보장 없음
    }
}

실행 결과

{Bob=30, Alice=28}

---

(2) LinkedHashMap

LinkedHashMap 특징

• 정의: HashMap과 동일한 방식으로 작동하나, 입력 순서를 유지.

• 특징:

  • 데이터가 삽입된 순서대로 순회 가능.

  • 내부적으로 해시 테이블과 이중 연결 리스트를 사용.

코드 예시

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        System.out.println(map); // 입력 순서 유지
    }
}

실행 결과

{Alice=25, Bob=30, Charlie=35}

---

(3) TreeMap

TreeMap 특징

• 정의: TreeSet과 유사하게 정렬된 상태로 데이터를 저장.

• 특징:

  • 키를 기준으로 정렬.

  • 내부적으로 Red-Black Tree를 사용하여 조회/삽입/삭제 모두 O(log n) 성능.

  • 키가 비교 가능해야 하므로 Comparable 또는 **Comparator**를 구현해야 함.

코드 예시

import java.util.TreeMap;
import java.util.Map;

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("Charlie", 35);
        map.put("Alice", 25);
        map.put("Bob", 30);

        System.out.println(map); // 키를 기준으로 정렬
    }
}

실행 결과

코드 복사{Alice=25, Bob=30, Charlie=35}

---

Map 구현체 사용 요약

특징	HashMap	LinkedHashMap	TreeMap
순서	순서 없음	입력 순서 유지	키를 기준으로 정렬
성능	평균 O(1)	평균 O(1)	O(log n)
내부 구조	해시 테이블	해시 테이블 + 이중 연결 리스트	Red-Black Tree
사용 예시	일반적인 키-값 데이터 저장	순서가 중요한 데이터 저장	정렬이 필요한 데이터 저장

---

19. Stack, Queue, Deque

(1) Stack

Stack 특징

• 정의: LIFO(Last In First Out) 자료구조. 가장 나중에 삽입된 데이터가 가장 먼저 처리됨.

• 특징:

  • 데이터 삽입(push) 및 삭제(pop)이 한쪽 끝에서만 이루어짐.

• 사용 예시:

  • 함수 호출 스택, Undo/Redo 기능 구현.

코드 예시

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10); // 데이터 추가
        stack.push(20);
        stack.push(30);

        System.out.println("Stack: " + stack);

        System.out.println("Popped: " + stack.pop()); // 데이터 제거
        System.out.println("Peek: " + stack.peek()); // 가장 상단 데이터 조회
    }
}

실행 결과

Stack: [10, 20, 30]
Popped: 30
Peek: 20

---

(2) Queue

Queue 특징

• 정의: FIFO(First In First Out) 자료구조. 가장 먼저 삽입된 데이터가 가장 먼저 처리됨.

• 특징:

  • 데이터 삽입(add)은 뒤쪽에서, 삭제(poll)는 앞쪽에서 이루어짐.

• 사용 예시:

  • 작업 대기열, 프로세스 관리.

코드 예시

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(10); // 데이터 추가
        queue.add(20);
        queue.add(30);

        System.out.println("Queue: " + queue);

        System.out.println("Polled: " + queue.poll()); // 데이터 제거
        System.out.println("Peek: " + queue.peek()); // 가장 앞의 데이터 조회
    }
}

실행 결과

Queue: [10, 20, 30]
Polled: 10
Peek: 20

---

(3) Deque

Deque 특징

• 정의: 양방향 큐로, Queue와 Stack의 기능을 모두 제공.

• 특징:

  • 데이터 삽입과 삭제가 양쪽에서 모두 가능.

  • Deque는 LIFO와 FIFO를 모두 지원.

• 사용 예시:

  • 브라우저의 뒤로 가기/앞으로 가기, 양방향 작업 큐.

코드 예시

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addFirst(10); // 앞쪽에 추가
        deque.addLast(20);  // 뒤쪽에 추가
        deque.addFirst(5);  // 앞쪽에 추가

        System.out.println("Deque: " + deque);

        System.out.println("Removed from front: " + deque.pollFirst()); // 앞쪽 제거
        System.out.println("Removed from back: " + deque.pollLast());  // 뒤쪽 제거
    }
}

실행 결과

Deque: [5, 10, 20]
Removed from front: 5
Removed from back: 20

---

20. Stack, Queue, Deque 요약

특징	Stack	Queue	Deque
데이터 처리 방식	LIFO	FIFO	양방향 (LIFO + FIFO)
대표 구현체	Stack	LinkedList	ArrayDeque
사용 예시	함수 호출 스택	작업 대기열	브라우저 뒤로 가기/앞으로 가기

---

정리

1. HashMap:

   • 가장 많이 사용하는 Map 구현체.

   • 키를 기준으로 hashCode와 equals를 구현해야 함.

   • 순서 보장 없음.

2. LinkedHashMap:

   • HashMap과 유사하지만 입력 순서를 보장.

3. TreeMap:

   • 키를 기준으로 정렬.

   • 정렬된 데이터를 저장할 때 적합.

4. Stack:

   • LIFO 방식.

   • 함수 호출 스택, Undo/Redo 등.

5. Queue:

   • FIFO 방식.

   • 작업 대기열, 프로세스 관리.

6. Deque:

   • 양방향 큐로, Queue와 Stack의 기능 모두 지원.

21. Iterable과 Iterator

(1) Iterable이란?

• 정의: 반복 가능한 객체로, 모든 자료구조를 동일한 방식으로 순회할 수 있도록 제공하는 인터페이스.

• 특징:

  • 모든 컬렉션(List, Set, Queue 등)은 Iterable 인터페이스를 구현.

  • Iterable 인터페이스는 반복자를 반환하는 iterator() 메서드를 제공.

  • 반복자는 데이터를 하나씩 순회하기 위한 hasNext(), next() 메서드를 포함.

---

(2) Iterator란?

• 정의: 반복자로, 컬렉션에 저장된 요소를 하나씩 순회하며 접근하는 객체.

• 특징:

  • 단독 사용 불가: 항상 Iterable 객체의 iterator()를 통해 생성.

  • 메서드:

    • hasNext(): 다음 요소가 있는지 확인.

    • next(): 다음 요소를 반환.

    • remove(): 현재 요소를 삭제(선택적 기능).

  • 모든 컬렉션(List, Set, Queue)에서 사용 가능.

  • **Map**은 Iterable을 구현하지 않음.

---

(3) Iterable과 Iterator의 사용 예제

(1) 직접 Iterator를 사용한 순회

import java.util.ArrayList;
import java.util.Iterator;

public class IteratorExample {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // Iterator 사용
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

실행 결과

Apple
Banana
Cherry

---

(2) 향상된 for문을 사용한 순회

• 모든 Iterable 객체는 향상된 for문을 통해 순회 가능.

코드 예시

import java.util.ArrayList;

public class EnhancedForLoopExample {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 향상된 for문
        for (String item : list) {
            System.out.println(item);
        }
    }
}

실행 결과

Apple
Banana
Cherry

---

(3) Set과 Queue에서의 Iterator 사용

코드 예시

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Iterator;

public class SetAndQueueIteratorExample {
    public static void main(String[] args) {
        // HashSet
        HashSet<String> set = new HashSet<>();
        set.add("A");
        set.add("B");
        set.add("C");

        System.out.println("HashSet elements:");
        Iterator<String> setIterator = set.iterator();
        while (setIterator.hasNext()) {
            System.out.println(setIterator.next());
        }

        // Queue
        LinkedList<String> queue = new LinkedList<>();
        queue.add("X");
        queue.add("Y");
        queue.add("Z");

        System.out.println("\nQueue elements:");
        Iterator<String> queueIterator = queue.iterator();
        while (queueIterator.hasNext()) {
            System.out.println(queueIterator.next());
        }
    }
}

실행 결과

HashSet elements:
A
B
C

Queue elements:
X
Y
Z

---

(4) Iterable과 Collection 관계

구조

1. Iterable 인터페이스:

   • 가장 상위 인터페이스로 반복자를 반환하는 iterator() 메서드를 제공.

2. Collection 인터페이스:

   • List, Set, Queue는 모두 Collection을 구현.

   • 따라서 모든 컬렉션은 Iterable을 구현.

주요 구조 다이어그램

Iterable
   └── Collection
         ├── List
         ├── Set
         └── Queue

주요 특징

• 모든 Collection 인터페이스 구현체(List, Set, Queue)는 Iterable을 구현.

• 따라서 모든 컬렉션은 동일한 방식으로 순회 가능.

• **Map**은 Iterable을 직접 구현하지 않음.

---

(5) Map의 반복

Map은 Iterable을 구현하지 않음

• 하지만, keySet(), values(), entrySet() 메서드를 통해 부분적으로 순회 가능.

코드 예시

import java.util.HashMap;
import java.util.Map;

public class MapIterationExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        // 키를 기준으로 순회
        System.out.println("Keys:");
        for (String key : map.keySet()) {
            System.out.println(key);
        }

        // 값을 기준으로 순회
        System.out.println("\nValues:");
        for (Integer value : map.values()) {
            System.out.println(value);
        }

        // 키-값 쌍으로 순회
        System.out.println("\nEntries:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

실행 결과

Keys:
Alice
Bob
Charlie

Values:
25
30
35

Entries:
Alice = 25
Bob = 30
Charlie = 35

---

정리

Iterable과 Iterator

1. Iterable:

   • 반복 가능한 객체로 iterator() 메서드를 제공.

   • 모든 컬렉션(List, Set, Queue)이 이를 구현.

   • Iterable 구현체는 향상된 for문으로 순회 가능.

2. Iterator:

   • 반복자를 통해 데이터에 순차적으로 접근.

   • 주요 메서드:

     • hasNext(): 다음 요소가 있는지 확인.

     • next(): 다음 요소 반환.

Map

• Iterable을 구현하지 않지만, keySet(), values(), entrySet()을 통해 순회 가능.