자바 중급 2-2 (컬렉션 자료구조 구현)

🔖Java

자바 중급 2-2 (컬렉션 자료구조 구현)

Jerry_K 2025. 5. 2. 10:48

자바 중급 2-2 포스팅은 김영한님의 자바 중급 2편의 컬렉션을 다룬다.

앞서 제네릭편은 이전에 포스팅하였다.

컬렉션은 관련 자료구조들을 일부 직접 구현하기 때문에,

이렇게 따로 포스팅을 진행한다.

관련한 자세한 코드는 깃허브에 기록해두었다.

(깃허브 기록 할 때, 좀 더 상세하게 작성해야 했는데 그러지 못한게 아쉽다...)

https://github.com/jerry-1211/Collection

GitHub - jerry-1211/Collection: Java Collection

Java Collection. Contribute to jerry-1211/Collection development by creating an account on GitHub.

github.com

ArrayList

배열과 인덱스

배열에서는 자료를 찾을 때 인덱스를 사용하여 빠르게 자료를 찾을 수 있다.

위의 그림은 arr[2]에 위치한 자료를 찾고 있다.
배열은 메모리상에 붙여져 존재한다.
참고로 int형은 4 byte 차지한다.
따라서 arr[2]의 위치는 x100 (배열 시작 위치) + ( 4byte * 2) = x108이 된다.
- 하나 하나 탐색이 아니라, 계산으로 한번에 찾음
한번의 계산으로 매우 효율적으로 자료의 위치를 찾을 수 있다.

배열의 한계

배열은 가장 기본적인 자료구조로 인덱스를 사용할 때 최고의 효율이 나온다.
하지만 배열의 크기를 배열을 생성하는 시점에 미리 정해야 하는 한계
배열은 정적으로 길이가 정해져 있음

리스트

배열의 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조
리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변함

배열 리스트

ArrayList (배열 리스트)는 리스트 자료 구조를 사용하는데, 내부의 데이터는 배열에 보관하는 것이다.
데이터 추가 시간 복잡도
- 마지막 추가 : O(1)
- 앞, 중간 추가 : O(N)
데이터 삭제 시간 복잡도
- 마지막 삭제 : O(1)
- 앞, 중간 삭제 : O(N)
인덱스 조회 : O(1) → 한번의 계산으로 자료의 인덱스 위치 바로 찾음
데이터 검색 : O(N)

배열 리스트의 가장 큰 단점이 있다.

배열의 사용하지 않는 공간 낭비
배열의 중간에 데이터 추가

이러한 문제를 해결할 수 있는데, 그게 바로 링크드 리스트이다.

LinkedList

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼만 메모리 확보
내부에 저장할 데이터인 item과, 다음으로 연결할 노드의 참조 next를 가진다.
첫 번째 위치에 데이터 추가 및 삭제 O(1) 로 매우 빠르다.
중간 위치에서 데이터 추가 및 삭제는 위치 찾는데 O(n) + 노드 추가에 O(1)이 여서 O(n)이 걸린다.

배열 리스트와 연결 리스트의 성능 비교 표

배열 리스트 VS 연결 리스트 사용

데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열리스트
앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결리스트
이론적으로 MyLinkedList의 평균 연산이 MyArrayList보다 빠를 수 있지만 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비욜, CPU 캐시 활용도 등 다용한 요소에 영향받는다
MyArrayList는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고 메모리 접근 속도가 빠름
MyLinkedList는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하여 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느릴 수 있다.

대부분의 경우 현업에서는 배열 리스트를 기본으로 사용한다.
하지만 만약 데이터를 앞쪽에서 자주 추가하는 일이 생기면 연결 리스트를 고려한다.

컴파일 타임 의존관계

// BatchProcessor (Client 역할)
public class BatchProcessor {
    private final MyList<Integer> list ;

    public BatchProcessor(MyList<Integer> list) {
        this.list = list;
    }
    
    . . .   
}

BatchProcessor은 MyList에 의존한다.

public class MyArrayList<E> implements MyList<E> {
	. . .
}

public class MyLinkedList<E> implements MyList<E>{
	. . .
}

MyArrayList와 MyLinkedList는 MyList에 의존한다.
이 부분을 내가 여태 이해를 못했다... 저렇게 implements에 MyList가 있으므로 의존이다.

이렇게 컴파일 타임에 의존을 하면,

구체적인 구현에 의존하는 것이 아니라 추상적인 MyList에 의존하며
런타임에 MyList의 구현체를 얼마든지 선택 할 수 있다.

리스트의 의존관계를 클래스에서 미리 결정하는 것이 아니라,
런타임 객체를 생성하는 시점으로 미룬다.
여기에서 결정을 나중에 미루는 것은 코드의 재사용성을 높힌다.
(예를 들어 매서드에 매개변수, 제네릭의 타입 매개변수, 인스턴스 매개변수 등등)

실제 List

Collection 인터페이스 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나
Collection 인터페이스에는 List, Set, Queue와 같은 다양한 하위 인터페이스 함께 사용
List 인터페이스는 ArrayList, LinkedList와 같은 여러 구현 클래스를 가짐

자바가 제공하는 배열 리스트와 연결 리스트 성능 비교

이론적으로는 LinkedList의 중간 삽입 연산이 ArrayList보다 빠를 수 있지만,
실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 영향 받는다.
또한 실제 자바의 ArrayList는 데이터를 한 칸씩 직접 이동하지 않고, 메모리 고속 복사를 사용
요약하자면 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화,
메모리 고속 복사 등을 고려할 때 ArrayList가 실제 사용 환경에서 더 나은 성능을 보여준다.
그래서 대부분의 경우 ArrayList를 사용하는 것이 성능상 유리하다.
만약 앞쪽에 자주 추가하거나 삭제하는 경우에는 LinkedList 도입을 고려

주로 사용되는 메서드

add(E e)
add(int index, E element)
addAll(Collection<? extends E> c)

clear()

clone()

contains(Object o)

forEach(Consumer<? super E> action)
// numbers.forEach(number -> System.out.println(number));

get(int index)

indexOf(Object o)

isEmpty()

lastIndexOf(Object o)

remove(int index)

remove(Object o)

removeAll(Collection<?> c)

set(int index, E element) // 교체에 사용

size()

sort(Comparator<? super E> c)

subList(int fromIndex, int toIndex)

toArray()

asList()

Set

List 와 Set 비교

List

리스트는 요소들의 순차적인 컬렉션
특정 순서를 가지며 같은 요소가 여러번 나타날 수 있음
리스트에 추가된 요소는 특정한 순서를 유지한다.
리스트는 동일한 값이나 객체의 중복 허용
리스트의 각 요소는 인덱스를 통해 접근 가능

Set

세트는 유일한 요소들의 컬렉션
중복된 요소가 존재하지 않음
요소들의 순서를 보장하지 않음
요소의 유뮤를 빠르게 확인할 수 있도록 최적화되어 있음

어떻게 하면 검색을 O(1)의 속도로 끌어 올릴 수 있을까 ?

1. 데이터의 값과 배열의 인덱스를 맞추어 입력

이렇게 할 경우 탐색에 시간 복잡도는 O(1) 이다.
배열에 따라 낭비되는 공간이 발생

2. 나머지 연산

해시 인덱스를 사용해서 데이터 저장
배열의 크기를 제한하였기 때문에, 나머지 연산을 통해 메모리가 낭비되는 문제 해결
하지만 같은 인덱스일 경우 해시 충돌의 문제 발생

그렇다면 해시 충돌 문제를 어떻게 해결할 수 있을까 ?

해시 충돌을 막을 수는 없다..
해시 충돌은 낮은 확률로 일어날 수 있다고 가정하고, 해시 충돌을 인정하자.
해시 충돌이 발생했을 때, 인덱스의 값을 같은 인덱스에 배열 형태로 저장해버리면 된다.

이렇게 최악의 경우에도 O(N)의 성능을 보인다.
평균적으로 대부분 O(1)의 성능을 제공하고, 가끔 해시 충돌이 발생해도 내부 값 몇번 비교하는 수준이다.

참고) 자바는 제네릭 배열을 허용하지 않는다.

LinkedList<Integer>[] buckets = new LinkedList<>[CAPACITY]; //컴파일 에러

제네릭 배열을 직접 만들 경우, 개발자가 안전하다고 착각할 수 있음
따라서 컴파일 에러 발생

LinkedList<Integer>[] buckets = new LinkedList[CAPACITY]; // 가능

new LinkedList[CAPACITY]는 raw type 배열 생성이라 허용
타입 안정성은 개발자가 책임지기 때문에, 경고를 띄어준다.

위의 두가지 모두 아래와 같은 문제가 생길 수 있다.

Object[] objArr = buckets;  // 배열은 공변이므로 OK

objArr[0] = new LinkedList<String>();  // 💥 이게 문제!

buckets[0].add(123);  // 💥 ClassCastException 발생

제네릭 배열 같은 경우는, 개발자가 안전하다고 착각 할 수 있게 만드는게 제일 큰 문제

런타임에 실체화되는 배열의 타입을
제네릭으로 할 경우 타입 안정성을 보장하지 못한다.
따라서 제네릭 배열은 컴파일 에러가 발생하는 것을 기억하자!

해시 충돌

import java.util.Arrays;
import java.util.LinkedList;

public class MyHashSetV1 {
    static final int DEFAULT_INITIAL_CAPACITY = 10;
    LinkedList<Integer>[] buckets;

    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;

    public MyHashSetV1() {
        initBuckets();
    }

    public MyHashSetV1(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }

    private void initBuckets() {
        buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    public boolean add(int value){
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];
        if(bucket.contains(value)){
            return false;
        }
        bucket.add(value);
        size ++;
        return true;
    }

    public boolean remove(int value){
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];
        boolean result =  bucket.remove(Integer.valueOf(value));
        if(result){
            size--;
            return true;
        }else{
            return false;
        }
    }

    public boolean contains(int searchValue){
        int hashIndex = hashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }

    private int hashIndex(int value){
        return value % capacity;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV1{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}

해시 충돌을 해결한 코드이다.
먼저 LinkedList 타입으로 배열을 만들고, 각 배열의 LinkedList를 생성한다.
add 메서드에서는 hashIndex를 통해 bucket의 위치를 알아내고, contain 메서드에서는 value가 있는지를 확인한다.
해시 인덱스를 사용하는 경우
- 데이터 저장
  - 평균 : O(1)
  - 최악 : O(n)
- 데이터 조회
  - 평균 : O(1)
  - 최악 : O(n)

정수형은 이제 처리가 되었으니, 이제 문자열을 해결해보자 !

static int hashCode(String str){
    char[] charArray = str.toCharArray();
    int sum = 0;
    for(char c : charArray){
        sum += (int) c;
    }
    return  sum;
}

문자열도 결국에 해시코드로 변경하면 된다.
hashCode() 메서드를 사용해서 문자열을 해시 코드로 변경한다.
- 위의 hashCode는 아주 간단하게 구현된 hashCode이다.
그러면 고유한 정수 숫자값이 나오고, 이거를 해시 코드라고 한다.
정수인 해시 코드를 사용해서 해시 인덱스를 생성한다.

해시 함수 (Hash Function)

임의의 길이의 데이터를 입력으로 받아, 고정된 길이의 해시값(해시 코드) 출력
같은 데이터를 입력하면 항상 같은 해시 코드 출력

해시 코드 (Hash Code)

해시 코드는 데이터를 대표하는 값
보통 해시 함수를 통해 만들어짐

해시 인덱스 (Hash Index)

해시 인덱스는 데이터의 저장 위치를 결정
주로 해시 코드를 사용해서 만듬

이제 그렇다면 문자 뿐만 아니라 내가 직접 만든 객체는 어떻게 해시 코드로 정의할 수 있을까 ?

자바의 hashCode( )

자바는 모든 객체가 자신만의 해시 코드를 표현할 수 있는 기능 제공
- 바로 Object에 있는 hashCode( ) 메서드
Integer, String 같은 자바 기본 클래스들 대부분은 내부 값을 기반으로 hashCode 메서드 이미 재정의
기본 구현은 객체의 참조값을 기반으로 해시 코드 생성
- 인스턴스가 다르면 해시 코드도 다름
해시 코드의 경우 정수를 반환하기 때문에 마이너스 값도 가능

@Override
public int hashCode() {
    return Objects.hashCode(id);
}

이 메서드는 보통 재정의 (오버라이딩)해서 사용
hashCode를 재정의하지 않으면 Object가 기본으로 제공하는 hashCode 메서드 사용 (참조값 기반)
위의 코드는 id를 기반으로 재정의하여, id만 같으면 같은 해시코드 반환

MyHashSetV2 (추가 보완)

private LinkedList<Object>[] buckets;

private void initBuckets() {
    buckets = new LinkedList[capacity];    
    for (int i = 0; i < capacity; i++) {
	    buckets[i] = new LinkedList<>(); 
    }
}

모든 타입을 저장할 수 있는 Set을 위해 제네릭 매개변수를 모두 Object 타입으로 변경

private int hashIndex(Object value){
    return Math.abs(value.hashCode()) % capacity;
}

hashIndex만 hashCode를 사용해서 수정
- 여기에서 hashCode는 다형성에 의해 오버라이딩 된 hashCode가 수행
hashCode의 결과가 음수가 나올수 있기 때문에 절대값 사용

직접 만든 객체 보관

직접 만든 객체도 Set에 보관이 가능하다.
주의할 점은 직접 만든 객체에 hashCode(), equals() 메서드를 필수로 구현해야 한다.
hashIndex(Object value) 부분에서 value.hashCode() 호출
- 이 부분이 직접 재정의한 객체의 hashCode() 메서드
- hashCode() 메서드를 통해 해시 코드 반환되고 이후 인덱스 생성

add 순서 : 해시 코드 → 해시 인덱스 → add

그럼 equals()는 왜 오버라이딩 해야할까 ?

equals 같은 경우 contains에 쓰인다.
아래의 예시 코드를 확인해보자.

public boolean contains(Object searchValue){
    int hashIndex = hashIndex(searchValue);
    LinkedList<Object> bucket = buckets[hashIndex];
    return bucket.contains(searchValue);
}

원하는 값 (searchValue)을 찾기 위한 과정을 정리하면,

1. searchValue를 Hash Function에 넣어서 Hash Code를 구함

2. Hash Code를 통해 Hash Index를 구한다.

3. Hash Index를 통해 buckets에서 원하는 값이 있는 Linked List(=bucket) 찾음

4. bucket에서 contains 메서드로 값이 있는지 확인

5. bucket 리스트를 하나씩 탐색하면서 equal() 메서드 사용

≫ 이러한 이유로 contains 메서드에서 재정의한 객체의 equals() 메서드가 필요

따라서 직접 만든 객체에 Hash Set을 사용할 때,
hashcode와 equals 메서드는 필수적으로 재정의 해야한다 !

Object의 기본 기능

Object의 hashCode()
- 객체의 참조값을 기반으로 해시 코드 반환
Object의 equals()
- 객체의 참조값이 같아야 true 반환

hashCode, equals 모드를 구현하지 않는 경우

MemberOnlyHash m1 = new MemberOnlyHash("A");
MemberOnlyHash m2 = new MemberOnlyHash("A");

객체들은 기본 Object의 hashCode를 사용하여, 다른 해시코드의 값이 나온다.
설령 객체들이 같은 해시 인덱스에 있더라도, 각각의 객체들은 Obejct의 equals를 사용하여 다르다고 출력된다.
이러한 이유는 Object에서 hashCode, equals 메서드는 인스턴스의 참조값을 기반으로 하기 때문이다.

hashCode만 구현한 경우

MemberOnlyHash m1 = new MemberOnlyHash("A");
MemberOnlyHash m2 = new MemberOnlyHash("A");

이 경우는 해시코드와 해시 인덱스는 동일하다.

하지만 하나의 해시 배열에 각각의 객체가 들어가게 된다.
해시 add에서 contains 메서드를 사용하는데, 여기에서 equals가 들어간다.
equals를 구현하지 않았고, 때문에 객체의 참조값 기반으로 판단을 하게된다.
따라서 두 객체는 서로 다르다고 판별되어 각각 들어가게 된다.

제네릭과 인터페이스 도입

MySet 인터페이스

public interface MySet<E> {
    boolean add (E element);

    boolean remove(E value);

    boolean contains (E value);
}

MyHashSet ( 제네릭 도입)

import java.util.Arrays;
import java.util.LinkedList;

public class MyHashSetV3 <E> implements MySet<E>{
    static final int DEFAULT_INITIAL_CAPACITY = 10;
    LinkedList<E>[] buckets;

    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;


    public MyHashSetV3() {
        initBuckets();
    }

    public MyHashSetV3(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }

    private void initBuckets() {
        buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    @Override
    public boolean add(E value){
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        if(bucket.contains(value)){
            return false;
        }
        bucket.add(value);
        size ++;
        return true;
    }

    @Override
    public boolean remove(E value){
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        boolean result =  bucket.remove(value);
        if(result){
            size--;
            return true;
        }else{
            return false;
        }
    }

    @Override
    public boolean contains(E searchValue){
        int hashIndex = hashIndex(searchValue);
        LinkedList<E> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }

    private int hashIndex(E value){
        return Math.abs(value.hashCode()) % capacity;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSet32{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}

이전 Object를 타입 매개변수 E로 변경

public class MyHashSetV3Main {
    public static void main(String[] args) {
      MySet<String> set = new MyHashSetV3<>();
      set.add("A");
      set.add("B");
      set.add("C");
      System.out.println(set);

      // 검색
      String searchValue = "A";
      boolean result = set.contains(searchValue);
      System.out.println("set.contains(" + searchValue + ") = " + result);
    }
}

제네릭 덕분에 안정성이 높은 자료 구조 만들 수 있다.

Set

Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스
Set 인터페이스는 중복을 허용하지 않는 유일한 요소의 집합
또한 순서를 보장하지 않기 때문에 index를 통해 찾는 메서드들이 없음

Hash Set

특정 순서 없이 저장되어 순서를 보장하지 않는다.
추가,삭제,검색은 평균적으로 O(1) 복잡도 가짐
위에어 여태까지 구현한 Set

LinkedHash Set

Hash Set에 연결 리스트를 추가해서 요소들의 순서 유지
순서대로 조회시 요소들이 추가된 순서대로 반환
HashSet과 마찬가지로 주요 연산에 대해 평균 O(1) 시간 복잡도
연결 링크를 유지해야 하기 때문에 Hash Set보다는 무거움

Tree Set

이진 탐색 트리를 개선한 RB 트리를 내부에서 사용
주요 연산들은 O(log n)의 시간 복잡도를 가짐
데이터들을 정렬된 순서로 유지하면서 집합의 특성 유지

만약 데이터가 1, 5, 6, 10, 15와 같은 순서로 입력했을 경우 최악의 경우 O(n) 시간 복잡도
- 하지만 Tree Set은 RB 트리 알고리즘을 사용하며 최악의 경우에도 O(log n) 성능
이를 개선하기위해 AVL트리나 RB 트리와 같은 균형을 맞추는 트리 사용

HashSet 최적화

해시 기반 자료 구조를 사용하는 경우 통계적으로 입력한 데이터의 수가 배열의 크기를 75% 정도 넘어가면, 해시 인덱스가 자주 충돌한다. (이러한 경우 성능이 O(n)으로 될 수 있음
따라서 데이터의 양이 배열의 크시 75%를 넘어가면 배열의 크기를 2배로 늘린다. (그냥 참고 정도만 !)
이대 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다.

실무에서는 HashSet을 가장 많이 사용한다고 한다 !

Map

Map 인터페이스는 Collection와 관련 없음
Key는 맵 내에서 유일하고, 키를 통해 값을 빠르게 검색 가능
Key는 중복될 수 없지만, 값은 중복될 수 있음
Map은 순서를 유지하지 않음

자바는 HashMap, TreeMap, LinkedHashMap 등 다양한 Map 구현체 제공

Map 생성자 생성

Map<String,Integer> studentMap = new HashMap<>();

Map Key와 Value 저장

studentMap.put("studentA",90);
studentMap.put("studentB",80);

Key값으로 Value 찾기

Integer result = studentMap.get("studentD");
System.out.println("result = " + result);

KeySet으로 한번에 Value들 찾기

Set<String> keySet =  studentMap.keySet();

for (String key : keySet) {
    Integer value = studentMap.get(key);
    System.out.println("key = " + key + ", value = " + value);
}

KeySet 메서드에 반환값은 Set이다.
Key는 중복되지 않아야하므로, Set 활용

EntrySet을 활용하여 Key와 Value 함께 가져오기

Set<Map.Entry<String, Integer>> entries = studentMap.entrySet();
for (Map.Entry<String, Integer> entry : entries) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println("key= " + key + ", value= " + value);
}

Set 안에 제네릭이 좀 복잡하다.
이거는 자동완성으로 ...

Values() 가져오기

Collection<Integer> values = studentMap.values();
for (Integer value : values) {
    System.out.println("value = " + value);
}

putIfAbsent

studentMap.putIfAbsent("studentB",100);

studentB 가 studentMap에 없는 경우 100을 추가하라는 명령어

Map 구현체

Map 인터페이스는 키-값 쌍을 저장하는 자료구조
대표적으로 HashMap, TreeMap, LinkedHashMap 등이 있다.
- 해당 구현체 특성들은 Set이랑 거의 똑같음
Set과 Map은 상당히 비슷한데, 사실 Set은 Map에서 Value만 뺀 것이다.
해시를 사용해서 키와 값을 저장하는 자료 구조를 일반적으로 해시 테이블 또는 딕셔너리라고 함
Map의 Key로 사용되는 객체는 hashCode()와 equals()를 반드시 구현해야 한다 !
참고로 containsKey()를 하는 것은 O(1), containsValue()를 하는 것은 O(n)이다.
실무에서는 Map이 필요한 경우 HashMap을 주로 사용한다고 한다 !

(Set과 마찬가지로)
Map의 Key가 내가 만든 객체라면
반드시 HashCode(), equals() 매서드를 재정의해야 한다 !!

Stack 자료 구조

후입 선출
자바의 Stack 클래스는 내부에서 Vector라는 자료 구조를 사용
지금은 더 빠른 좋은 자료 구조가 많아서 Vector의 Stack을 사용하지 않는 것을 권장
대신에 Deque를 사용하는 것이 좋다.

Queue 자료 구조

선입 선출
Queue 인테페이스는 List, Set과 같이 Collection의 자식
Queue의 대표적인 구현체는 ArrayDeque, LinkedList가 있다.
- 참고로 LinkedList는 Deque와 List 인터페이스를 모두 구현

Deque 자료 구조

deque.offerFirst(1);
deque.offerLast(3);

System.out.println("deque.pollFirst() = " + deque.pollFirst());
System.out.println("deque.pollLast() = " + deque.pollLast());

Deque의 대표적인 구현체는 ArrayDeque와 LinkedList가 있다.
이 중 ArrayDeque가 모든 면에서 더 빠르다.
- 시스템 메모리 접근 패턴, CPU 캐시 최적화 등을 고려했을 때 ArrayDeque가 더 나음
Deque는 Stack과 Queue로 사용하기 위한 메서드 이름까지 제공

ArrayDeque<Integer> deque = new ArrayDeque<>();

deque.push(1);
deque.push(2);
deque.push(3);

System.out.println("deque.pop() = " + deque.pop());
System.out.println("deque.pop() = " + deque.pop());
System.out.println("deque.pop() = " + deque.pop());
System.out.println(deque);

위의 코드는 Stack을 위한 메서드

ArrayDeque<Integer> deque = new ArrayDeque<>();

deque.offer(1);
deque.offer(2);
deque.offer(3);

System.out.println("deque.poll() = " + deque.poll());
System.out.println("deque.poll() = " + deque.poll());
System.out.println("deque.poll() = " + deque.poll());
System.out.println(deque);

위의 코드는 Queue를 위한 메서드

Queue에서 offer / poll 메서드

offer과 poll 메서드는 큐가 비었을 때도 예외 없이 반환값으로 상태를 확인 할 수 있다.
반면 pop과 push는 스택이 비어있으면 예외를 발생시킨다.
offer는 제안,제공하다는 의미로 큐가 거절을 할 수도 있다.
poll은 가볍게 확인, 조사하다는 의미로 조심스럽게 확인하고 없으면 null을 반환 한다.

실무에서는 ArrayDeque를 쓰면 될 것 같다

순회

Iterable, Iterator

다양한 자료 구조가 있고, 각각의 자료 구조마다 데이터 접근하는 방법이 다르다.
자바에서 Iterable과 Iterator 인터페이스를 통해 위의 문제 해결 가능
Iterable (반복 가능한), Iterator (반복자)
Iterable을 구현한다는거는 반복이 가능하다는 것을 의미한다.

Iterable 인터페이스의 주요 메서드

 public interface Iterable<T> {
 	Iterator<T> iterator();
 }

Iterator 인터페이스의 주요 메서드

public interface Iterator<E> {
     boolean hasNext();
     E next();
 }

자료구조에 다음 요소가 있는지 물어보고, 있으면 다음 요소를 꺼네는 과정 반복
만일 다음 요소가 없으면 종료

간단한 Iterator 구현체 만들기

클래스 구조도

MyArrayIterator 구현

package collection.iterable;

import java.util.Iterator;

public class MyArrayIterator implements Iterator<Integer> {

    private int currentIndex = -1;
    private int[] targetArr;

    public MyArrayIterator(int[] targetArr) {
        this.targetArr = targetArr;
    }

    @Override
    public boolean hasNext() {
        return currentIndex < targetArr.length - 1;
    }

    @Override
    public Integer next() {
        return targetArr[++currentIndex];
    }
}

생성자를 통해 반복자가 사용할 배열 참조
hasNext(), next() 메서드들이 가장 핵심이다.
- 참고로 인덱스의 길이는 0부터 시작

Iterator를 테스트 하기위한 간단한 자료구조

package collection.iterable;

import java.util.Iterator;

public class MyArray implements Iterable<Integer>{
    private int[] number;

    public MyArray(int[] number) {
        this.number = number;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new MyArrayIterator(number);
    }
}

Iterable 인터페이스를 구현 (반복 가능하다는 의미)
따라서 MyArray는 반복할 수 있다는 의미를 가짐
iterable 인터페이스를 구현하면 iterator() 메서드를 구현해야 한다.

Iterator를 테스트

package collection.iterable;

import java.util.Iterator;

public class MyArrayMain {
    public static void main(String[] args) {
        MyArray myArray = new MyArray(new int[]{1,2,3,4});

        Iterator<Integer> iterator = myArray.iterator();
        System.out.println("iterator 사용");
        while(iterator.hasNext()){
            System.out.println("value = " + iterator.next());
        }

    }
}

iterator 객체 생성 후 순회

런타임 메모리 구조도

for each문

while(iterator.hasNext()){
    System.out.println("value = " + iterator.next());
}

for(int value : myArray){
    System.out.println("value = " + value);
}

위의 두 코드는 똑같은 코드이다.
Iterable 인터페이스를 구현한 객체에 대해서는 향상된 for문 사용 가능
만일 구현이 안된 경우는 for each문 사용 불가능
아래 코드가 깔끔하기때문에, 해당 코드 사용을 권장

자바가 제공하는 Iterable, Iterator

자바 컬렉션 프레임워크는 배열 리스트, 연결 리스트, 해시 셋, 열결 해시 셋, 트리 셋 등등 다양한 자료 구조를 제공
컬렉션 프레임워크를 사용하는 개발자가 편리하고 일관된 방법으로 자료구조 순회 가능
Iterable 인터페이스를 제공하고, 각각의 구현체에 맞는 Iterator도 구현
Map의 경우 Key, Value 까지 있어서 바로 순회 불가능
- 하지만 keySet(), values()를 호출하면 Set, Collection을 반환하여 순회 가능
- Entry를 Set 구조로 반환하는 entrySet()도 순회 가능

// iterable
private static void foreach(Iterable<Integer> iterable) {
    System.out.println("iterable.getClass() = " + iterable.getClass());
    for (Integer ls : iterable) {
        System.out.println("ls = " + ls);
    }
}

// iterator
private static void printAll(Iterator<Integer> iterator) {
    System.out.println("iterator.getClass() = " + iterator.getClass());
    while(iterator.hasNext()){
        System.out.println("iterator.next() = " + iterator.next());
    }
}

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);

HashSet<Integer> set = new HashSet<>();
set.add(1);
set.add(2);

foreach(list);
foreach(set);

printAll(list.iterator());
printAll(set.iterator());

foreach () 메서드의 매개변수 타입은 Iterable여야 한다.
- 이해가 안될 경우, 위에 클래스 구조도 보면 이해 될 듯
printAll() 메서드의 매개변수 타입은 Iterator여야 한다.
위와 같은 Iterator, Iterable인터페이스를 통해 다형성을 적극 활용 가능

여러 자료 구조의 iterator의 구현은 다르겠지만 우리는 그냥 iterator 인터페이스만 쓰면 된다.
hashNext나 next만 알면 어떤 것이든 일관성 있게 iterator로 탐색 가능하다.

Iterator 디자인 패턴

이 패턴은 우리가 지금까지 해왔던 패턴과 똑같다.
내부 구조를 노출하지 않고도 그 요소들에 순차적으로 접근할 수 있게 해주는 패턴이다.
Iterator 패턴은 컬렉션의 구현과는 독립적으로 요소들을 탐색가능
- 책임 분리
따라서 코드의 복잡성을 줄이고 재사용성을 높인다.
컬렉션에 상관없이 객체 접근 순회 방식을 통일하고자 할 때 사용된다.
컬렉션의 복잡한 내부 구조를 클라이언트로 부터 숨기고 싶은 경우 사용 (편의 + 보안)

💠 반복자(Iterator) 패턴 - 완벽 마스터하기

Iterator Pattern 반복자(Iterator) 패턴은 일련의 데이터 집합에 대하여 순차적인 접근(순회)을 지원하는 패턴이다. 데이터 집합이란 객체들을 그룹으로 묶어 자료의 구조를 취하는 컬렉션을 말한다.

inpa.tistory.com

이해가 잘 되지 않는다면,

Inpa님의 "예제를 통해 알아보는 Iterator 패턴" 부분을 봐보자

정렬

비교자 Comparator

 public interface Comparator<T> {
 int compare(T o1, T o2);
 }

비교자를 통해 두값 비교 기준 직접 할 수 있다.

활용 예시

import java.util.Arrays;
import java.util.Comparator;

public class SortMain2 {
    public static void main(String[] args) {
        Integer[] array = {3,2,1};
        System.out.println(Arrays.toString(array));

        System.out.println("Comparator 비교");

        Arrays.sort(array,new AscComparator());
        System.out.println(Arrays.toString(array));

        Arrays.sort(array,new DescComparator());
        System.out.println(Arrays.toString(array));

        Arrays.sort(array,new DescComparator().reversed());
        System.out.println(Arrays.toString(array));

    }

    static class DescComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2){
            System.out.println("o1= " + o1 + " o2=" + o2);
            return ((o1<o2)? -1: (o1==o2) ? 0 : 1) * -1;
        }
    }

    static class AscComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2){
            System.out.println("o1= " + o1 + " o2=" + o2);
            return (o1<o2)? -1: (o1==o2) ? 0 : 1;
        }
    }
}

Comparator 인터페이스 구현
Comparator 인터페이스에 reversed() 메서드도 사용 가능

Comparator, Comparable

자바에서 기본으로 제공하는 Integer, String 같은 객체를 제외하고,

Myuser와 같이 직접 만든 객체를 정렬하려면 어떻게 해야 할까 ?

Comparable 인터페이스 구현

package collection.compare;

import java.util.Comparator;

public class MyUser implements Comparable<MyUser> {
    private String id;
    private int age;

	. . .

    @Override
    public int compareTo(MyUser o) {
       return this.age  < o.age ? -1 : (this.age == o.age ? 0 : 1);
    }
}

compareTo를 보면 내림, 오름 차순인지 알기 어렵다.
좀 쉽게 이해 하기위해서, this < o / -1 , 0, 1 의 순서를 기억하자
"<"의 방향은 바꾸지 말고 ...
만일 o < this 또는 1, 0, -1 중 하나이면 내림 차순
o < this 과 1, 0, -1 이면 오름차순
가장 기본인 this와 o / -1 , 0, 1 는 오름 차순

System.out.println("Comparable 기본 정렬");
Arrays.sort(array);
System.out.println(Arrays.toString(array));

위와 같이 직접 만든 객체를 정렬하려면 Comparable 인터페이스를 구현하면 된다
- Comparable로 비교 가능하게 됐다.
Comparable을 통해 구현한 순서를 자연 순서 (Natural Ordering)이라 한다.
해당 순서는 MyUser가 구현한 대로 age 기준으로 오름차순 정렬된다.

만약 객체가 가지고 있는 Comparable 기본 정렬이 아니라 다른 정렬을 사용하고 싶다면 ??

비교할 수 있는 Comparator 생성

import java.util.Comparator;

public class Idcomparator implements Comparator<MyUser> {

    @Override
    public int compare(MyUser o1, MyUser o2) {
        return o1.getId().compareTo(o2.getId());
    }
}

System.out.println("IdComparator 정렬");
Arrays.sort(array,new Idcomparator());
System.out.println(Arrays.toString(array));

Arrays.sort(array, new Idcomparator().reversed());
System.out.println(Arrays.toString(array));

해당 코드는 아이디를 기준으로 정렬한다.
Arrays.sort의 인수로 비교자 Comparator를 만들어 넘겨준다.
객체가 기본적으로 가지고 있는 Comparable을 무시하고 Comparator를 사용해서 정렬한다.

직접 만든 객체를 정렬할 때, Comparable, Comparator 두개 다 구현하지 않으면 런타임 오류 발생 !

보통은 Comparable을 구현해서 정의한다.

이렇게 하면 객체는 이름 그대로 비교할 수 있는 객체가 된다.

하지만 기본 정렬 외에 다른 정렬 방법을 사용해야 하는 경우는

Comparator 비교자를 구현해서 정렬 메서드에 전달하면 된다.

이렇게 전달한 Comparator은 항상 우선권을 가진다.

참고로 자바가 제공하는 Integer, String 같은 기본 객체들은 대부분 Comparable이 구현되어 있다.

정렬은 배열 뿐만 아니라 순서가 있는 List 같은 자료 구조에도 사용 가능하다.

List 정렬

package collection.compare;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

public class SortMain4 {
    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("a",30);
        MyUser myUser2 = new MyUser("b",20);
        MyUser myUser3 = new MyUser("c",10);

        LinkedList<MyUser> list = new LinkedList<>();
        list.add(myUser1);
        list.add(myUser2);
        list.add(myUser3);

        System.out.println("Comparable 기본 정렬");
        list.sort(null);
        // Collections.sort(list);
        System.out.println(list);

        System.out.println("IdComparator");
        list.sort(new Idcomparator());
        System.out.println(list);


    }
}

Collections.sort(list) 이런 방식으로도 가능은 하지만, list.sort() 방식이 더 권장 됨 (객체지향적)
list.sort() 메서드의 인자에 비교자 comparator를 넘겨 줄 수 있다.

Tree 구조와 정렬

TreeSet과 같은 이진 탐색 트리 구조는 이미 데이터를 정렬하면서 보관
따라서 TreeSet, TreeMap은 Comparable 또는 Comparator가 필수적 !

TreeSet<MyUser> treeSet1 = new TreeSet<>();
treeSet1.add(myUser1);
treeSet1.add(myUser2);
treeSet1.add(myUser3);
System.out.println("Comparable 기본 정렬");
System.out.println(treeSet1);

TreeSet<MyUser> treeSet2 = new TreeSet<>(new Idcomparator());
treeSet2.add(myUser1);
treeSet2.add(myUser2);
treeSet2.add(myUser3);
System.out.println("Idcomparator 기본 정렬");
System.out.println(treeSet2);

별도의 비교자 Comparator를 제공하지 않으면 객체가 구현한 Comparable 사용
별도의 비교자를 넣고 싶으면 TreeSet 생성할 때, 별도의 비교자 Comparator 제공

자바의 정렬 알고리즘은 거의 완성형에 가깝다 !

따라서 복잡한 정렬 알고리즘을 신경쓰지않으면서,

정렬의 기준만 간단히 변경할 수 있도록 정렬의 기준을
Comparable, Comparator 인터페이스를 통해 추상화해 두었다 .

자연 순서 외에 다른 정렬 기준이 필요하면 Comparator를 구현하여 제공하자 !

Collections utils (컬렉션 유틸)

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

Integer max = Collections.max(list);
System.out.println("max = " + max);

Integer min = Collections.min(list);
System.out.println("min = " + min);

Collections.shuffle(list);
System.out.println("shuffle list = " + list);

Collections.sort(list);
System.out.println("sort list = " + list);

Collections.reverse(list);
System.out.println("reverse list = " + list);

max / min
shuffle
sort (Collections.sort()는 권장되지 않음)
reverse

불변 컬렉션 생성

List<Integer> list = List.of(1,2,3);
System.out.println("list = " + list);

Set<Integer> set = Set.of(1,2,3);
System.out.println("set = " + set);

Map<Integer,String>  map = Map.of(1,"one",2,"two");
System.out.println("map = " + map);
System.out.println("list class = " + list.getClass());

// list.add(1);  이런거 안됨 !!

불변 컬렉션으로 값 변경 불가능

불변 컬렉션을 가변 컬렉션으로 전환

List<Integer> list = List.of(1, 2, 3);

// 이렇게 불변으로 새로운 객체 만들면 가변 리스트로 가능
ArrayList<Integer> mutableList = new ArrayList<>(list);
mutableList.add(4);
System.out.println("mutableList = " + mutableList);


// 다시 불변으로 변경
List<Integer> unmodifiableList = Collections.unmodifiableList(mutableList);
// unmodifiableList.add(1); 불가능
System.out.println("unmodifiableList = " + unmodifiableList);

빈 리스트 생성

// 가변 리스트
ArrayList<Integer> list1 = new ArrayList<>();
LinkedList<Integer> list2 = new LinkedList<>();

// 불변 리스트
List<Integer> list4 = List.of();
System.out.println("list4.getClass() = " + list4.getClass());

Arrays.asList() 메서드를 통해 List.of 처럼 할 수 있지만, 권장되는 방식이 아님

멀티스레드 동기화

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

System.out.println("list.getClass() = " + list.getClass());

List<Integer> synchronizedList = Collections.synchronizedList(list);
System.out.println("synchronizedList.getClass() = " + synchronizedList.getClass());

멀티스레드 상황에서 동기화 문제가 발생하지 않는 안전한 리스트로 만들 수 있다.
하지만 동기화 작업으로 일반 리스트보다 성능이 더 느리다.

Collection이 아닌 Collections의 메서드이다 !!
Collection은 모든 자료 구조의 가장 기본적인 인터페이스

컬렉션 프레임워크 전체 정리

일관성
재사용성
확장성
다형성

Collection 인터페이스의 주요 메서드

add(E e)
remove(Object o)
size() 
isEmpty()
contains(Object o)
iterator()
clear()

모든 기능들을 다 제공하지는 않음 (공통적인 것들만 제공)

인터페이스

Collection

단일 루트 인터페이스로, 모든 컬렉션 클래스가 이 인터페이스를 상속

List

순서가 있는 컬렉션으로 중복 가능하고 인덱스를 통해 접근

Set

중복 요소를 허용하지 않는 컬렉션으로, 특정 위치가 없어 인덱스를 통해 요소 접근 불가

Queue

요소가 처리되기 전에 보관되는 컬렉션

Map

키와 값 쌍으로 요소를 저장하는 객체로 Collection 인터페이스를 상속 받지 않음

구현

List

ArrayList는 내부적으로 배열을 , LinkedList는 연결 리스트 사용

Set

HashSet은 해시 테이블, LinkedHashSet은 해시 테이블과 연결리스트, TreeSet은 RB 트리를 사용

Queue

LinkedList는 연결 리스트 , ArrayDeque는 배열 기반의 원형큐 사용 (ArrayDeque가 빠름)

Map

HashMap은 해시 테이블, LinkedHashMap은 해시 테이블과 연결 리스트, TreeMap은 RB 트리를 사용

실무 선택 가이드

List의 경우 대부분 ArrayList를 사용
Set읭 경우 대부분 HashSet을 사용
- 입력 순서를 유지해야한다면 LinkedHashSet, 정렬된 순서가 필요하면 TreeSet
Map의 경우 대부분 HashMap을 사용
Queue의 경우 대부분 ArrayDeque 사용

'🔖Java' 카테고리의 다른 글

Java 중급 2-1 (제네릭) (0)	2025.04.17
Java 기본 (객체 지향 프로그래밍) (0)	2025.03.16
Java 중급-1 (0)	2025.03.16
Java 기초 정리 (0)	2025.03.09

현재글자바 중급 2-2 (컬렉션 자료구조 구현)

Jerry의 컴퓨터 일기

기억보다는, 기록을 남깁니다.

Today :
Yesterday :

« 2025/05 »
일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31