Written by xi-jjun
on 

JAVA - Collection Frameworks2

Java

Java 공부를 정리 tag


JDK 8 Collections: Java docs를 공부하며 정리하는 글입니다.


지난 시간까지 Collection Interfaces에 대해 알아봤다. 이제 각각의 interface들을 알아볼 것이다


Set Interface

중복 element를 허락하지 않는 Collection.


Examples

Collection<Type> noDups = new HashSet<Type>(c);

Collection c가 있다고 가정하자. c에서 중복을 없애고 싶다면 위와 같은 코드를 쓰면 된다. 그리고 Collection interfaces들의 모든 constructor들은 Collection type를 parameter로 받기 때문에 우와 같은 코드가 가능하다.


Set<String> set = people.stream()
  .map(Person::getName)
  .collect(Collectors.toCollection(TreeSet::new));

Java 8 이후의 버전에서는 위와 같이 TreeSet으로 set instance를 stream으로 가져와서 초기화해줄 수 있다.


Set Interface Basic Operations

Set에 관한 테스트 코드를 작성해봤다. 위 method들을 다 사용한건 아니고 궁금한 것 위주로 사용했다.


Set Interface Bulk Operations

bulk operation은 Set에 적합하다. s1과 s2를 Set이라고 가정하자. 다음과 같은 동작을 할 수 있다고 한다.

bulk operation code를 작성해봤다. (그냥 테스트 겸으로 어떤 느낌인지 알기 위해서 간단하게 작성한 것이다.)

다른 예시들도 있었는데 인상깊었던게 있어서 가져와봤다.

Set<Type> symmetricDiff = new HashSet<Type>(s1);
symmetricDiff.addAll(s2); // symmetricDiff = s1 ∪ s2
Set<Type> tmp = new HashSet<Type>(s1);
tmp.retainAll(s2); // tmp = s1 ∩ s2
symmetricDiff.removeAll(tmp); // symmetricDiff = symmetricDiff - tmp

s1, s2 둘 중 하나에는 무조건 포함되어 있지만, 동시에 2개의 집합에는 포함안되는 element들의 집합을 표현한 것이다.


Set Interface Array Operations

The array operations don’t do anything special for Sets beyond what they do for any other Collection.

Set에서 array operation은 특별한 동작을 하지 않는다고 한다.



List Interface

순서가 있는 Collection. 중복되는 element를 가질 수 있다.

List interface는 Collection으로 부터 상속받은 기능말고도 다음과 같은 기능도 추가된다.


왜 List를 쓸까

Set은 그래도 중복을 허용하지 않는다는 점에 있어서 기존에 있던(Collections Frameworks 이외의) 기능이 아니기에 쓰는 이유를 납득했다. 근데 List같은 경우는 배열이라는 객체가 존재하는데 굳이 만들어서 쓰는 이유가 뭔지 궁금했다.

int[] arr = new int[4];
arr = addItem(arr, 100);
...

public int[] addItem(int[] arr, int item) {
  int[] newArr = new int[5]; // array size++
  newArr = Arrays.copyOf(arr, arr.length);
  newArr[newArr.length - 1] = item;
  return newArr;
}

배열 arr에 데이터 하나를 추가해보려고 한다. 따라서 addItem()이라는 함수를 만들었다. 다음으로는 ArrayList에서 list에 데이터 하나를 추가해보려고 한다.

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

둘의 차이가 느껴지는가? 데이터 하나를 추가하기 위해 배열에서는 직접 함수를 만들어서 크기가 더 큰 배열 선언해서 원래 값 복사하고 마지막 추가할 데이터 추가해준다음 해당 배열 반환… 반면에 리스트에서는 너무나도 간단하게 Collection으로부터 상속받은 add() method를 써서 해결했다. 개발자가 저런 자잘자잘한 일보다 더 중요한 로직을 신경 쓸 수 있게 해주는게 Collection Frameworks이기 때문에 List를 쓰는 것이다.


Collection Operations

List의 동작은 Collection으로부터 상속받은 동작들이며 우리가 이전에 Collection interface를 공부하며 봤었던 기능이라 생각하면 된다고 한다.


Positional Access and Search Operations

positional access에는 기본적으로 get, set, add, remove 가 있다. 나머지에 대해서는 이미 Set에서 했었어서 알기 쉽지만 set이라는 method는 생소할 수 있다. 순서에 대한 정보를 가지는 List는 index로 접근이 가능하기에 ‘원하는 index에 element를 삽입’할 수 있는 기능인 set method가 있는 것이다.

// ArrayList.java
public boolean addAll(Collection<? extends E> c) // 리스트 끝 부터 Collection c의 모든 element 삽입
public boolean addAll(int index, Collection<? extends E> c) // 리스트의 index부터 Collection c의 모든 element 삽입

addAll method는 특정 index부터 다른 리스트를 추가할 수 있는 기능도 있다. 그리고 Collection c 에서 제공하는 iterator의 순서를 기준으로 리스트에 c의 element들이 삽입된다고 한다.


Arrays.asList

Arrays class에는 asList()라는 method가 있다. 잠깐 알아보고 가도록 하자.

// Arrays.java
...
public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
}


private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable {...}

ArrayList를 생성하여 반환하는 것 처럼 보이지만, List interface 구현체인 ArrayList가 아닌, Arrays 내에서 선언된 ArrayList를 반환하는 것이다.

The resulting List is not a general-purpose List implementation, because it doesn’t implement the (optional) add and remove operations.

저번 포스팅에서 잠깐 언급했던 말인데, add, remove method가 Arrays의 ArrayList에는 구현되지 않았다. 따라서

List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
Iterator<Integer> iterator = numbers.iterator();

while (iterator.hasNext()) {
    // logic has remove method
    iterator.remove()
}

/* Exception in thread "main" java.lang.UnsupportedOperationException: remove
	 	at java.base/java.util.Iterator.remove(Iterator.java:102)
*/

Exception in thread "main" java.lang.UnsupportedOperationException: remove
	 	at java.base/java.util.Iterator.remove(Iterator.java:102)

위와 같은 코드는 오류가 발생하게 된다. new ArrayList(Arrays.asList(1, 2, 3, 4, 5))로 생성해주면 오류를 해결 할 수 있다.

마찬가지로 add method에서도 오류가 나타난다.

List<Integer> asList = Arrays.asList(1, 2, 3 ,4);
asList.add(3000);

Exception in thread "main" java.lang.UnsupportedOperationException
	at java.base/java.util.AbstractList.add(AbstractList.java:153)
	at java.base/java.util.AbstractList.add(AbstractList.java:111)
	at javastudy.collectionframework.listInterface.ListTest.main(ListTest.java:85)

따라서 Arrays.asList는 배열을 List로 볼 수 있게 해주는 method이다. 그러나 그저 배열의 내용을 복사해주는 method가 아니라 리스트의 변경사항을 배열에 반영할 수 있고, 그 반대도 가능하다고 한다. 또한 배열의 크기는 바뀔 수가 없기 때문에 add, remove method가 구현되지 못한 것이다. 테스트 코드

The Arrays class has a static factory method called asList, which allows an array to be viewed as a List. This method does not copy the array. Changes in the List write through to the array and vice versa. The resulting List is not a general-purpose List implementation, because it doesn’t implement the (optional) add and remove operations: Arrays are not resizable.


Iterators

List의 iterator에 의해 반환된 Iterator는 리스트의 element를 적절한 순서로 반환하는 역할을 한다. 또한 List에서는 ListIterator라는 것을 제공하는데 양방향 탐색, 반복 도중의 수정, iterator의 현재 index위치도 얻을 수 있다.

// ArrayList.java
/* 
  Returns a list iterator over the elements in this list (in proper sequence), 
  starting at the specified position in the list.
*/
public ListIterator<E> listIterator(int index) 
...

/*
  Returns a list iterator over the elements in this list (in proper sequence).
*/
public ListIterator<E> listIterator()

2가지 종류의 ListIteratormethod를 제공하는데 index가 parameter로 있는 method는 특정 index를 시작으로 하는 list iterator를 반환한다.


Range-View Operation

range-view operation인 subList(int fromIndex, int toIndex)는 지정한 구간에 해당하는 리스트를 반환한다. view operation이라는 말 답게 어떤 리스트의 subList는 원래 리스트가 변경되면 그 변경사항이 동일하게 subList에도 반영된다.

System.out.println("=== subList modify Test ===");
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
List<Integer> subListOfList = list.subList(3, 7);
System.out.println("list = " + list);
System.out.println("subListOfList = " + subListOfList);
list.set(4, 1000); // 원래 리스트 변경
System.out.println(" << modify list's index 4th (5=>1000) >> ");
System.out.println("list = " + list);
System.out.println("subListOfList = " + subListOfList);
/**
 * === subList modify Test ===
 * list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 * subListOfList = [4, 5, 6, 7]
 *  << modify list's index 4th (5=>1000) >>
 * list = [1, 2, 3, 4, 1000, 6, 7, 8, 9, 10]
 * subListOfList = [4, 1000, 6, 7]
 */

다른 테스트 코드는 여기에 있으니 한번 봐도 좋을 것 같다.


왜 굳이 subList를 쓰는 것일까

처음에 굳이..? 라는 생각이 들었다.

for(int i = fromIndex; i < toIndex; i++) {
  ...
}

위같이 (아주 조금은 귀찮지만) 간단하게 subList를 흉내낼 수 있는데 왜 굳이 사용할까 라는 의문이었다. Java docs에서는 다음과 같이 말한다.

This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List.

전체 리스트에서 할 작업을 subList를 써서 할 수 있기에 우리가 위처럼 for를 직접 만들어가며 명시적으로 사용할 일을 없애준다고 한다… 아직까지 와닿지는 않지만 아래와 같은 활용 예시를 보여주고 있었다.

list.subList(1, 3).clear(); // list의 1번, 2번 index element 제거

int index = list.subList(5, 9).indexOf(Obj); // list의 5~9 사이의 element 중에 Obj에 해당하는 값이 있으면 해당 index 위치 반환

확실히 indexOf와 같은 method를 쓸 때에는 더 깔끔하고 간결한 코드가 나올 것 같다.

근데 위 예시를 보면… 과연 ‘subList를 수정하면 원본에 반영이 될까?’라는 생각이 들었다. 결과적으로는 반영이 된다. 왜일까?

// ArrayList.java
...
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList<>(this, fromIndex, toIndex);
}
...

ArrayList를 기준으로 설명하자면, 위와 같은 method가 존재한다. 따라서 우리는 List interface의 구현체인 ArrayList에서 subList라는 method를 호출할 수 있는 것이다. 하지만 위 method는 new SubList<>(...)를 반환하는 것을 볼 수 있다. 한번 따라가서 보도록 해보자.

// ArrayList.java
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList<>(this, fromIndex, toIndex);
}   
...
  
    private static class SubList<E> extends AbstractList<E> implements RandomAccess {
        private final ArrayList<E> root;
        private final SubList<E> parent;
        private final int offset;
        private int size;
      ...

ArrayList 안에 static class로 선언된 SubList class를 볼 수 있었다. 생성자를 또 찾아 볼 수 있는데 아래와 같다.

// constructor
public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
    this.root = root;
    this.parent = null;
    this.offset = fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = root.modCount;
}

그러니깐 어떤 흐름이냐면,

  1. List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> subList = list.subList(2, 5);

    먼저 list에서 subList 를 호출했다.

  2. // ArrayList.java
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList<>(this, fromIndex, toIndex);
}

    ArrayList의 subList method가 호출될 때 new SubList 로 다른 생성자를 반환한다. 이 때 생성자의 첫번째 parameter로 넘어간 값을 잘 보면, this 키워드가 있음을 알 수 있다.

  3. // SubList constructor in ArrayList.java
public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
    this.root = root;
    this.parent = null;
    this.offset = fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = root.modCount;
}

    ArrayList type으로 들어온 parameter는 아까 this 즉, 원래 list를 참조하는 위치가 그대로 들어온 것이다. 따라서 subList를 변경하면 원래 리스트에도 반영되는 것이다.


좋은거 알았는데 쓸 때는 조심!!

subList method로 생성된 리스트는 back up list에서 element의 추가 또는 제거의 작업이 발생하면 더이상 정의되지 않는다. 말이 이해가 잘 안갔는데 코드로 직접 보면서 어느 부분에서 오류가 나는지 보면 이해가 더 쉽다.

System.out.println("=== subList adding Test ===");
List<Integer> listA = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
List<Integer> subListA = listA.subList(3, 7);
System.out.println("listA = " + listA);
System.out.println("subListA = " + subListA);
listA.add(1000); // back up list 에 add 작업 진행. <= 에러 발생 원인 코드
System.out.println("listA = " + listA);
System.out.println("subListA = " + subListA); // 여기서 에러 발생!

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1445)
	at java.base/java.util.ArrayList$SubList.listIterator(ArrayList.java:1314)
	at java.base/java.util.AbstractList.listIterator(AbstractList.java:311)
	at java.base/java.util.ArrayList$SubList.iterator(ArrayList.java:1310)
	at java.base/java.util.AbstractCollection.toString(AbstractCollection.java:465)
	at java.base/java.lang.String.valueOf(String.java:2951)
	at javastudy.collectionframework.listInterface.SubListTest.main(SubListTest.java:78)

ConcurrentModificationException이 발생했음을 볼 수 있다. (set과 같은 작업은 에러가 발생하지 않는다.)

따라서 subList는 일시적인 작업에서 매우 추천된다고 한다.


List Algorithm

Collections class에 있는 대부분의 알고리즘은 List에 적용된다. 이 알고리즘들을 잘 사용하면 더 쉽게 리스트를 조작할 수 있다.

간단하게 몇가지는 테스트를 진행해봤었다. 여기에서 볼 수 있다.

다음 포스팅에서는 Queue에 대해서 알아보도록 하자.


Rerference

Java JDK 8 docs - Collections

Java JDK 8 docs - Set Interface

Java JDK 8 docs - List Interface