Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - ArrayList, Deque

들어가며

• 해당 글은 아래 알고리즘에 대해 보기 전 Java에서 PS를 할 시 자주 사용할 Collection 클래스 또는 다른 유용한 클래스들을 설명한다.
• 설명하면서 간단히 예제와 함께 사용방법들 역시 익히는 것이 목표이다.

 

 

Sequence Containers

• Sequence Containers는 다음과 같은 특징을 가진다.
• Sequence Containers의 경우, 데이터를 순차적으로 저장하며 정렬 상태를 유지하지 않는다.
• 구현이 단순하여 가볍고 빠르다.
• 기본적으로 만나볼 수 있는 Sequence Containers는 ArrayList(Vector)와 Deque(ArrayDeque)가 있다.

 ArrayList(구 Vector)

• 일반적으로 사용하는 배열(Array)의 경우, 랜덤 엑세스가 가능하고 읽고 쓰기가 O(1)이라는 강력한 장점을 가지지만 컴파일 시 결정된 배열의 크기를 재조정할 수 없다는 문제점이 존재한다.
• 이를 해결하기 위하여 만들어진 것이 Vector<> 컬랙션이고 이를 발전시켜 구현한 것이 ArrayList<>이다.
• Java에서 ArrayList는 List 인터페이스를 구현한 컬랙션으로 데이터의 순서를 유지하며 중복값을 허용한다.
• ArrayList의 기본적인 연산은 다음과 같다.

메서드	메서드 타입	설명
ArrayList()	constructor	ArrayList 객체를 생성하여 반환한다. 초기 용량은 10이다.
ArrayList(Collection c)	constructor	지정된 컬랙션 c의 모든 요소를 포함하는 ArrayList 객체를 생성하여 반환한다.
ArrayList(int inititalCapacity)	constructor	초기 용량이 initialCapacity인 ArrayList 객체를 생성하여 반환한다.
removeAll(Collection c)	void	지정된 컬랙션 c의 모든 요소를 ArrayList에서 삭제한다.
add(E e)	boolean	객체 e를 ArrayList에 추가한다.
remove(E e)	boolean	객체 e를 ArrayList에서 제거한다. 존재하지 않을 시 false를 반환한다.
contains(E e)	boolean	객체 e가 ArrayList에 존재하는지 확인한다.
contains(Collection c)	boolean	컬랙션 c에 있는 모든 요소가 ArrayList에 존재하는지 확인한다.
toArray()	Object[]	ArrayList의 모든 요소를 배열로 변환하여 반환한다.

import java.util.*;

public class StudyCode {
    public static void main(String[] args) throws Exception{
        ArrayList<Integer> vector = new ArrayList<>(20);

        for (int i = 0; i<15; i++){
            vector.add(i);
        }
        System.out.println(vector.contains(10));
        System.out.println(vector.contains(20));

        Object[] vectorData = vector.toArray();
        vector.remove(5);

        for (int element: vector){
            System.out.println(element);
        }

        System.out.println();
        
        for(Object element: vectorData){
            System.out.println((int)element);
        }
    }
}​

• 위 예제는 ArrayList를 활용한 기본적인 연산들을 코드로 나타낸 것이다.
• ArrayList를 사용할 경우 주의할 점이 있는데 데이터를 삽입할 시에 시간은 O(1)로 상수 시간을 가지지만 지정된 용량을 초과할 시 배열을 복사하여 재할당하는 reallocation이 발생한다. 이는 연산량을 많이 잡아먹게 되기 때문에 최대 용량을 넉넉히 잡은 상태에서 사용하는 것을 추천한다.

Deque(ArrayDeque)

• 덱(Deque)는 컨테이너의 Front와 Rear 양방향에서 데이터의 삽입/삭제 연산이 가능한 컬랙션이다.
• Deque는 구현체가 LinkedList와 ArrayDeque로 2개로 나뉘어져 있으며 일반적으로 ArrayDeque가 LinkedList대비 더 좋은 성능을 보인다.
• 이는 LinkedList가 Array와는 다르게 연속된 메모리 공간을 차지하고 있지 않기 때문에 접근 시간이 느려진다는 것과 캐시의 지역성(Locality)와도 연관되어 있는 것이 원인이다.
• 양방향에서 데이터의 삽입/삭제가 가능하므로, Queue와 Stack의 기능까지도 모두 포함하여 사용할 수 있다.
• Deque의 연산은 다음과 같다.

메서드	메서드 타입	설명
ArrayDeque()	constructor	초기 용량이 16인 ArrayDeque 객체를 생성하여 반환한다.
ArrayDeque(Collection c)	constructor	컬랙션 c의 모든 요소를 포함하는 ArrayDeque 객체를 생성하여 반환한다.
ArrayDeque(int capacity)	constructor	주어진 용량 capacity를 가진 ArrayDeque 객체를 생성하여 반환한다.
addFirst(E e)	void	ArrayDeque의 Front에 객체를 삽입한다.
offerFirst(E e)	boolean	ArrayDeque의 Front에 객체를 삽입한다. 용량 제한인 경우 false를 반환한다.
addLast(E e)	void	ArrayDeque의 Rear에 객체를 삽입한다.
offerLast(E e)	boolean	ArrayDeque의 Rear에 객체를 삽입한다. 용량 제한인 경우 false를 반환한다.
pollFirst()	E	ArrayDeque의 Front에 있는 객체를 삭제하고 그 객체를 반환한다.
pollLast()	E	ArrayDeque의 Rear에 있는 객체를 삭제하고 그 객체를 반환한다.
peekFirst()	E	ArrayDeque의 Front에 있는 객체를 조회하여 반환한다.
peekLast()	E	ArrayDeque의 Rear에 있는 객체를 조회하여 반환한다.
contains(Object o)	boolean	주어진 객체가 ArrayDeque에 존재하는지를 확인한다.
iterator()	Iterator<E>	ArrayDeque를 정방향으로 순회하는 반복자를 반환한다.
descendingIterator()	Iterator<E>	ArrayDeque를 역방향으로 순회하는 반복자를 반환한다.

import java.util.*;

public class StudyCode {
    static Deque<Integer> deque;

    public static void main(String[] args) throws Exception{
        ArrayList<Integer> vector = new ArrayList<>(20);
        for (int i = 0; i<15; i++){
            vector.add(i);
        }
        deque = new ArrayDeque<>(vector);

        printElement();
        printReverseElement();

        System.out.println();

        deque.addFirst(-1);
        deque.addFirst(-2);
        deque.addLast(15);
        deque.addLast(16);

        printElement();
        printReverseElement();

        System.out.println();

        deque.removeFirst();
        deque.removeLast();

        System.out.println(deque.peekFirst());
        System.out.println(deque.peekLast());

        System.out.println();

        printElement();
        printReverseElement();
    }

    static void printElement(){
        for (int element: deque){
            System.out.print(element + " ");
        }
        System.out.println();
    }

    static void printReverseElement(){
        Iterator<Integer> iter = deque.descendingIterator();

        while(iter.hasNext()){
            System.out.print(iter.next() + " ");
        }
        System.out.println();
    }
}