The List Interface

The List Interface

List 는 정렬된 Collection이다. (가끔 sequence라고도 한다.). 리스트는 중복되는 엘리먼트를 포함한다. 정렬된 Collection이다. 리스트는 많은 중복된 엘리먼트들을 가지고 있다. Collection으로 부터 상속받은 오퍼레이션이 추가되어 있으며, List인터페이스는 다음과 같은 오퍼레이션이 있다.

• Positional access — 리스트에서 인덱스 수치를 통해서 접근이 가능하다.
• Search — 특정 객체를 리스트에서 Search를 수행하면 수치적인 위치를 반환한다.
• Iteration — 리스트의 내용을 순차적으로 접근할 수있도록 Iterator에서 상속 받은 기능이다.
• Range-view — 다양한 범위 처리를 수행한다.

List 인터페이스는 다음과 같다.

public interface List<E> extends Collection<E> {

    // Positional access

    E get(int index);

    E set(int index, E element);    //optional

    boolean add(E element);         //optional

    void add(int index, E element); //optional

    E remove(int index);            //optional

    boolean addAll(int index,

        Collection<? extends E> c); //optional



    // Search

    int indexOf(Object o);

    int lastIndexOf(Object o);



    // Iteration

    ListIterator<E> listIterator();

    ListIterator<E> listIterator(int index);



    // Range-view

    List<E> subList(int from, int to);

}

Java는 2개의 범용 List를 구현하고 있다. 하나는 ArrayList이고 좋은 성능을 발휘한다. 다른 하나는  LinkedList이며 특정 환경에서 낳은 속도를 낸다. 또한 Vector은 List를 개량해서 구현한 자료구조이다.

Vector과 비교

만약 Vector를 이용한다면 이미 List의 일반적인 기능을 이용하고 있는 것이다. (물론 List는 인터페이스이고 Vector은 concrete 구현체이다.) List는 Vector에 있는 몇가지 고정된 하위 API를 지정하고 있다.
Vector 오퍼레이션을 이용할때 쓰는 elementAt과 setElementAt와 같은 것은 공통적으로 이용이 가능한 기능으로 좀더 짧은 이름으로 구현하고 있다. 만약 배열에서 []를 이용하여 처리하는 것을 2가지 관점으로 비교해 본다면, List는 Vector보다 좀더 짧아진 이름을 지원한다. 다음 문장을 보며 확인해 보자.

a[i] = a[j].times(a[k]);

The Vector equivalent is:

v.setElementAt(v.elementAt(j).times(v.elementAt(k)), i);

The List equivalent is:

v.set(i, v.get(j).times(v.get(k)));

아마도 벌써 set메소드를 눈치챘을 것이다. 이것은 Vector의 setElementAt 메소드를 대체하는 것으로 배열의 인덱스를 이용하여 접근 하는 것과 동일한 처리를 수행한다. 다음 대입 문을 확인해 보자.

gift[5] = "golden rings";

The Vector equivalent is:

gift.setElementAt("golden rings", 5);

The List equivalent is:

gift.set(5, "golden rings");

여전히 고개를 끄덕일 것이다. add(int, E) 이 메소드는 insertElementAt(Object, int)의 벡터 메소드를 대체하고 있다.

벡터에서는 3가지 범위 처리 기능이 있다. (indexOf, lastIndexOf, setSize) 이것은 하나의 범위 처리 연산인 (subList)를 이용하여 처리할 수 있으며, 좀더 강력하고, 일관성이 있는 처리가 될 것이다.

Collection 조작

Collection으로 부터 처리하고자 하는 대부분의 메소드를 상속받았다. 이것들을 보면 이미 눈에 익은 그런 내용들일 것이다. 만약 Collection과 유사하지 않다면, 지금 The Collection Interface 섹션을 배워볼 좋은 기회일 것이다. remove 처리는 항상 첫번째 발생하는 특정 엘리먼트를 제거한다. add와 addAll 처리는 항상 새로운 엘리먼트를 리스트의 마지막에 추가한다. 그러므로 다음 구문을 보면 리스트에 다른 리스트를 추가하는 것임을 알 수 있다.

list1.addAll(list2);

이것은 기존 리스트를 깨지 않고 처리하는 구문이다. List는 첫번째 리스트에 추가된 두번째 리스트의 값으로 구성되어 있다.

List<Type> list3 = new ArrayList<Type>(list1);

list3.addAll(list2);

이러한 문장들을 보면서 ArrayList의 표준 변환의 이점을 확인할 수 있을 것이다.

Set인터페이스처럼, List는 equals와 hashCode 메소드를 매우 강력하게 처리하고 있다. 두개의 List 객체는 그것들의 구현체 없이도 매우 논리적인 비교를 수행하고 있다. 두개의 List 객체는 서로 동일한 엘리먼트들이 동일한 순서로 저장되어 있다면 같은 것으로 처리할 것이다.

위치 접근과 Search 처리

가장 기본적인 position 접근 처리는 (get, set, add, remove)가 있으며 이것은 벡터에 있는 (elementAt, setElementAt, removeElementAt)보다 더 짧은 이름을 가지고 있다.
set과 remove 처리는 제거 하기 전에 가지고 있던 값을 반환환다. Vector에서는 (setElementAt과 removeElementAt)은 void 연산이며 아무것도 반환하지 않는다. search 처리의 경우 indexOf와 lastIndexOf가, Vector과 동일한 처릴를 수행한다.

addAll 연산은 특정 위치에서 부터 해당 엘리먼트들을 추가하는 처리를 수행한다. 엘리먼트들이 입력되면 특정 컬렉션을 반복적으로 저장하게 되는 것이다. 이것은 Collection의 addAll 처리에서 위치를 통해서 연속적으로 값을 입력하는 것이다.

여기 있는 메소드는 List에 2개의 인덱스에 존재하는 값을 서로 교환하는 작업을 수행한다.

public static <E> void swap(List<E> a, int i, int j) {

    E tmp = a.get(i);

    a.set(i, a.get(j));

    a.set(j, tmp);

}

물론 기본적인 swap와는 크게 달라 보인다. 이것은 폴리몰픽 알고리즘이다. 이것은 리스트에 존재하는 두개의 엘리먼트를 교환하는 것으로 구현된 타입에 대해서 신경쓰지 않는다. 다른 폴리몰픽 알고리즘은 다음과 같은 구문이 있다.

public static void shuffle(List<?> list, Random rnd) {

    for (int i = list.size(); i > 1; i--)

        swap(list, i - 1, rnd.nextInt(i));

}

이 알고리즘은 Collections클래스에 포함된 내용을 랜덤하게 교환을 하는 일을 처리한다. 이것은 매우 신기하다. 이것은 현재 포지션을 증가해 가면서, 현재 포지션의 값과, 랜덤한 위치값에 있는 내용을 교환한다. 대부분의 shuffling과는 다르다. 이것은 모든 엘리먼트를 공정하게 섞어 주며, list.size() - 1까지 교체하므로 빠른 처리를 수행한다. 다음은 이것을 이용하여 전달된 값들을 섞어주는 역할을 수행한다.

import java.util.*;



public class Shuffle {

    public static void main(String[] args) {

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

        for (String a : args)

            list.add(a);

        Collections.shuffle(list, new Random());

        System.out.println(list);

    }

}

사실 프로그램은 짧고 빠르게 만들 수 있다. Arrays클래스는 asList라고 하는 정적 팩토리 메소드를 이용하고 있다. 이것은 배열을 List로 보이게 하는 것이다. 이 메소드는 배열의 내용을 복사하지 않는다. 단지 배열을 List로 변환하는 작업을 할 뿐이다. 결과 리스트는 범용 리스트의 구현체가 아니다. 외냐하면 이것은 add와 remove 처리를 구현하고 있지 않기 때문이다. Arrays는 그 크기를 변경할 수 없다. Arrays.asList의 이점과 shuffle의 버젼을 제공 받을 수 있다. tiny program을 이전 소스와 비교해 보라.

import java.util.*;



public class Shuffle {

    public static void main(String[] args) {

        List<String> list = Arrays.asList(args);

        Collections.shuffle(list);

        System.out.println(list);

    }

}

Iterators

기대하는 것과 같이 Iterator은 List의 iterator 처리를 담당하는 Iterator 객체를 반환하고, 순차적으로 반복을 수행하도록 한다. List는 또한 더 풍부한 iterator을 제공해 주는데 ListIterator이 그것이다. 이것은 리스트의 내용을 양방향으로 탐색할 수있다. 또한 리스트를 반복하면서 변경도 가능하며, 현재 위치를 획득할 수 있다. ListIterator다음과 같은 인터페이스를 가지고 있다.

public interface ListIterator<E> extends Iterator<E> {

    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    void remove(); //optional

    void set(E e); //optional

    void add(E e); //optional

}

ListIterator은 Iterator로 부터 3개의 기본적인 메소드를 상속 받았으며 (hasNext, next, remove)가 그것이다. 이것은 동일한 인터페이스를 제공한다. hasPrevious와 previous 처리는  hasNext와 next와 같이 순차적인 접근을 수행하도록 한다. 현재 엘리먼트가 위치한 곳을 커서라고 하면, previous는 커서를 이전으로 돌려놓는 것이다. next는 다음으로 가는 것이다.

여기에는 표준적인 역뱡향으로 이동하는 iterating작업을 볼 수 있다.

for (ListIterator<Type> it = list.listIterator(list.size());

     it.hasPrevious(); ) {

    Type t = it.previous();

    ...

}

listIterator 아규먼트를 확인해 보자. List 인터페이스는 2개의 형태로 listIterator 메소드를 가지고 있다. 리스트의 처음 위치에 포지션을 가지고 있는 listIterator과, 특정 위치를 지정한 listIterator을 반환하는 것 두가지이다. 인덱스 참조는 next를 처음 호출하는 것으로 현재 인덱스의 자료를 호출할 수 있고, previous의 경우 index-1의 자료를 반환하게 되는 것이다. 만약 list의 엘리먼트가 n개가 존재한다면 가질 수 있는 인덱스는 0 ~ n이된다.

직관적으로 말해서, 커서는 항상 2개의 엘리먼트 사이에 존재한다. 하나는 previous를 호출하는 것이고, 다른것은 next를 호출하는 위치에 존재하는 것이다. n+1이 가능한 인덱스라면 n+1의 갭은 엘리먼트 사이에서,
The n+1 valid index values correspond to the n+1 gaps between elements, from the gap before the first element to the gap after the last one.
다음 그림은 4개의 엘리먼트가 존재하는 리스트에서 가능한 커서의 위치를 보여준다.

5개의 가능한 커서 위치가 존재하며 이것은 0 ~ 4가 된다. 각 화살표는 커서가 존재하는 포지션을 나타낸다

The five possible cursor positions.

next혹은 previous를 혼합해서 호출 할 수 있다. 그러나 주의해야 한다. 첫번째로 previous를 호출하고, next를 나중에 호출하면 현재와 같은 엘리먼트가 반환된다. 유사하게 next를 먼저 호출하고, previous를 호출하면 마지막에 호출한 previouse는 동일한 엘리먼트가 반환된다.

It should come as no surprise that the nextIndex method returns the index of the element that would be returned by a subsequent call to next, and previousIndex returns the index of the element that would be returned by a subsequent call to previous. These calls are typically used either to report the position where something was found or to record the position of the ListIterator so that another ListIterator with identical position can be created.

nextIndex는 항상 previousIndex에 의해서 반환되는 인덱스 보다 크다는것은 당연할 것이다. 이것은 2개의 경계에 대한 작업이며, previousIndex를 호출하는 경우 커서가 초기 엘리먼트 위치에서 있다면 -1을 반환할 것이고, nextIndex라면 list.size()가 반환될 것이다. 이것을 구체적으로 구현한다면 다음과 같이 List.indexOf가 만들어 질 것이다.

public int indexOf(E e) {

    for (ListIterator<E> it = listIterator(); it.hasNext(); )

        if (e == null ? it.next() == null : e.equals(it.next()))

            return it.previousIndex();

    return -1;  // Element not found

}

indexOf메소드의 반환값이나. it.previousIndex()의 반환값이다. 둘다. list를 전 방향으로 탐색하는것에는 동일한다. 이러한 이유로 it.nextIndex()역시 예제와 같이 동일한 인덱스를 반환한다는 것에는 변함이 없다.

Iterator 인터페이스는 remove 처리를 제공한다. ListIterator에서는 제거한 엘리먼트의 값을 반환한다.
ListIterator 인터페이스는 2개의 추가 메소드를 제공하는데 set과 add가 그것이다. set메소드는 next 혹은 previous 의 결과값을 반환하고, 그 값을 덮어 쓰는 작업을 수핸한다. 다음은 폴리몰픽 알고리즘을 이용하여 set 메소드를 이용한 코드로, 특정 엘리먼트를 다른 값으로 변경하는 작업을 수행하는 작업을 한다.

public static <E> void replace(List<E> list, E val, E newVal) {

    for (ListIterator<E> it = list.listIterator(); it.hasNext(); )

        if (val == null ? it.next() == null : val.equals(it.next()))

            it.set(newVal);

}

add메소드는 새로운 엘리먼트를 현재 포지션에 추가를 수행한다. 이 메소드는 다음 폴리몰픽 알고리즘에서 표현하고 있다. 이것은 특정한 엘리먼트를 지정될 리스트에 추가하는 작업을 수행한다.

public static <E> void replace(List<E> list, E val,

                               List<? extends E> newVals) {

    for (ListIterator<E> it = list.listIterator(); it.hasNext(); ){

        if (val == null ? it.next() == null : val.equals(it.next())) {

            it.remove();

            for (E e : newVals)

                it.add(e);

        }

    }

}

Range-View Operation

range-view 오퍼레이션은 subList(int fromIndex, int toIndex)를 이용하여 구할수 있으며 이것은 부분 볌위의 List를 반환한다. fromIndex는 포함되고, toIndex는 포함되지 않는다. 이것은 반 개방 루프를 이용하여 처리된다.

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

    ...

}

view라는 용어가 함축하고 있는 것은 반환되는 List는 List에서 subList를 호출할때 백업된 값을 반환하는 것이다.
As the term view implies, the returned List is backed up by the List on which subList was called, so changes in the former are reflected in the latter.

이 메소드이용하여 제거 작업을 수행할때에는 명시적인 범위 처리를 필요로 한다. 즉, List의 전체 내용 대신에 subList를 전달하여 범위 처리를 수행하고자 할 경우 보통 이용되며, 다음 예는 List로 부터 특정 범위의 엘리먼트를 제거한다.

list.subList(fromIndex, toIndex).clear();

유사한 구문으로 범위내에 존재하는 엘리먼트를 검색할 수 있다.

int i = list.subList(fromIndex, toIndex).indexOf(o);

int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

이전 예에서 subList에 존재하는 인덱스를 반환한 경우에는, 그것이  List에 있는 인덱스가 아님을 주의해야 한다.

폴리몰픽 알고리즘을 이용하여 replace와 shuffle 예제를 작성할경우, subList의 반환으로 그 작업을 할 수 있다.

폴리몰픽 알고리즘을 subList를 이용하여 구현하는 예이다. 이것은 새로운 List(hand)를 반환한다. 여기에는 특정 List(deck)의 엘리먼트가 존재한다. 엘리먼트는 deck로 부터 제거된 엘리먼트들을 반환하는 작업을 수행한다.

public static <E> List<E> dealHand(List<E> deck, int n) {

    int deckSize = deck.size();

    List<E> handView = deck.subList(deckSize - n, deckSize);

    List<E> hand = new ArrayList<E>(handView);

    handView.clear();

    return hand;

}

이것은 deck의 끝에서부터 hand를 제거하는 작업을 수행한다. 많은 일반적인 리스트에서는 ArrayList와 같은 대표적인 리스트에서는 리스트의 끝에서 부터 제거하는것을 처음부터 제거하는것보다 선호한다. (처음부터 제거하면 인덱스 문제가 발생되어 프로그램이 복잡해지므로)

다음은 a program dealHand 메소드를 이용하고 Collections.shuffle를 함께 이용하여 52개의 카드를 석는 작업을 수행한다. 프로그램은 2개의 커맨드라인 인수를 받는데 첫번째는 deal할 숫자이고, 2번째 인수는 각 핸드에 존재하는 카드의 개수를 나타낸다.

import java.util.*;



class Deal {

    public static void main(String[] args) {

        int numHands = Integer.parseInt(args[0]);

        int cardsPerHand = Integer.parseInt(args[1]);



        // Make a normal 52-card deck.

        String[] suit = new String[]

            {"spades", "hearts", "diamonds", "clubs"};

        String[] rank = new String[]

            {"ace","2","3","4","5","6","7","8",

             "9","10","jack","queen","king"};

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

        for (int i = 0; i < suit.length; i++)

            for (int j = 0; j < rank.length; j++)

                deck.add(rank[j] + " of " + suit[i]);



        Collections.shuffle(deck);



        for (int i=0; i < numHands; i++)

            System.out.println(dealHand(deck, cardsPerHand));

    }

}

Running the program produces the following output.

% java Deal 4 5



[8 of hearts, jack of spades, 3 of spades, 4 of spades,

    king of diamonds]

[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,

    queen of hearts]

[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,

    9 of clubs]

[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,

    ace of hearts]

subList 처리가 매우 강력하지만 사용할때에는 주의해야할 점이 있다. List의 의미를 볼때 subList로 반환된 값은, 과거 리스트에서 추가되거나, 반환되는 경우에 그 값을 명쾨하게 정의할 수 없다는 것이다. 그러므로 subList에 의해서 반환되는 리스트는 중간 단계의 객체라는 것이다. 더욱 오래 subList의 인스턴스를 이용하고자 한다면,  기존의 리스트를 직접 변경하거나, 다른 subList를 이용하여 그 작업을 처리해야 한다는 것이다.

List Algorithms

대부분 폴리몰픽 알고리즘은 특별하게 List에 구현되어 있다. 모든 이러한 알고리즘은 list를 매우 쉽게 운용할 수 있도록 해준다. 여기에는 사용된 알고리즘 리스트가 존재한다. 이것은 Algorithms section 을 참조하면 될 것이다.

• sort — sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)
• shuffle — randomly permutes the elements in a List.
• reverse — reverses the order of the elements in a List.
• rotate — rotates all the elements in a List by a specified distance.
• swap — swaps the elements at specified positions in a List.
• replaceAll — replaces all occurrences of one specified value with another.
• fill — overwrites every element in a List with the specified value.
• copy — copies the source List into the destination List.
• binarySearch — searches for an element in an ordered List using the binary search algorithm.
• indexOfSubList — returns the index of the first sublist of one List that is equal to another.
• lastIndexOfSubList — returns the index of the last sublist of one List that is equal to another.