자바의 정석 Chapter 11 컬렉션 프레임워크

Eunkyung·2021년 10월 22일
Java
0

Java

목록 보기
9/21

1. 컬렉션 프레임워크

앞서 배열은 한 번 생성하면 크기를 변경할 수 없고, 항목을 저장, 삭제, 추가하는 메소드가 없기 때문에 직접 인덱스를 사용해야 하는 불편함이 있었다. 이러한 불편함을 해결하기 위해 자바는 컬렉션 프레임 워크를 제공한다.

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

List 인터페이스

List 컬렉션은 배열과 비슷하게 객체를 인덱스로 관리하는데 저장 용량이 자동으로 증가하고, 객체 저장 시 인덱스가 자동으로 부여되는 차이점이 있다.
List 컬렉션은 객체 자체를 저장하는 것이 아니라 객체의 번지를 참조하여 동일한 객체를 중복 저장할 수 있으며, 이 때 동일한 번지가 참조된다.
구현 클래스로는 ArrayList, Vector, LinkedList 등이 있다.

중복을 허용하면서 저장순서가 유지되는 컬렉션 구현 시 사용

i. ArrayList

List 인터페이스의 대표적인 구현 클래스로 저장되는 객체 수가 늘어나면 용량이 자동적으로 증가하고 인덱스는 0부터 시작한다.

ArrayList를 생성하기 위해서는 저장할 객체 타입 E 타입 파라미터 자리에 표기하고 기본 생성자를 호출한다. 다음 코드는 String 타입을 저장하는 ArrayList 생성하는 코드이다.

List<String> list = new ArrayList<String>();

ArrayList에 객체 추가 시 0번 인덱스부터 차례로 저장되고, 특정 인덱스의 객체 제거 시 바로 뒤 인덱스부터 마지막 인덱스까지 모두 한 칸씩 당겨진다. 이와 마찬가지로 특정 인덱스에 객체 추가 시 해당 인덱스부터 마지막 인덱스까지 모두 한 칸씩 밀려난다.
그렇기 때문에 빈번한 객체 삭제와 삽입이 일어날 경우 ArrayList를 사용하는 것은 적절하지 않다.

ii. Vector

Vector는 ArrayList와 동일한 내부 구조를 가지고 있지만 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 Vector의 메소드들을 실행할 수 없고, 하나의 스레드가 메소드 실행을 완료해야만 다른 스레드가 메소드를 실행할 수 있다. 이는 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있음을 의미하며 스레드에 안전하다고 표현한다.

iii. LinkedList

LinkedList는 데이터와 포인터로 이루어진 노드가 일렬로 이어진 형태의 자료구조로 각 노드의 주소는 연속적이지 않은 특징이 있다. 특정 인덱스의 객체 삽입, 삭제 시 포인터가 가르키는 주소만 달라지기 때문에 빈번한 객체 삽입, 삭제 시 ArrayList보다 좋은 성능을 발휘한다.

연결리스트 종류

  • Single Linked List (단일 연결리스트)
    - 구조

    class Node {
    Node next; // 다음 요소의 주소 저장
    Object obj; // 데이터 저장
}

  • Doubly Linked List (이중 연결리스트)

    • 구조
      class Node {
    Node next; // 다음 요소의 주소 저장
    Node previous; // 이전 요소의 주소 저장
    Object obj; // 데이터 저장
}
    • 단일 연결리스트는 한 방향으로만 순회가 가능한 반면, 이중 연결리스트는 양방향으로 순회 가능
    • 모든 노드를 순회할 때, 반으로 나눠서 오른쪽은 next 포인터로, 왼쪽은 prev 포인터로 순회 가능
    • 페이지 교체 알고리즘 중 LRU 구현에 사용

  • Circular Linked List (원형 연결리스트)
    - 끝이 없고 원형으로 순환하는 형태

    • tail의 next 포인터가 맨 앞의 노드 head를 가리킴
    • head와 tail을 명시해, 노드 순회 시 무한하게 반복 순회하는 일이 없도록 해야함
    • CPU 스케줄링 알고리즘 중 Round Robin(RR) 알고리즘 구현에 사용

정리

  1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
  2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
    • LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠른 반면, ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 늦다.

Set 인터페이스

Set 컬렉션은 List 컬렉션과 달리 중복을 허용하지 않고 저장순서가 유지되지 않는다. Set 컬렉션은 인덱스로 객체를 검색해서 가져오는 메소드가 없기 때문에 전체 객체를 대상으로 한 번씩 반복해서 가져오는 반복자(Iterator)를 제공한다.
구현 클래스로는 HashSet, LinkedHashSet, TreeSet 등이 있다.

중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 구현 시 사용

i. HashSet

HashSet은 객체를 저장하기 전에 객체의 hashCode() 메소드를 호출해서 해시코드를 얻어내고, 이미 저장되어 있는 객체들의 해시코드와 비교한다. 만약 동일한 해시코드가 있다면 다시 equals() 메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.

같은 문자열을 HashSet에 저장할 경우 동등한 객체로 간주되어 하나의 값만 저장이 되는데, 그 이유는 String 클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열인 경우 hashCode()의 리턴값은 같게, equals()의 리턴값은 true가 나오게 했기 때문이다.

Map 인터페이스

Map 컬렉션은 키와 값으로 구성된 Map.Entry 객체를 저장하는 구조로 키는 중복 불가능, 값은 중복 가능하다는 특징이 있다.
구현 클래스로는 HashMap, TreeMap, Hashtable, Properties 등이 있다.

i. HashMap

HashMap의 키와 값 타입으로 기본 타입은 사용할 수 없고 클래스 및 인터페이스 타입만 사용 가능하다. 만약 정수 타입을 저장하고 싶을 때는 Integer 타입을 사용하면 되는데 이 때 오토박싱되어 저장된다.

ii. Hashtable

Hashtable은 HashMap과 동일한 내부 구조를 가지고 있지만 동기화된 메소드로 구성되어 있어 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있어서 스레드에 안전하다.

1.3 Stack과 Queue

마지막으로 컬렉션 프레임워크에 있는 Stack 클래스와 Queue 인터페이스에 대해 알아보자.

Stack

마지막에 저장한 데이터를 가장 먼저 꺼내는 자료구조(Last In First Out)로 순차적인 추가, 삭제가 용이한 ArrayList를 사용한다.
스택의 활용 ex) 수식계산, 수식괄호검사, 웹브라우저의 뒤로/앞으로

Queue

처음에 저장한 데이터를 가장 먼저 꺼내는 자료구조(First In First Out)로 비순차적인 추가, 삭제가 용이한 LinkedList를 사용한다.
스택과 달리 큐는 인터페이스만 정의되어 있어 인터페이스를 구현한 클래스 중 하나(대표적인 구현 클래스 : LinkedList)를 선택해서 사용한다.
큐의 활용 ex) 최근사용문서, 버퍼

스택과 큐
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class StackQueueEx {
    public static void main(String[] args) {
        // Stack은 클래스로 제공
        // Queue는 Queue 인터페이스를 구현한 클래스 중 하나를 선택해서 사용
        Stack st = new Stack();
        Queue q = new LinkedList(); // Queue 인터페이스의 구현체인 LinkedList 사용

        st.push("0");
        st.push("1");
        st.push("2");

        q.offer("0");
        q.offer("1");
        q.offer("2");

        System.out.println("Stack");
        while (!st.empty()) {
            System.out.println(st.pop()); // 2 1 0
        }
        System.out.println("Queue");
        while (!q.isEmpty()) {
            System.out.println(q.poll()); // 0 1 2
        }
    }
}
스택 구현하기
import java.util.EmptyStackException;
import java.util.Vector;

public class MyStack extends Vector {
    public Object push(Object item) {
        addElement(item);
        return item;
    }

    public Object pop() {
        Object obj = peek(); // 스택에 저장된 마지막 요소 읽어옴
        // 만약 스택이 비어있다면 EmptyStackException 발생
        // 마지막 요소 삭제
        removeElementAt(size() - 1); // 마지막 인덱스
        return obj;
    }

    public Object peek() {
        int len = size();
        if (len == 0) {
            throw new EmptyStackException();
        }
        // 마지막 요소 반환
        return elementAt(len - 1);
    }

    public boolean empty() {
        return size() == 0;
    }

    public int search(Object o) {
        int i = lastIndexOf(o); // 끝에서부터 탐색
        if (i >= 0) {
            return size() - i;
        }
        return -1; // 해당 객체를 찾지 못하면 -1 반환
    }
}

PriorityQueue

Queue 인터페이스의 구현체 중 하나로 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내며, null은 저장할 수 없다. 힙 형태로 저장하여 최대값이나 최소값을 빠르게 찾을 수 있다.

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueEx {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();
        pq.offer(3);
        pq.offer(1);
        pq.offer(5);
        pq.offer(2);
        pq.offer(4);
        System.out.println(pq);
        Object obj = null;
        // 우선순위가 높은 것부터 출력되는데 숫자가 작을수록 우선순위가 높음
        while ((obj = pq.poll()) != null) {
            System.out.println(obj);  // 1 2 3 4 5
        }
    }
}

Deque

Deque은 Queue의 변형으로 스택과 큐를 합쳐놓은 것과 같으며 양쪽 끝에 추가 및 삭제가 가능하다.
Deque의 조상은 Queue이며, 구현체로는 ArrayDeque과 LinkedList 등이 있다.

출처

profile
Eunkyung
꾸준히 하자
이전 포스트

자바의 정석 Chapter08 예외처리

다음 포스트

Comparable와 Comparator

0개의 댓글