java [7] Collections-1

lsy·2022년 10월 22일

자바

목록 보기

8/14

Collections Framework

컬렉션 프레임워크는 데이터들을 저장하는 클래스들을 표준화한 설계를 뜻한다. 컬렉션 프레임워크는 다수의 데이터를 다루는 데 필요한 다양하고 풍부한 클래스들을 제공하고 있다.

JDK1.2 이전까지는 Vector, Hashtable, Properties와 같은 클래스들을 이용해 서로 다른 각자의 방식으로 처리해야 했으나 JDK1.2부터 컬레션 프레임워크가 등장하고 다양한 종류의 컬렉션 클래스가 추가되었고, 모든 클련 클래스를 표준화된 방식으로 다룰 수 있게 체계화되었다.

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

컬렉션 프레임워크는 크게 3가지 타입이 존재한다고 인식하고 List, Set, Map 인터페이스들로 정의했다. 그 후에 List와 Set의 공통된 기능을 뽑아 Collection이라는 인터페이스를 추가로 정의하였다.

List는 순서가 있는 데이터의 집합이며, 중복을 허용한다.
Set은 수학에서의 집합과 같이 순서가 없고, 중복을 허용하지 않는다.
Map은 Key, Value를 쌍으로 가지는 데이터의 집합이다. 순서가 없으며, key는 유일해야 하고 Value는 중복을 허용한다.

컬렉션 프레임워크의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있다. 또한 그들의 이름에는 구현한 인터페이스의 이름이 들어가 있어 특징을 쉽게 알 수 있도록 되어있다.

그러나 Vector, Stack, Hashtable, Properties 같은 클래스들은 컬렉션 프레임워크가 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임 워크의 명명법을 따르지 않는다. Vector와 Hashtable 같은 것은 호환을 위해 설계를 변경해서 남겨두었지만 가능하면 새로 추가된 ArrayList와 HashMap을 사용하는 것이 좋다.

위 그림은 Vector의 상속계층도 변화이며 왼쪽이 JDK1.2이전, 오른쪽이 JDK1.2 이후부터이다.

Collection 인터페이스

List와 Set의 조상인 Collection 인터페이스는 컬렉션 클래스에 저장된 데이터를 읽고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의하고 있다.

List 인터페이스

List 인터페이스는 Collection을 상속받았으며, 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다. List의 상속계층도는 다음과 같다.

Set 인터페이스

Set 인터페이스는 중복을 허용하지 않고, 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다. Set의 상속계층도는 다음과 같다.

Map 인터페이스

Map 인터페이스는 key와 value를 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는데 사용된다. Map의 상속계층도는 다음과 같다.

Map.Entry 인터페이스

Map.Entry 인터페이스는 Map의 내부 인터페이스이다. Map에 저장되는 key-value쌍을 다루기 위해 내부적으로 Entry 인터페이스를 정의해놓았다. 이것은 객체지향적으로 설계하도록 유도하기 위한 것으로 Map 인터페이스를 구현하는 클래스에서는 Map.Entry 인터페이스도 함께 구현해야한다.

public interface Map {
    ...
    public static interface Entry {
        Object getKey();
        Object getValue();
        ...
    }
    ...
}

ArrayList

ArrayList는 List를 구현한 것으로 데이터의 저장순서가 유지되고 중복을 허용한다. 또 기존의 Vector를 개선한 것으로 Vector의 구현원리와 기능적인 측면에서 동일하다고 할 수 있다.

ArrayList는 Object 배열을 이용해서 데이터를 순차적으로 저장한다. 만약 배열에 더 이상 저장할 공간이 없으면, 새로운 큰 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 뒤에 저장한다.

또 Object 배열을 이용하기 때문에, 모든 종류의 객체를 담을 수 있다.

import java.util.*;

class ArrayListEx1{
	public static void main(String[] args) {
		ArrayList list1 = new ArrayList(10);
		list1.add(new Integer(5));
		list1.add(new Integer(4));
		list1.add(new Integer(2));
		list1.add(new Integer(0));
		list1.add(new Integer(1));
		list1.add(new Integer(3));

		ArrayList list2 = new ArrayList(list1.subList(1,4)); 
		print(list1, list2);

		Collections.sort(list1);	// list1과 list2를 정렬한다.
		Collections.sort(list2);	// Collections.sort(List l)
		print(list1, list2);

		System.out.println("list1.containsAll(list2):" + list1.containsAll(list2));

		list2.add("B");
		list2.add("C");
		list2.add(3, "A");
		print(list1, list2);

		list2.set(3, "AA");
		print(list1, list2);
		
		// list1에서 list2와 겹치는 부분만 남기고 나머지는 삭제한다.
		System.out.println("list1.retainAll(list2):" + list1.retainAll(list2));	
		print(list1, list2);
		
		//  list2에서 list1에 포함된 객체들을 삭제한다.
		for(int i= list2.size()-1; i >= 0; i--) {
			if(list1.contains(list2.get(i)))
				list2.remove(i);
		}
		print(list1, list2);
	} // main의 끝

	static void print(ArrayList list1, ArrayList list2) {
		System.out.println("list1:"+list1);
		System.out.println("list2:"+list2);
		System.out.println();		
	}
} // class

list1:[5, 4, 2, 0, 1, 3]
list2:[4, 2, 0]

list1:[0, 1, 2, 3, 4, 5]
list2:[0, 2, 4]

list1.containsAll(list2) :true
list1:[0, 1, 2, 3, 4, 5]
list2:[0, 2, 4, A, B, C]

list1:[0, 1, 2, 3, 4, 5]
list2:[0, 2, 4, AA, B, C]

list1.retainAll(list2) :true
list1:[0, 2, 4]
list2:[0, 2, 4, AA, B, C]

list1:[0, 2, 4]
list2:[AA, B, C]

ArrayList의 메서드는 아래 링크에서 모두 볼 수 있다.

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayList.html

만약, size가 capacity를 넘긴다면, 배열의 추가 확장이 필요할 것이다. Vector는 capacity가 부족할 경우 기존의 크기보다 2배의 크기로 증가시킨다. 이때, 기존의 인스턴스를 활용하는 것이 아니라 새로운 배열을 만들어서 그곳에 기존 데이터들을 복사하여 옮긴다.

이와 같이, 용량을 변경해야할때는 새로운 배열을 생성한 후 기존의 배열의 데이터를 전부 복사해야하기 때문에 효율이 떨어진다. 따라서 처음에 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋다.

LinkedList

배열은 두 가지 단점을 가지고 있다. 크기를 변경할 수 없고, 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다는 것이다. 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 중간에 데이터를 추가하거나 삭제하려면 다른 데이터들을 복사해서 이동시켜야 한다.

이를 보완하기 위해 LinkedList가 고안되었다. 단방향, 양방향, 원형 여러가지가 있지만, 자바에서 LinkedList는 양방향이다.

LinkedList는 하나의 노드에 값이 들어있고, 이전, 다음 노드의 주소를 참조한다.

class Node {
    Node next;
    Node previous;
    Object obj;
}

LinkedList 역시 List 인터페이스를 구현했기 때문에 ArrayList가 제공하는 메서드의 종류와 기능은 거의 같다.

LinkedList의 메서드는 아래 링크에서 모두 볼 수 있다.

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html

ArrayList vs LinkedList

그렇다면 두 자료형중 어느 것을 선택해야할까? 각각 장단점이 존재한다.

순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다. ArrayList의 capacity가 충분하다는 가정하에, 순차적으로 추가하고 삭제하는 경우에는 값만 넣어주고, 값만 null로 바꿔주면 되기 때문에 이것저것 세팅해야하는 LinkedList보다 빠르다.

중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다. 중간 요소를 추가 또는 삭제하는 경우에는 LinkedList는 각 요소간의 연결만 변경해주면 되므로 처리속도가 상당히 빠르다. 반면 ArrayList는 각 요소들을 재배치해야하기 때문에 처리속도가 늦다.

추가로 ArrayList는 연속되어있는 메모리 구조이기 때문에 원하는 index에 저장된 값을 바로 읽어올 수 있지만, LinkedList는 각 요소들이 불연속적으로 연결되어 있어 처음부터 n번째까지 차례대로 따라가야 원하는 값을 얻을 수 있다. 그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어오는 시간이 길어진다는 단점이 있다.

정리하자면 다음과 같다.

ArrayList: 읽기가 빠르고, 비순차적인 추가/삭제는 느리다. (순차적인 추가/삭제는 빠름)
LinkedList: 읽기가 느리고, 추가/삭제가 빠르다. (데이터가 많을수록 더 느려짐)

꼭 둘 중 하나만 써야하는게 아니라면, 두 클래스를 조합해서 장점만 취하는 방법도 있다. 각 클래스는 서로 변환하는 생성자를 제공하므로 그것을 이용하면 된다.

예를 들어, 처음에 작업하기 전 데이터를 저장할 때는 ArrayList를 이용하고, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하는 경우이다.

Stack과 Queue

Stack은 LIFO구조, Queue는 보통 FIFO구조를 따른다.

Stack은 컬렉션 프레임워크 이전부터 존재했으므로 Vector를 상속받아 구현하였다. Stack은 수식계산, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로 같은 곳에서 사용한다.

Stack의 메서드는 아래 링크에서 모두 볼 수 있다.

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Stack.html

자바에서 Queue는 별도의 클래스를 제공하지 않고 있으며, 대신 Queue 인터페이스를 구현한 클래스들이 몇 가지 존재한다.

아래 링크에서 인터페이스와, Queue를 구현한 클래스들을 볼 수 있다.

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html

Queue를 구현한 것중에 LinkedList가 있으므로 다음과 같이 선언하여 사용하면된다.

Queue q = new LinkedList();

Queue는 최근 사용문서, 버퍼 등에서 사용한다.

PriorityQueue, Deque

PriorityQueue는 Queue 인터페이스의 구현체중 하나로 힙 자료구조를 이용하여 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼낸다. 또한 null은 저장할 수 없다.

PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙으로 저장한다.

자세한 메서드는 아래 링크에서 볼 수 있다.

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

Deque는 Queue의 변형으로 양쪽 끝에 추가/삭제가 가능하다. Deque의 조상은 Queue이며 구현체로는 ArrayDeque와 LinkedList 등이 있다.

Iterator

컬렉션 프레임워크에서는 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화하였다. 컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator 인터페이스를 정의하고, Collection 인터페이스에는 Iterator(Iterator를 구현한 클래스의 인스턴스)를 반환하는 iterator()를 정의하고 있다.

pulbic interface Iterator {
    boolean hasNext();
    Object next();
    void remove();
}

public interface Collection {
    ...
    public Iterator iterator();
    ...
}

iterator()는 Collection 인터페이스에 정의된 메서드로 이를 상속하는 List와 Set에도 포함되어있다. List나 Set 인터페이스를 구현하는 컬렉션은 iterator()가 각 컬렉션의 특징에 알맞게 작성되어 있다. 컬렉션 클래스에 대해 iterator()를 호출하여 Iterator를 얻은 다음, 반복문을 통해 컬렉션 클래스의 요소들을 읽어 올 수 있다.

Collection c = new ArrayList();
Iterator it = c.iterator();

while(it.haxNext()) {
    System.out.println(it.next());
}

여기서 참조 변수가 ArrayList가 아니라 Collection인데, Collection에 없고 ArrayList에만 있는 메서드를 사용하는게 아니라면 Collection 타입의 참조변수로 선언하는게 좋다. 왜냐하면 만일 ArrayList가 아닌 LinkedList 같은 클래스로 바꿔야할 경우 선언문 하나만 변경하면 나머지 코드는 검토하지 않아도 되지만, ArrayList로 선언했을 경우에는 Collection에 정의되지 않은 메서드를 호출했을 수도 있기 때문에 나머지 코드를 검토해야하기 때문이다.

Map의 경우에는 keySet()이나 entrySet() 같은 메서드를 이용하여 키와 값을 각각 따로 Set의 형태로 얻어온 다음에 iteraotr()를 호출해야 Iterator를 얻어 사용할 수 있다.

ListIterator와 Enumeration

Enumeration은 컬렉션 프레임워크가 만들어지기 이전에 사용하던 것으로 Iterator의 구버전이다. 되도록이면 사용하지말고 Iterator를 사용해야한다.

ListIterator는 Iterator를 상속받아서 기능을 추가한 것으로, 컬렉션의 요소에 접근할 때 Iterator는 단방향으로만 이동할 수 있는 데 반해 ListIterator는 양방향으로의 이동이 가능하다. 다만 ArrayList나 LinkedList와 같이 List 인터페이스를 구현한 컬렉션에서만 사용할 수 있다.

import java.util.*;

class ListIteratorEx1 {
	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		list.add("5");

		ListIterator it = list.listIterator();

		while(it.hasNext()) {
			System.out.print(it.next()); // 순방향으로 진행하면서 읽어온다.
		}
		System.out.println();

		while(it.hasPrevious()) {
			System.out.print(it.previous()); // 역방향으로 진행하면서 읽어온다.
		}
		System.out.println();
	}
}