6장 리스트와 반복자

6장 리스트와 반복자

2023. 12. 22. 19:50ㆍ프로그래밍 공부/Data Structure

6.1 배열 리스트

리스트(list) 또는 수열(시퀀스, sequence): 선형 순서로 저장된 n개 요소의 집합 S

이 때 집합 S 속 요소들을 첫 번째, 두 번째, 세 번째 등등이라고 부를 수 있다.

S 속의 e 앞에 오는 S의 요소들의 수와 같은

[0,n - 1] 범위의 정수를 사용하여

S 속의 각 요소 e를 고유하게 나타낼 수 있다.

S 속의 요소 e의 인덱스(index) = S 속의 e 앞에 있는 요소들의 수

S 속의 첫 번째 요소: 인덱스 0

마지막 요소: 인덱스 n - 1

S의 요소의 인덱스가 i이면,

이전 요소의 (존재하는 경우)의 인덱스: i - 1

다음 요소 (존재하는 경우)는 인덱스: i + 1

인덱스의 개념은 정의되는 리스트의 요소의 순위와 관련있다.

순위(rank): 인덱스 + 1

첫 번째 요소: 랭크 1

두 번째 요소: 랭크 2

배열 리스트(array list)(또는 이전 용어로는 벡터(vector)):

인덱스를 통해 요소에 접근할 수 있도록 지원하는 수열

인덱스 정의는

배열이 자바 및 다른 프로그래밍 언어(예: C 및 C++)에서

색인화되는 방식과 더 일치하므로

배열 리스트에서 요소가 저장된 위치를 "순위"가 아닌 "인덱스"로 표시할 것이다.

(비록 "i"라는 문자가 for문의 카운터로 사용되는 경우

이 인덱스를 표시하기 위해 r을 사용할 수 있지만).

이 인덱스 개념은

리스트에 새 요소를 삽입할 위치 또는

이전 요소를 제거할 위치를 지정하는 데 사용할 수 있으므로

단순하지만 강력한 개념이다.

6.1.1 배열 리스트 추상 데이터 타입

배열 리스트 S는 ADT로서 다음과 같은 메소드를 갖는다

(표준 size() 및 is Empty() 메소드 외):

get(i): 인덱스 i로 S의 요소를 반환한다.

i < 0 또는 i > size() - 1인 경우 오류 조건이 발생한다.

set(i, e): e로 대체하고 인덱스 i에서 요소를 반환한다.

i < 0 또는 i > size() - 1인 경우 오류 조건이 발생한다.

add(i, e): 인덱스 i를 가지려면 S에 새 요소 e를 삽입한다.

i < 0 또는 i > size()이면 오류 조건이 발생한다.

remove(i): 인덱스 i의 S에서 요소를 제거한다.

i < 0 또는 i > size() - 1인 경우 오류 조건이 발생한다.

그것이 (매우 자연스러운) 가능성 중 하나이기는 하지만,

우리는 배열 리스트를 구현하기 위해 배열을 사용해야 한다고 주장하지 않는다.

색인 정의는 요소가 배열에 저장된 "장소"를 참조하는 방법을 제공하므로,

그 배열이 정확히 구현되는지 걱정할 필요가 없다.

그러나 다음 예제에서 보여주듯이,

요소의 색인은 배열이 업데이트될 때마다 바뀔 수 있다.

예제 6.1: 처음에 비어 있는 배열 리스트 S에 대한 몇 가지 연산을 다음과 같이 보여준다.

연산	출력	S
add(0, 7)	-	(7)
add(0, 4)	-	(4, 7)
get(1)	7	(4, 7)
add(2, 2)	-	(4, 7, 2)
get(3)	"error"	(4, 7, 2)
remove(1)	7	(4, 2)
add(1, 5)	-	(4, 5, 2)
add(1, 3)	-	(4, 3, 5, 2)
add(4, 9)	-	(4, 3, 5, 2, 9)
get(2)	5	(4, 3, 5, 2, 9)
set(3, 8)	2	(4, 3, 5, 8, 9)

6.1.2 어댑터 패턴

클래스는 종종 다른 클래스와 유사한 기능을 제공하기 위해 작성된다.

어댑터 디자인 패턴(adapter design pattern):

기존 클래스의 메소드가 관련된 다른 클래스 또는 인터페이스의 메소드와 일치하도록

기존 클래스를 수정하려는 모든 컨텍스트에 적용된다.

어댑터 패턴을 적용하는 한 가지 일반적인 방법은

이전 클래스의 인스턴스를 숨김 필드로 포함하도록 새 클래스를 정의하고

이 숨김 인스턴스 변수의 메소드를 사용하여 새 클래스의 각 메소드를 구현하는 것이다.

어댑터 패턴을 적용한 결과 이전의 클래스와 거의 동일한 기능을 수행하면서도

보다 편리한 방식으로 클래스를 새롭게 만들어낸 것이다.

배열 리스트 ADT에 대한 논의와 관련하여,

이 ADT는 표 6.1에 표시된 바와 같이

데크 ADT에 대한 어댑터 클래스를 정의하기에 충분하다(연습 C-6.8 참조)

표 6.1: 배열 리스트를 통한 데크 실현

데크 메소드	배열 리스트 메소드를 통한 실현
size(), isEmpty()	size(), isEmpty()
getFirst()	get(0)
getLast()	get(size() -1)
addFirst(e)	add(0,e)
addLast(e)	add(size(),e)
removeFirst()	remove(0)
removeLast()	remove(size() - 1)

6.1.3 간단한 배열 기반 구현

배열 리스트 ADT를 구현하기 위한 명백한 선택은 배열 A를 사용하는 것이다.

여기서 A[i]는 인덱스 i가 있는 요소를 저장한다.

배열 A의 크기 N을 충분히 크게 선택하고,

인스턴스 변수의 요소의 수, n < N을 유지한다.

배열 리스트 ADT의 이 구현의 세부 사항은 간단하다.

예를 들어, get(i) 연산을 구현하려면 A[i]를 반환한다.

add(i, e)와 remove(i) 메소드의 구현은 코드 조각 6.1에 나와 있다.

이 구현의 중요한 부분(그리고 시간이 많이 걸리는 부분)은

점유된 셀을 배열에 연속적으로 유지하기 위해 요소를 위 또는 아래로 이동하는 것이다.

이러한 이동 연산은 리스트 인덱스가 i인 요소를

배열 A에 항상 저장하는 규칙을 유지하는 데 필요하다.

(그림 6.1 및 연습 R-6.12 참조)

코드 조각 6.1:

배열 리스트 ADT의 배열 구현에서

(i, e)와 (i)를 추가하는 메소드와 제거하는 메소드이다.

배열 리스트의 요소의 수를 저장하는 인스턴스 변수를 n으로 표시한다.

Algorithm add(i, e):

for j = n - 1, n - 2, ..., i do

A[j + 1] ← A[j] {make room for the new element}

A[i] ← e

n ← n + 1

Algorithm remove(i):

e ← A[i] { e is a temporary variable}

for j = i, i + 1, ..., n - 2 do

A[j] ← A[j + 1] {fill in for the removed element}

n ← n - 1

return e

그림 6.1:

n개의 요소를 저장하는 배열 리스트 S의 배열 기반 구현:

(a) 인덱스 i

(b)에서 삽입을 위해 쉬프트 업(shift up),

인덱스 i에서 제거를 위해 쉬프트 다운(shift down)

단순 배열 기반 구현의 성능

표 6.2는 배열을 통해 n개의 요소가 구현된 배열 리스트의 메소드 중

최악의 실행 시간을 보여준다.

메소드 isEmpty, size, get 및 set이 명확하게 O(1) 시간에 실행되지만

삽입 및 제거 메소드는 이보다 훨씬 더 오래 걸릴 수 있다.

특히 add(i, e)는 O(n) 시간에 실행된다.

실제로 이 작업의 최악의 경우는 i = 0일 때 발생한다.

최악의 경우(i = 0), n - 1 요소를 뒤로 이동해야 하기 때문에

O(n) 시간에 실행되는 메소드 remove(i)에도 유사한 인수가 적용된다.

실제로 각 가능한 인덱스가

동일하게 이러한 작업의 인수로 전달될 가능성이 있다고 가정하면

평균 n/2 요소를 이동해야 하기 때문에 평균 실행 시간은 O(n)이다.

표 6.2: 배열로 구현된 n개의 요소를 가진 배열 리스트의 성능.

공간 사용량은 O(N)이며, N은 배열의 크기이다.

메소드	시간
size()	O(1)
isEmpty()	O(1)
get(i)	O(1)
set(i, e)	O(1)
add(i, e)	O(n)
remove(i)	O(n)

add(i, e)와 remove(i)를 좀 더 자세히 살펴보면

인덱스 i 이상의 요소에 대해서만 O(n - i + 1) 시간에 각각 실행된다.

따라서 배열 리스트의 끝에 있는 항목을 삽입하거나 제거하는 데

각각 add(n, e)와 remove(n - 1) 방법을 사용하면 O(1) 시간이 걸린다.

또한 이 관찰은 배열 리스트 ADT를

6.1.1절에 주어진 데크 ADT에 적용하는 데 흥미로운 결과를 가져온다.

이 경우 배열 리스트 ADT가 위에서 설명한 것과 같이

배열을 통해 구현된 경우

메소드는 각 데크의 addLast와 removeLast를 O(1) 시간에 실행한다.

그러나 메소드는 각 데크의 addFirst와 removeFirst를 O(n) 시간에 실행한다.

실제로 조금만 노력하면 배열 리스트 ADT를 배열 기반으로 구현하여

인덱스 0에서 삽입 및 제거, 배열 리스트의 끝에서

삽입 및 제거에 대한 O(1) 시간을 달성할 수 있다.

이를 달성하려면

인덱스 i에 있는 원소가 인덱스 i의 배열에 저장된다는

규칙을 포기해야 하지만,

5.2절에서 큐를 구현하기 위해 사용한 것과 같은

원형 배열 접근법을 사용해야 하기 때문이다.

6.1.4 단순 인터페이스와 java.util.ArrayList 클래스

배열 리스트 ADT의 자바 구현을 구성하기 위해

코드 조각 6.2에서 자바 인터페이스 IndexList를 보여준다.

IndexList: 배열 리스트 ADT에서 main 메소드를 캡처하는 자바 인터페이스

이 경우에는 IndexOutOfBoundsException을 사용하여

잘못된 인덱스 인수를 시그널링한다.

코드 조각 6.2: 배열 리스트 ADT의 IndexList 인터페이스.

public interface IndexList<E> {
  /** Returns the number of elements in this list. */
  public int size();
  /** Returns whether the list is empty. */
  public boolean isEmpty();
  /** Inserts an element e to be at index i, shifting all elements after this. */
  public void add(int i, E e)
    throws IndexOutOfBoundsException;
  /** Returns the element at index i, without removing it. */
  public E get(int i)
    throws IndexOutOfBoundsException;
  /** Removes and returns the element at index i, shifting the elements after this. */
  public E remove(int i)
    throws IndexOutOfBoundsException;
  /** Replaces the element at index i with e, returning the previous element at i. */
  public E set(int i, E e)
    throws IndexOutOfBoundsException;
}

java.util.ArrayList 클래스

Java는 위의 배열 리스트 ADT에 대해

제공하는 모든 메소드를 구현하는 클래스 java.util.ArrayList를 제공한다.

즉, IndexList 인터페이스에 대한 코드 조각 6.2에 포함된 모든 메소드를 포함한다.

또한 java.util.ArrayList 클래스에는 단순화된 배열 리스트 ADT 외에도 기능이 있다.

클래스 java.util.ArrayList에 있는 메소드

clear(): 배열 리스트에서 모든 요소를 제거한다.

toArray(): 배열 리스트의 모든 요소를 동일한 순서로 포함하는 배열을 반환한다.

그 중 목록을 검색하는 메소드들

indexOf(e): 배열 리스트에서 e와 동일한 요소가 처음 발생한 인덱스를 반환한다.

lastIndexOf(e): 배열 리스트에서 e와 동일한 요소가 마지막으로 발생한 인덱스를 반환한다.

이 두 메소드 모두 e와 동일한 요소를 찾지 못하면 (유효하지 않은) 인덱스 값 - 1을 반환한다.

6.1.5 확장 가능한 배열을 사용한 배열 리스트 구현

IndexList 인터페이스의 메소드(및 다른 유용한 메소드)를 구현하는 것 외에도

java.util.ArrayList 클래스는 단순 배열 구현의 약점을 극복하는 흥미로운 기능을 제공한다.

특히 6.1.3절에 주어진

배열 리스트 ADT에 대한 간단한 배열 구현의 가장 큰 약점은

배열 리스트에 저장될 수 있는 총 요소 수에 대해 고정 용량 N을 미리 지정해야 한다는 것이다.

배열 리스트의 실제 요소 수 n이 N보다 훨씬 작으면 이 구현은 공간을 낭비한다.

더 나쁜 것은 n이 N을 지나서 증가하면 이 구현은 충돌한다.

대신 java.util.ArrayList는 이 클래스를 사용할 때

배열 오버플로를 걱정할 필요가 없도록 흥미로운 확장 가능 배열 기법을 사용한다.

java.util.ArrayList 클래스와 마찬가지로

배열 리스트 S의 요소를 저장하는 배열 A를 확장할 수 있는 방법을 제시하겠다.

물론 자바(및 다른 프로그래밍 언어)에서는 배열 A를 실제로 확장할 수 없으며,

이미 관찰한 것처럼 배열 용량은 N으로 고정되어 있다.

대신 오버플로우가 발생했을 때,

즉 n = N이 메소드 add를 호출할 때,

다음과 같은 추가 단계를 수행한다:
1. 2N 용량의 새 배열 B 할당
2. i = 0, ..., N-1에 대하여 B[i]← A[i]라고 하자.
3. A ← B라고 하자. 즉, B를 S를 지원하는 배열로 사용한다.
4. A에 새 요소를 삽입한다.

이 배열 교체 전략은 확장 가능한 배열(extendable array)로 알려져 있는데,

이는 더 많은 요소를 위한 공간을 만들기 위해

기본 배열의 끝을 확장하는 것으로 볼 수 있기 때문이다.

(그림 6.2 참조)

그림 6.2: 확장 가능한 배열을 "성장"하기 위한 세 단계의 그림:

(a) 새 배열 B를 생성한다 .

(b) 요소를 A에서 B로 복사한다.

이전 배열의 미래 가비지 컬렉션은 표시되지 않는다.

확장 가능한 배열을 사용하여 IndexList 인터페이스 구현

코드 조각 6.3에서 확장 가능한 배열을 사용하여

배열 리스트 ADT의 자바 구현의 일부를 제공한다.

이 클래스는 배열이 증가할 수 있는 수단만 제공한다.

코드 조각 6.3: 확장 가능한 배열을 사용하여

배열 리스트 ADT를 실현하는

클래스 ArrayIndexList의 일부이다.

메소드 checkIndex(r, n) (표시되지 않음)는

인덱스 r이 [0, n - 1] 범위에 있는지 확인한다.

/** Realization of an indexed list by means of an array, which is doubled
 * when the size of the indexed list exceeds the capacity of the array.
 */
public class ArrayIndexList<E> implements IndexList<E> {
  private E[] A;            // array storing the elements of the indexed list
  private int capacity = 16; // initial length of array A
  private int size = 0;     // number of elements stored in the indexed list
  /** Creates the indexed list with initial capacity 16. */
  public ArrayIndexList() {
    A = (E[]) new Object[capacity]; // the compiler may warn, but this is ok
  }
  /** Inserts an element at the given index. */
  public void add(int r, E e)
    throws IndexOutOfBoundsException {
    checkIndex(r, size() + 1);
    if (size == capacity) {         // an overflow
      capacity *= 2;
      E[] B = (E[]) new Object[capacity];
      for (int i = 0; i<size; i++)
        B[i] = A[i];
      A = B;
    }
    for (int i=size-1; i >=r; i--)  // shift elements up
      A[i+1] = A[i];
    A[r] = e;
    size++;
  }
  /** Removes the element stored at the given index. */
  public E remove(int r)
    throws IndexOutOfBoundsException {
    checkIndex(r, size());
    E temp = A[r];
    for (int i=r; i < size-1; i++)  // shift elements up
      A[i] = A[i+1];
    size--;
    return temp;
  }
}

확장 가능한 배열의 분할 상환 분석

배열 교체 전략은 처음에는 느리게 보일 수 있는데,

일부 요소를 삽입할 때 필요한 단일 배열 교체를 수행하려면

O(n) 시간이 걸릴 수 있다.

그럼에도 불구하고

배열 교체를 수행한 후 새 배열을 사용하면

배열을 다시 교체하기 전에

배열 리스트에 n개의 새로운 요소를 추가할 수 있다.

이 간단한 사실은

처음에 비어 있던 배열 리스트에서 일련의 연산을 수행하는 것이

실제로 꽤 효율적이라는 것을 보여준다.

push 연산: 배열 리스트의 마지막 요소가 될 요소를 삽입하는 것

(그림 6.3 참조)

그림 6.3: 초기 크기 1의 java.util.ArrayList에서 일련의 push 연산의 실행 시간.

분할 상환(amortization)이라고 불리는 알고리즘 설계 패턴을 사용하여,

우리는 확장 가능한 배열로 구현된 배열 리스트에서

그러한 push 연산을 수행하는 것이

실제로 꽤 효율적이라는 것을 보여줄 수 있다.

분할 상환 분석(amortized analysis)을 수행하기 위해,

우리는 컴퓨터를

일정한 계산 시간 동안

사이버 달러(cyber-dollar) 한 개를 지불해야 하는

동전으로 작동하는 기기로 간주하는

회계 기법을 사용한다.

어떤 연산이 실행되면,

우리는 현재 "은행 계좌"에

그 연산의 실행 시간에 지불할 수 있는

충분한 사이버 달러를 가지고 있어야 한다.

따라서, 어떤 연산에 사용된 사이버 달러의 총 금액은

그 연산에 사용된 총 시간에 비례할 것이다.

이 분석 방법을 사용하는 것의 장점은

우리가 사이버 달러를 절약하기 위해

일부 연산을 과다 청구할 수 있다는 것이다.

명제 6.2: S를 초기 길이가 1인 확장 가능한 배열로 구현된 배열 리스트이라고 하자.

S가 비어 있는 상태에서 시작하여 일련의 n개의 push 연산을 수행하는 총 시간은 O(n)이다.

정당성: 배열을 증가시키는 데 드는 시간을 제외하고,

1개의 사이버 달러로 S의 각 푸시 작업을 수행하는 데 드는 비용을 지불할 수 있다고 가정하자.

또한 배열을 k 크기에서 2k 크기로 증가시키는 데 드는 시간 동안

요소를 복사하는 데 드는 k개의 사이버 달러가 필요하다고 가정하자.

우리는 각 push 연산에 3개의 사이버 달러를 충전해야 한다.

따라서, 우리는 2개의 사이버 달러에 의해

넘치지 않는 각 push 연산에 비용을 청구한다.

배열을 증가시키지 않는 삽입으로 이익을 얻는 2개의 사이버 달러가

삽입된 요소에 "저장"되어 있다고 생각하자.

배열 리스트 S에 2^i개의 요소가 있을 때,

일부 정수 i에 대해 i ≥ 0이고,

S를 나타내는 배열 리스트가 사용하는 배열의 크기는 2^i이다.

따라서 배열의 크기를 두 배로 늘리려면 2^i개의 사이버 달러가 필요하다.

다행히도, 이러한 사이버 달러는

2^(i-1)부터 2^i - 1까지 셀에 저장된 요소에서 찾을 수 있다.

(그림 6.4 참조)

이전 오버플로우는 요소의 수가 처음으로 2^(i-1)보다 많아져서

2^(i-1)부터 2^i - 1까지 셀에 저장된

사이버 달러를 사용하지 않은 경우에 발생했다.

따라서 각 작업에 3개의 사이버 달러가 청구되고

모든 계산 시간이 지불되는 유효한 분할상환 방식이 있다.

즉, 3n 사이버 달러를 사용하여 n개의 push 연산 실행 비용을 지불할 수 있다.

각 push 연산의 분할 실행 시간: O(1)

n개의 push 연산의 총 실행 시간: O(n)

그림 6.4: 배열 리스트에 있는 일련의 push 연산 예:

(a) 8셀 배열이 꽉 찼고, 4번부터 7번까지 셀에 2개의 사이버 달러가 "저장"되었다.

(b) push 연산으로 인해 오버플로가 발생하고 용량이 두 배로 증가한다.

8개의 오래된 요소를 새 배열에 복사하는 비용은 이미 표에 저장된 사이버 달러에서 지불된다.

새 요소를 삽입하는 비용은 push 연산에 충전된 사이버 달러 중 하나에서 지불되며,

수익을 얻은 2개의 사이버 달러는 8번 셀에 저장된다.

6.2 노드 리스트

인덱스를 사용하는 것은 요소가 수열에 나타나는 위치를 나타내는 유일한 방법은 아니다.

만약 (단일 또는 이중) 연결 리스트으로 구현된 수열 S가 있다면,

S에 접근하고 업데이트할 위치를 식별하는 수단으로

인덱스 대신 노드를 사용하는 것이 더 자연스럽고 효율적일 수 있다.

이 절에서는 노드 리스트 ADT를 정의하고,

노드 리스트에서 "장소"라는 개념을 추상화하는 관련 위치(position) ADT를 사용하여

구체적인 연결 리스트 자료 구조(제3.2절 및 제3.3절)를 추상화한다.

6.2.1 노드 기반 연산

S를 (단일 또는 이중) 연결 리스트이라고 하자.

우리는 노드를 매개 변수로 하고

노드를 반환 타입으로 제공하는 S에 대한 방법을 정의하고자 한다.

연결 리스트에서 요소의 인덱스를 찾는 것은

리스트의 시작 또는 끝부터 요소를 계산하는 것을 필요로 하기 때문에,

이러한 방법은 인덱스 기반 방법에 비해 상당한 속도 향상을 제공할 수 있다.

예시1)

remove(v):

리스트의 노드 v에 저장된 S의 요소를 제거한다.

노드를 매개 변수로 사용하는 것은

노드가 저장된 곳으로 직접 이동한 다음

이웃의 next 및 prev 링크를 업데이트하여

이 노드를 "연결"하므로써

O(1) 시간에 요소를 제거할 수 있게 한다.

예시2)

addAfter(v, e):

새로운 원소 e를 S에 O(1)시간에 삽입할 수 있다.

새 요소의 노드를 삽입해야 하는 노드 v를 지정해야 한다.

이 경우, 우리는 단순히 새로운 노드를 "링크"한다.

이러한 노드 기반 연산을 추가하여 리스트 ADT의 방법을 정의하는 것은

우리가 리스트의 구현에 대해 얼마나 많은 정보를 노출해야 하는지에 대한 문제를 제기한다.

물론 사용자에게 이러한 세부 사항을 밝히지 않고

단일 또는 이중 연결 리스트를 사용할 수 있는 것이 바람직하다.

마찬가지로, 우리는 사용자가 우리가 모르는 사이에

리스트의 내부 구조를 수정하는 것을 원하지 않다.

그러나 만약 사용자가

그 노드의 내부 데이터에 접근할 수 있는 형태로

리스트의 노드에 대한 참조를 제공한다면,

그러한 수정은 가능할 것이다(예: next 또는 prev 필드).

리스트의 다양한 구현에서 요소를 저장하는 다양한 방법을 추상화하고 통합하기 위해,

위치의 개념을 소개한다.

위치(포지션, position)은 리스트의 다른 요소에 대한 "장소"의 직관적인 개념을 공식화한다.

6.2.2 위치

리스트에 대한 일련의 작업을 안전하게 확장하기 위해

객체 지향 설계 원칙을 위반하지 않고

이중 또는 단일 연결 리스트 구현의 효율성을 누릴 수 있는 "위치(position)" 개념을 추상화한다.

이 프레임워크에서 리스트를

각 요소를 위치에 저장하고 이러한 위치를 선형 순서로 배열하는 요소의 모음으로 본다.

위치(position)는 다음과 같은 간단한 방법을 지원하는 추상 데이터 타입이다:

element(): 이 위치에 저장된 요소를 반환한다.

위치는 항상 상대적으로, 즉 이웃들의 관점에서 정의된다.

리스트에서 위치 p는 항상 어떤 위치 q 다음에 있고

어떤 위치들은 (p가 첫 번째 또는 마지막 위치가 아닌 한) 앞에 있을 것이다.

리스트 S의 어떤 요소 e와 관련된 위치 p는 S에서 e의 지수가 변하더라도,

우리가 명시적으로 e를 제거하지 않는 한 (따라서 위치 p를 파괴) 변하지 않다.

또한 p에 저장된 요소 e를 다른 요소로 교체하거나 교체하더라도 위치 p는 변하지 않다.

위치에 대한 이러한 사실을 통해 위치 객체를 매개 변수로 하고

위치 객체를 반환 값으로 제공하는 위치 기반 리스트 방법의 집합을 정의할 수 있다.

6.2.3 노드 리스트 추상 데이터 타입

"노드"라는 개념을 리스트에 캡슐화하기 위해 위치 개념을 사용하여

노드 리스트 ADT라고 하는 또 다른 타입의 수열 ADT를 정의할 수 있다.

이 ADT는 리스트 S에 대해 다음과 같은 방법을 지원한다:

first ():
S의 첫 번째 요소의 위치를 반환한다.

S가 비어 있으면 오류가 발생한다.

last():
S의 마지막 요소의 위치를 반환한다.

S가 비어 있으면 오류가 발생한다.

prev(p):
위치 p에서 앞에 있는 S의 요소의 위치를 반환한다.

p가 첫 번째 위치이면 오류가 발생한다.
next(p):
위치 p의 S 다음 S의 요소의 위치를 반환한다.

p가 마지막 위치일 경우 오류가 발생한다.

위의 메소드를 사용하면

리스트에서 상대적인 위치를 처음이나 끝에서 참조하고

리스트의 위쪽이나 아래쪽으로 점진적으로 이동할 수 있다.

이러한 위치는 직관적으로 리스트의 노드로 생각할 수 있지만

노드 객체에 대한 특정 참조는 없다.

또한 리스트 메소드에 대한 인수로 위치를 제공하면

해당 위치는 해당 리스트에서 유효한 위치를 나타내야 한다.

노드 리스트 업데이트 방법

위 메소드와 일반 메소드 size 및 isEmpty 외에도

위치 객체를 매개 변수로 사용하거나

위치 객체를 반환 값으로 제공하는

노드 리스트 ADT에 대한 다음 업데이트 메소드도 포함한다.

set(p, e):
위치 p에 있는 요소를 p로 교체하고 이전에 위치 p에 있는 요소를 반환한다.
addFirst(e):
S에 첫 번째 요소로 새 요소 e를 삽입한다.
addLast(e):
마지막 요소로 S에 새 요소 e를 삽입한다.
addBefore(p, e):
위치 p 이전에 S에 새 요소 e를 삽입한다.
addAfter(p, e):
p 위치 후 S에 새 e를 삽입한다.
remove(p):
S의 위치 p에 있는 요소를 제거하고 반환하여 S의 위치를 무효하게 한다.

노드 리스트 ADT를 사용하면 해당 위치가 정확히 표시되는 방식에 대해 걱정하지 않고

해당 위치의 관점에서 정렬된 객체 컬렉션을 볼 수 있다(그림 6.5 참조)

그림 6.5: 노드 리스트. 현재 순서에서 위치는 p, q, r, s이다.

addBefore(first(), e)로 연산 addFirst(e)를 수행하고,

addAfter(getLast(), e)로 연산 addLast(e)를 수행할 수 있으므로

처음에는 노드 리스트 ADT에 대한 위의 레퍼토리에 중복성이 있는 것처럼 보일 수 있다.

그러나 이러한 대체는 비어 있지 않은 리스트에 대해서만 수행할 수 있다.

리스트 연산 중 하나에 인수로 전달된 위치가 유효하지 않으면 오류 조건이 발생한다.

위치 p가 유효하지 않은 이유는 다음과 같다:

• p= null
• p는 이전에 리스트에서 삭제되었다
• p는 다른 리스트의 위치이다
• p는 리스트의 첫번째 위치이고 우리는 prev(p)라고 부른다
• p는 리스트의 마지막 위치이고 우리는 next(p)를 부른다.

다음 예에서는 노드 리스트 ADT의 동작을 설명한다.

예제 6.3: 처음에 빈 리스트 노드 S에 대한 일련의 연산을 다음과 같이 보여준다.

변수 p1, p2 등을 사용하여 서로 다른 위치를 표시하고 괄호 안에 현재 저장된 객체를 표시한다.

연산	출력	S
addFirst(8)	-	(8)
first()	p1(8)	(8)
addAfter(p1, 5)	-	(8, 5)
addBefore(p2, 3)	-	(8, 3, 5)
prev(p2)	p3(3)	(8, 3, 5)
addFirst(9)	7	(9, 8, 3, 5)
last()	p2(5)	(9, 8, 3, 5)
remove(first())	9	(8, 3, 5)
set(p3, 7)	3	(8, 7, 5)
addAfter(first(), 2)	-	(8, 2, 7, 5)

위치에 대한 개념이 내장된 노드 리스트 ADT는 여러 가지 설정에서 유용하다.

예를 들어, 카드 게임을 시뮬레이션하는 프로그램은

각 사람의 손을 노드 리스트로 모델링할 수 있다.

대부분의 사람들은 동일한 슈트의 카드를 함께 보관하기 때문에,

사람의 손에서 카드를 삽입하고 제거하는 방법은

노드 리스트 ADT의 방법을 사용하여 구현될 수 있으며,

슈트의 자연스러운 순서에 의해 위치가 결정된다.

마찬가지로, 이러한 편집자는 일반적으로 편집되는 텍스트의 문자 리스트에서

현재 위치를 나타내는 커서에 대한 모든 업데이트를 수행하므로

단순한 텍스트 편집자는 위치 삽입 및 제거 개념을 포함한다.

위치 ADT를 나타내는 자바 인터페이스는 코드 조각 6.4에 나와 있다.

코드 조각 6.4: 위치 ADT를 위한 자바 인터페이스.

public interface Position<E> {
  /** Return the element stored at this position. */
  E element();
}

코드 조각 6.5에는 위치 리스트이라는 노드 리스트 ADT를 위한 인터페이스가 제공된다.

이 인터페이스는 오류 조건을 나타내기 위해 다음과 같은 예외를 사용한다.

BoundaryViolationException:

위치가 리스트의 위치 범위 밖에 있는 요소에 접근하려고 시도할 경우 버려진다

(예: 수열의 마지막 위치에서 다음 호출 방법).

InvalidPositionException:

인수로 제공된 위치가 유효하지 않은 경우

(예: null 참조이거나 연결 리스트가 없는 경우) 버려진다.

코드 조각 6.5: 노드 리스트 ADT를 위한 자바 인터페이스.

public interface PositionList<E> {
  /** Returns the number of elements in this list. */
  public int size();
  /** Returns whether the list is empty. */
  public boolean isEmpty();
  /** Returns the first node in the list. */
  public Position<E> first();
  /** Returns the last node in the list. */
  public Position<E> last();
  /** Returns the node after a given node in the list. */
  public Position<E> next(Position<E> P)
    throws InvalidPositionException, BoundaryViolationException;
  /** Returns the node before a given node in the list. */
  public Position<E> prev(Position<E> P)
    throws InvalidPositionException, BoundaryViolationException;
  /** Inserts an element at the front of the list, returning new position. */
  public void addFirst(E e);
  /** Inserts an element at the back of the list, returning new position. */
  public void addLast(E e);
  /** Inserts an element after a given node in the list. */
  public void addAfter(Position<E> p, E e)
    throws InvalidPositionException, BoundaryViolationException;
  /** Inserts an element before a given node in the list. */
  public void addBefore(Position<E> p, E e)
    throws InvalidPositionException, BoundaryViolationException;
  /** Removes a node from the list, returning the element stored there. */
  public E remove(Position<E> p) throws InvalidPositionException;
  /** Replaces the element stored at the given node, returning old element. */
  public E set(Position<E> p, E e) throws InvalidPositionException;
}

또 다른 데크 어댑터

노드 리스트 ADT에 대한 논의와 관련하여,

이 ADT는 표 6.3과 같이 데크 ADT에 대한 어댑터 클래스를 정의하기에 충분하다.

표 6.3: 노드 리스트를 통한 데크 실현

데크 메소드	노드 리스트 메소드를 통한 실현
size(), isEmpty()	size(), isEmpty()
getFirst()	first()·element()
getLast()	last()·element()
addFirst(e)	addFirst(e)
addLast(e)	addLast(e)
removeFirst()	remove(first())
removeLast()	remove(last())

6.2.4 이중 연결 리스트 구현

이중 연결 리스트(섹션 3.3)을 사용하여

노드 리스트 ADT를 구현하려고 한다고 가정한다.

연결 리스트의 노드가 위치 ADT를 구현하도록 간단히 만들 수 있다.

즉, 각 노드가 Position 인터페이스를 구현하도록 하고 메소드 element()를 정의한다.

메소드 element(): 노드에 저장된 요소를 반환한다.

따라서 노드 자체가 위치 역할을 한다.

연결 리스트는 내부적으로 노드로 간주되지만 외부에서는 위치로만 간주된다.

내부 보기에서 노드 v 인스턴스 변수 prev와 next를 제공할 수 있다.

혹은 헤더와 트레일러 센티널 노드를 사용할 수도 있다.

변수 prev: v의 이전 노드를 참조한다.

변수 next: v의 후속 노드를 참조한다.

헤더 노드: 리스트의 시작을 표시한다.

트레일러 노드: 리스트의 끝을 표시한다.

변수 prev와 next를 직접 사용하는 대신

이러한 변수에 접근하고 수정할 수 있는 노드의 메소드

getPrev, setPrev, getNext 및 setNext를 정의한다.

코드 조각 6.6에서는 위치 ADT를 구현하는

이중 연결 리스트의 노드에 대한 Java 클래스 DNode를 보여준다.

이 클래스는 코드 조각 3.17에 표시된 클래스 DNode와 유사하지만,

이제 노드에 문자열 대신 일반 요소가 저장된다.

아래 DNode 클래스의 prev 및 next 인스턴스 변수는

다른 DNode 객체에 대한 private 참조이다.

코드 조각 6.6: 이중 연결 리스트의 노드를 구현하고

Position 인터페이스(ADT)를 구현하는 클래스 DNode.

public class DNode<E> implements Position<E> {
  private DNode<E> prev, next;  // References to the nodes before and after
  private E element; // Element stored in this position
  /** Constructor */
  public DNode(DNode<E> newPrev, DNode<E> newNext, E elem) {
    prev = newPrev;
    next = newNext;
    element = elem;
  }
  // Method from interface Position
  public E element() throws IndexOutOfBoundsException {
    if ((prev == null) && (next == null)) {
      throw new IndexOutOfBoundsException("Position is not in a list!");
    return element;
  }
  // Accessor methods
  public Dnode<E> getNext() { return next; }
  public Dnode<E> getPrev() { return prev; }
  // Update methods
  public void setNext(Dnode<E> newNext)  { next = newNext; }
  public void setPrev(Dnode<E> newPrev) { prev = newPrev; }
  public void setElement(E newElement) { element = newElement; }
}

S에서 위치 p가 주어지면 p를 "언랩(unwrap)"하여

기본 노드 v를 드러낼 수 있다.

이는 위치를 노드에 캐스팅함으로써 수행된다.

노드 v가 있으면 v.getPrev로 메소드 prev(p)를 구현할 수 있다

(v.getPrev로 반환된 노드가 헤더인 경우는 제외).

따라서 이중 연결 리스트 구현에서의 위치는

추가적인 시간 또는 공간 오버헤드 없이

객체 지향적인 방식으로 지원될 수 있다.

위치 p 뒤에 요소 e를 삽입하기 위해

addAfter(p, e) 메소드를 구현하는 방법을 고려한다.

3.3.1절의 논의와 유사하게 요소 e를 유지하기 위해

새 노드 v를 만들고 v를 리스트의 위치에 연결한 다음

v의 두 새 이웃의 next 및 prev 참조를 업데이트한다.

이 메소드는 코드 조각 6.7에 나와 있으며

그림 6.6에 (다시) 표시되어 있다.

센티넬을 사용한 경우(3.3절)

이 알고리즘은 p가 마지막 실제 위치인 경우에도 작동한다.

코드 조각 6.7: 연결 리스트의 위치 p 뒤에 요소 e를 삽입한다.

Algorithm addAfter(p, e):

Create a new node v

v.setElement(e)

v.setPrev(p) {link v to its predecessor}

v.setNext(p.getNext()) {link v to its successor}

(p.getNext()).setPrev(v) {link p's old successor to v}

p.setNext(v) {link p to its new successor, v}

그림 6.6: "JFK" 위치 뒤에 새 노드 추가:
(a) 삽입 전;
(b) "BWI" 요소로 노드 v를 생성하고 연결한다;
(c) 삽입 후에.

메소드 addBefore, addFirst, addLast 알고리즘은

메소드 addAfter와 유사하다.

다음으로, p 위치에 저장된 e 요소를 제거하는 remove(p) 메소드를 고려한다.

3.3.2절의 논의와 유사하게,

이 작업을 수행하기 위해 p의 두 이웃을 연결하여 p를 연결한다.

p가 연결된 후에는 어떤 노드도 p를 가리키지 않으므로

가비지 콜렉터는 p에 대한 공간을 다시 확보할 수 있다.

이 알고리즘은 코드 조각 6.8에 나와 있으며 그림 6.7에 나와 있다.

헤더와 트레일러 센티넬을 사용한 점을 상기시켜 보면,

이 알고리즘은 p가 리스트의 첫 번째, 마지막 또는 유일한 실제 위치인 경우에도 작동한다.

코드 조각 6.8: 연결 리스트의 p 위치에 저장된 요소 e를 제거한다.

Algorithm remove(p):

t ← p.element() {a temporary variable to hold the return value}

(p.getPrev()).setNext(p.getNext()) {linking out p}

(p.getNext()).setPrev(p.getPrev())

p.setPrev(null) {invalidating the position p}

p.setNext(null)

return t

그림 6.7: "PVD" 위치에 보관된 객체 제거:
(a) 제거 전;
(b) 이전 노드를 연결한다;
(c) 제거 후(및 가비지 컬렉션).

결론적으로, 이중 연결 리스트를 사용하여

리스트 ADT의 모든 메소드를 O(1) 시간으로 수행할 수 있다.

따라서 이중 연결 리스트는 리스트 ADT를 효율적으로 구현하는 것이다.

자바의 노드 리스트 구현

이중 연결 리스트를 사용하여

노드 리스트 ADT를 구현하는 Java 클래스 NodePositionList의 일부는

코드 조각 6.9–6.11에 나와 있다.

코드 조각 6.9는

NodePositionList의 인스턴스 변수인

NodePositionList의 생성자와 메서드인 CheckPosition을 보여주며,

이는 안전 검사를 수행하고 위치를 "언랩(unwrap)"하여 DNode로 다시 캐스트한다.

코드 조각 6.10에는 추가 접근자 및 업데이트 메소드가 나와 있다.

코드 조각 6.11에는 추가 업데이트 메소드가 나와 있다.

코드 조각 6.9-6.11:

이중 연결 리스트로 노드 리스트 ADT를 구현하는

NodePositionList 클래스의 일부이다.

remove 메소드에서 위치를 무효화하는 데 사용되는 메커니즘이

checkPosition 편의 함수에서 수행되는 검사 중 하나와 일치한다.

public class NodePositionList<E> implements PositionList<E> {
  protected int numElts;       // Number of elements in the list
  private DNode<E> header, trailer;  // Special sentinels
  /** Constructor that creates an empty list; O(1) time */
  public NodePositionList(DNode<E> newPrev, DNode<E> newNext, E elem) {
    numElts = 0;
    header = new DNode<E>(null, null, null); // create header
    trailer = new DNode<E>(header, null, null); // create trailer
    header.setNext(trailer);    // make header and trailer point to each other
  }
  /** Checks if position is vaild for this list and converts it to 
   *  DNode if it is valid; O(1) time */
  protected DNode<E> checkPosition(Position<E> p) 
    throws InvalidPositionException {
    if (p == null)
      throw new InvalidPositionException
        ("Null Position passed to NodeList!");
    if (p == header)
      throw new InvalidPositionException
        ("The header node is not a valid position");
    if (p == trailer)
      throw new InvalidPositionException
        ("The trailer node is not a valid position");
    try {
      DNode<E> temp = (DNode<E>) p;
      if((temp.getPrev() == null) || (temp.getNext() == null))
        throw new InvalidPositionException
          ("Position does not belong to a valid NodeList");
      return element;
    } catch (ClassCastException e) {
      throw new InvalidPositionException
        ("Position is of wrong type for this list");
    }
  }
  /** Returns the number of elements in the list;  O(1) time */
  public int size() { return numElts; }
  /** Returns whether the list is empty;  O(1) time */
  public boolean isEmpty() { return (numElts == 0); }
  /** Returns the first position in the list;  O(1) time */
  public Position<E> first() 
     throws EmptyListException { 
    if (isEmpty())
      throw new EmptyListException("List is empty");
    return header.getNext(); 
  }
  /** Returns the position before the given one;  O(1) time */
  public Position<E> prev(Position<E> p) 
     throws InvalidPositionException, BoundaryViolationException { 
    Dnode<E> v = checkPosiiton(p);
    Dnode<E> prev = v.getPrev();
    if (prev == header)
      throw new BoundaryViolationException
        ("Cannot advance past the beginning of the list");
    return prev; 
  }
  /** Insert the given element before the given position, returning
   * the new position; O(1) time */
  public void addBefore(Position<E> p, E element)  
     throws InvalidPositionException { 
    Dnode<E> v = checkPosiiton(p);
    numElts++;
    Dnode<E> newNode = new Dnode<E>(v.getPrev(), v, element);
    v.getPrev().setNext(newNode);
    v.setPrev(newNode);
  }
  /** Insert the given element beginning of the list, returning
   *  the new position; O(1) time */
  public void addFirst(E element) { 
    numElts++;
    Dnode<E> newNode = new Dnode<E>(header, header.getNext(), element);
    header.getNext().getPrev().setNext(newNode);
    header.setPrev(newNode);
  }
  /** Remove the given position from the list; O(1) time */
  public E remove(Position<E> p) 
     throws InvalidPositionException { 
    Dnode<E> v = checkPosiiton(p);
    numElts--;
    Dnode<E> vPrev = v.getPrev();
    Dnode<E> vNext = v.getNext();
    vPrev.setNext(vNext);
    vNext.setPrev(vPrev);
    E vElem = v.element();
    // unlink the position from the list and make it invalid
    v.setNext(null);
    v.setPrev(null);
  }
  /** Replace the element at the given position with the new element returning
   *  the new position; O(1) time */
  public E set(Position<E> p, E element)
     throws InvalidPositionException { 
    Dnode<E> v = checkPosiiton(p);
    E oldElt = v.element();
    v.setElement(element);
    return oldElt;
  }
}

6.3 반복자

배열 리스트, 리스트 또는 수열에 대한 일반적인 계산은

한 번에 하나씩 특정 요소를 찾기 위해 해당 요소를 순서대로 행진하는 것이다.

6.3.1 반복자 및 반복할 수 있는 추상 데이터 타입

반복자(iterator): 한 번에 한 요소의 집합을 통해 스캔하는 과정을 추상화하는 소프트웨어 설계 패턴

반복자는 다음을 구성된다.

수열 S
S의 현재 요소
S의 다음 요소로 발걸음을 옮겨 현재 요소로 만드는 방법

따라서 반복자는 우리가 6.2절에서 소개한 위치 ADT의 개념을 확장한 것이다.

사실, 위치는 어디에도 가지 않는 반복자라고 생각할 수 있다.

반복자는 "장소"와 "다음"의 개념을 객체들의 집합 안에 캡슐화한다.

반복자 ADT는 두 가지 메소드를 지원하는 것으로 정의한다.

hasNext(): 반복자에 요소가 남아 있는지 테스트한다.
next(): 반복자의 다음 요소를 반환한다.

반복자 ADT는 수열의 순회에서 "현재" 요소의 개념을 갖는다는 것을 주목하자.

물론 반복자가 적어도 하나의 요소를 포함한다고 가정할 때,

반복자의 첫 번째 요소는 next 메소드로 첫 번째 호출에 의해 반환된다.

반복자는 집합의 특정 조직으로부터 독립적인 방식으로

객체 집합의 모든 요소에 접근할 수 있는 통합된 체계를 제공한다.

배열 리스트, 리스트 또는 수열에 대한 반복자는

요소를 그들의 선형 순서에 따라 반환해야 한다.

자바의 단순 반복자

Java는 java.util.Iterator 인터페이스를 통해 반복자를 제공한다.

java.util.Scanner 클래스(섹션 1.6)는 이 인터페이스를 구현한다.

이 인터페이스는 이전에 반환된 요소를 컬렉션에서 제거하는

추가적인 (선택적인) 메소드를 지원한다.

그러나 이 기능(반복자를 통해 요소를 제거)은

객체 지향 관점에서 다소 논란이 있으며

클래스별 구현이 선택적이라는 것은 놀라운 일이 아니다.

또한 자바는 java.util.Enumeration 인터페이스를 제공한다.

이 인터페이스는 역사적으로 반복자 인터페이스보다 오래되었으며

hasMoreElements() 및 nextElement()라는 이름을 사용한다.

반복 가능한 추상 데이터 타입

데이터 구조를 통해 스캔하기 위한 통합된 일반 메커니즘을 제공하기 위해

객체 모음을 저장하는 ADT는 다음 방법을 지원해야 한다:

iterator(): 집합에 있는 요소의 반복자를 반환한다.

이 메소드는 java.util.ArrayList 클래스에서 지원된다.

사실 이 메소드는 매우 중요하기 때문에

전체 인터페이스인 java.lang.Iterable이 있으며 이 메소드만 포함되어 있다.

이 메소드를 사용하면 쉽게 리스트의 요소를 반복해야 하는 계산을 지정할 수 있다.

예를 들어 코드 조각 6.12와 같이

노드 리스트에서 위 메소드를 지원하는 것을 보장하기 위해

이 메소드를 PositionList 인터페이스에 추가할 수 있다.

이 경우에는 PositionList extends Iterable도 말씀드리고자 한다.

따라서 배열 리스트와 노드 리스트가 iterator() 메소드를 지원한다고 가정해 보겠다.

코드 조각 6.12: PositionList 인터페이스에 반복자 메소드를 추가한다.

public interface PositionList<E> extends Iterable<E> {
  // ...all the other methods of the list ADT ...
  /** Returns an iterator of all the elements in the list. */
  public iterator<E> iterator();
}

이러한 PositionList 정의가 주어지면,

코드 조각 6.13과 같이 iterator() 메소드에 의해 반환되는 반복자를 사용하여

노드 리스트의 문자열 표현을 만들 수 있다.

코드 조각 6.13: 노드 리스트를 문자열로 변환하는 데 사용되는 자바 반복자의 예.

/** Returns a textual representation of a given node list */
public static <E> String toString(PositionList<E> I) {
  Iterator<E> it = I.iterator();
  String s = "[";
  while (it.hasNext()) {
    s += it.next();  // implicit cast of the next element to String
    if (it.hasNext())
      s += ", ";
    }
  s += "]";
  return s;
}

6.3.2 자바 For-Each문

반복자에 의해 반환되는 요소를 통과하는 것은 매우 일반적인 구조이기 때문에

자바는 for-each문이라고 불리는 그런 반복문들에 대한 약어 표기를 제공한다.

그런 반복문의 구문은 다음과 같다:

for (Type name : expression)

loop statement

expression: java.lang.Iterable 인터페이스를 구현하는 컬렉션을 나타낸다.

Type: 이 클래스에 대해 반복자가 반환하는 객체의 타입

name: loop_statement에서 이 반복자의 요소 값을 가져올 변수의 이름

이 표기법은 실제로 다음을 나타내는 약자이다:

for (Iterator<Type> it = expression.iterator(); it.hasNext(); ) {

Type name = it.next();

loop_statement

}

예를 들어 리스트 values의 정수 객체를 가지고 있고

values가 java.lang.Iterable을 구현하는 경우

다음과 같이 모든 values의 정수를 합산할 수 있다:

List<Integer> values;
// ... 새 값 리스트를 만들고 그것을 정수로 채우는 문
정수와 함께...
int sum = 0;
for (Integer i : values)
sum + = i; // unboxing을 사용하면 다음을 수행할 수 있다

위의 반복문은

"values 내에 각 Integer i에 대해 반복문 본문을 수행한다
(이 경우 i를 sum한다)"

위와 같은 for-each문 형식 외에도

자바는 식이 Type의 배열인 경우 for-each문을 정의할 수 있도록 하는데,

이 경우 기본 타입이나 객체 타입이 될 수 있다.

예를 들어 배열 v의 정수를 다음과 같이 합계할 수 있으며,

v는 처음 10개의 양의 정수를 저장한다:
int[] v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int total = 0;

for (int i : v)
total += i;

6.3.3 반복자 구현

요소 집합에 대한 반복자를 구현하는 한 가지 방법은

요소의 "스냅샷"을 만들고 반복하는 것이다.

이 방법은 요소에 대한 순차적 접근을 지원하는

별도의 자료 구조에 집합을 저장하는 것을 포함한다.

예를 들어, 집합의 모든 요소를 큐에 넣을 수 있는데,

이 경우 메소드의 hasNext()는 !isEmpty()에 대응하고

next()는 enqueue()에 대응한다.

이 방법을 사용하면

메소드 iterator()는 크기 n의 컬렉션에 O(n) 시간이 걸린다.

복사 오버헤드는 상대적으로 비용이 많이 들기 때문에

대부분의 경우 반복자가 복사본이 아닌 컬렉션 자체에서 작동하도록 하는 것이 좋다.

이 직접적인 접근 방식을 구현할 때는

반복자의 커서가 컬렉션 어디를 가리키는지만 계속 추적하면 된다.

따라서 이 경우에 새로운 반복자를 만드는 것은

단순히 컬렉션의 첫 번째 요소 바로 앞에 배치된 커서를 나타내는 반복자 객체를 만드는 것이다.

마찬가지로 next() 메소드를 수행하려면

다음 요소가 있는 경우 해당 요소를 반환하고

이 요소의 위치 바로 옆에서 커서를 이동해야 한다.

따라서 이 접근 방식에서는

반복자의 각 메소드와 마찬가지로

반복자를 만드는 데 O(1) 시간이 걸린다.

이러한 반복자를 구현하는 클래스는 코드 조각 6.14에서 보여드리고,

이 반복자를 사용하여 NodePositionList 클래스에서 iterator() 메소드를 구현하는 방법은

코드 조각 6.15에서 보여드리고 있다.

코드 조각 6.14: Position List의 요소 반복자 클래스.

public class ElementIterator<E> implements Iterator<E> {
  protected PositionList<E> list; // the underlying list
  protected Position<E> cursor; // the next position
  /** Creates an element iterator over the given list. */
  public ElementIterator(PositionList<E> L) {
    list = L;
    cursor = (list.isEmpty())? null : list.first();
  }
  public boolean hasNext() { return (cursor != null); }
  public E next() throws NoSuchElementException {
    if (cursor == null)
      throw new NoSuchElementException("No next element");
    E toReturn =cursor.element();
    cursor = (cursor == list.last())? null : list.next(cursor);
    return toReturn;
  }
}

코드 조각 6.15: 클래스 NodePositionList의 iterator() 메소드.

/** Returns an iterator of all the elements in the list. */
public Iterator<E> iterator() { return new ElementIterator<E>(this); }

위치 반복자

리스트 및 수열 ADT와 같이 위치 개념을 지원하는 ADT의 경우

다음과 같은 방법을 제공할 수도 있다:

positions(): 집합의 위치를 요소로 포함하는

Iterable 객체(배열 리스트 또는 노드 리스트 등)를 반환한다.

이 메소드를 통해 반환되는 반복자를 사용하면 리스트의 위치를 반복할 수 있다.

노드 리스트에서 이 메소드를 지원하는 것을 보장하기 위해

코드 조각 6.16과 같이 PositionList 인터페이스에 추가할 수 있다.

그런 다음 코드 조각 6.17과 같이

이 메소드의 구현을 NodePositionList에 추가할 수 있다.

이 메소드는 NodePositionList 클래스 자체를 사용하여

원래 리스트의 위치를 요소로 포함하는 리스트를 만든다.

이 위치 리스트을 Iterable 객체로 반환하면 다음 작업을 수행할 수 있다

그런 다음 이 객체에 대해 iterator()를 호출하여

원래 리스트에서 위치 반복자를 가져온다.

코드 조각 6.16: PositionList 인터페이스에 반복자 메소드를 추가한다.

public interface PositionList<E> extends Iterable<E> {
  // ...all the other methods of the list ADT ...
  /** Returns an iterable collection of all the nodes in the list. */
  public iterable<Position<E>> positions();
}

코드 조각 6.17: 클래스 NodePositionList의 positions() 메소드.

  /** Returns an iterable collection of all the nodes in the list. */
  public iterable<Position<E>> positions() {   // create a list of positions;
    PositionList<Position<E>> P = new NodePositionList<Position<E>>();
    if (!isEmpty()) {
      Position<E> P = first();
      while (true) {
        P.addLast(p); // add position p as the last element of list P
        if (p == last())
          break;
        p = next(p);
      }
    }
    return P; // return P as our Iterable object
  }

이것과 다른 Iterable 객체들에 의해 반환되는 iterator() 메소드는

요소들을 오직 한 번만 통과할 수 있는 제한된 형식의 반복자를 정의한다.

그러나 더 강력한 반복자들도 정의될 수 있으며,

이를 통해 요소들의 특정 순서에 대해 앞과 뒤로 이동할 수 있다.

6.3.4 Java의 반복자 리스트

java.util.LinkedList 클래스는 API에서 위치 개념을 사용자에게 노출시키지 않는다.

대신 Java에서 LinkedList 객체에 접근하여

인덱스를 사용하지 않고 업데이트하는 바람직한 방법은

listIterator() 메소드를 사용하여

LinkedList에 의해 생성되는 ListIterator를 사용하는 것이다.

이러한 반복자는 로컬 업데이트 메소드뿐만 아니라 순방향 및 역방향 순회 메소드를 제공한다.

현재 위치는 첫 번째 요소 앞에 있거나 두 요소 사이에 있거나 마지막 요소 뒤에 있는 것으로 본다.

즉, 화면 커서가 화면의 두 문자 사이에 있는 것처럼 보이는 것처럼

리스트 커서(cursor)를 사용한다.

구체적으로 java.util.ListIterator 인터페이스는 다음과 같은 방법을 포함한다:

add(e):
반복자의 현재 위치에 요소 e를 추가한다.

hasNext():
반복자의 현재 위치 뒤에 요소가 있는 경우에만 참이다.

hasPrevious():
반복자의 현재 위치 앞에 요소가 있는 경우에만 참이다.

previous():
요소 e를 현재 위치 앞으로 되돌리고 현재 위치를 이전으로 설정한다.

next():
현재 위치 뒤에 요소 e를 반환하고 현재 위치를 e 이후로 설정한다.

nextIndex():
다음 요소의 인덱스를 반환한다.

previousIndex():
이전 요소의 인덱스를 반환한다.

set(e):
이전의 다음 연산 또는 이전 연산에서 반환된 요소를 e로 교체한다.

remove():
이전의 다음 연산 또는 이전 연산에서 반환된 요소를 제거한다.

내용을 수정할 때 동일한 리스트 위에 여러 개의 반복자를 사용하는 것은 위험하다.

리스트의 여러 "장소"에 삽입, 삭제 또는 교체가 필요한 경우

장소를 사용하여 이러한 위치를 지정하는 것이 더 안전하다.

그러나 java.util.LinkedList 클래스는 위치 객체를 사용자에게 노출시키지 않는다.

따라서 여러 반복자를 생성한 리스트를 수정하는 위험을 피하기 위해

java.util.Iterator 객체에는 "fail-fast" 기능이 있으며,

만약 해당 반복자의 기본 컬렉션이 예기치 않게 수정되면

해당 반복자가 즉시 무효화된다.

따라서 iterator()' 메소드로 호출하여

여러 반복자를 생성한 리스트를 수정하는 위험을 피하기 위해

java.util.iterator 객체에는 "fail-fast" 기능이 있다.

fail-fast 기능: 기본 컬렉션이 예기치 않게 수정되면 그러한 반복자가 즉시 무효화된다.

예시)

java.util.LinkedList 객체 L이 5개의 다른 반복자를 반환했는데

그 중 하나가 L을 수정하면

나머지 4개는 모두 즉시 무효화된다.

즉, Java는 많은 반복자가 연결 리스트 L을 동시에 순회할 수 있도록 허용하지만,

만약 그 중 하나가 L을 수정(추가, 설정 또는 제거 메소드를 사용)하면

L에 대한 다른 모든 반복자가 무효화된다.

마찬가지로 L이 자체 업데이트 메소드 중 하나로 수정되면

L에 대한 기존의 모든 반복자가 즉시 무효화된다.

java.util.List 인터페이스 및 구현

자바는 java.util.ArrayList의 배열 리스트 및 java.util.List 인터페이스에서

당사의 배열 리스트 및 노드 리스트 ADT와 유사한 기능을 제공하며,

이는 java.util.List의 연결 리스트와 함께 구현된다.

자바는 java.util.List 인터페이스에서

우리의 배열 리스트 및 노드 리스트의 ADT와 유사한 기능을 제공한다.

이 인터페이스는 java.util.ArrayList의 배열과 java.util.LinkedList의 연결 리스트로 구현된다.

이 두 구현 사이에는 몇 가지 절충점이 있으며,

다음 섹션에서 자세히 설명한다.

또한 자바는 노드 리스트 ADT가 위치에서 도출하는 것과

유사한 기능을 달성하기 위해 반복자를 사용한다.

표 6.4는 우리의 (배열 및 노드) 리스트 ADT와

java.util 인터페이스 List 및 ListIterator 인터페이스 사이의 해당 메소드를 보여주며,

java.util 클래스 ArrayList 및 LinkedList에서의 구현에 대한 참고 사항이다.

표 6.4: 배열 리스트 및 노드 리스트 ADT의 메소드와

java.util 인터페이스 List 및 ListIterator 간의 대응.

java.util.ArrayList(또는 이것의 실행 시간)의 약어: A

java.util.LinkedList(또는 이것의 실행 시간)의 약어: L

List ADT Method	java.util List and ListIterator Method	Notes
size()	size()	O(1) time
isEmpty()	isEmpty()	O(1) time
get(i)	get(i)	A is O(1), L is O(min{i, n - i})
first()	listIterator()	first element is next
last()	listIterator(size())	last element is previous
prev(p)	previous()	O(1) time
next(p)	next()	O(1) time
set(p, e)	set(e)	O(1) time
set(i, e)	set(i, e)	A is O(1), L is O(min{i, n - i})
add(i, e)	add(i, e)	O(n) time
remove(i)	remove(i)	A is O(1), L is O(min{i, n - i})
addFirst(e)	add(0, e)	A is O(n), L is O(1)
addFirst(e)	addFirst(e)	only exists in L, O(1)
addLast(e)	add(e)	O(1) time
addLast(e)	addLast(e)	only exists in L, O(1)
addAfter(p, e)	add(e)	insertion is at cursor; A is O(n), L is O(1)
addBefore(p, e)	add(e)	insertion is at cursor; A is O(n), L is O(1)
remove(p)	remove()	deletion is at cursor; A is O(n), L is O(1)

6.4 리스트 ADT 및 컬렉션 프레임워크

이 절에서는 일반적인 리스트 ADT에 대해 논의하며,

여기서는 데크, 배열 리스트 및/또는 노드 리스트 ADT의 메소드를 결합한다.

그러한 ADT를 설명하기 전에 먼저,

우리는 그것들이 존재하는 더 큰 맥락에 대해 언급한다.

6.4.1 자바 컬렉션 프레임워크

자바는 자바 컬렉션 프레임워크(Java Collections Framework)를 정의하는

자료 구조 인터페이스와 클래스 패키지를 제공한다.

이 패키지인 java.util에는 이 책에서 설명한 여러 자료 구조의 버전이 포함되어 있으며,

그 중 일부는 이미 설명했고, 다른 일부는 이 책의 나머지 부분에서 설명한다.

특히 java.util 패키지에는 다음과 같은 인터페이스가 포함되어 있다:

Collection:
요소의 컬렉션을 포함하는 모든 자료 구조의 일반 인터페이스이다.

java.lang.Iterable을 확장하므로

이 집합에 있는 요소의 반복자를 반환하는

iterator() 메소드가 포함된다.

Iterator:
단순 반복자 ADT를 위한 인터페이스이다.

List:
컬렉션을 확장하여 배열 리스트 ADT를 포함하는 인터페이스 이 리스트에 대해

ListIterator 객체를 반환하는 메소드 listIterator도 포함되어 있다.

ListIterator:
리스트에 대한 순방향 및 역방향 순회와

커서 기반 업데이트 메소드를 모두 제공하는 반복자 인터페이스이다.

Map:
key를 value에 맵핑하기 위한 인터페이스.

이 개념과 인터페이스는 9.1절에서 설명한다.

Queue:
큐 ADT에 대한 인터페이스이지만 다른 메소드 이름을 사용한다.

메소드에는 peek()(front()과 동일), offer(e)(enqueue(e)와 동일), poll()(dequeue()와 동일)이 있다.

Set:
컬렉션을 세트로 확장하는 인터페이스이다.

자바 컬렉션 프레임워크에는

위와 같은 인터페이스의 다양한 조합을 구현하는 몇 가지 구체적인 클래스도 포함되어 있다.

하지만 여기서는 이러한 클래스를 일일이 열거하기보다는

이들을 좀 더 적절한 장소에서 논의한다.

그러나 지금 강조하고 싶은 한 가지 주제는

java.util.collection 인터페이스를 구현하는 모든 클래스가

java.lang.Iterable 인터페이스를 구현하므로

iterator() 메소드를 포함하고 for-each 루프에서 사용할 수 있다.

또한 java.util.List 인터페이스를 구현하는 모든 클래스에는

listIterator() 메소드도 포함되어 있다.

위에서 살펴본 바와 같이 이러한 인터페이스는

컬렉션이나 리스트의 요소를 반복하는 데 유용하다.

6.4.2 java.util.LinkedList 클래스

java.util.Linked List 클래스는

데크 ADT의 모든 메소드(섹션 5.3)와

배열 리스트 ADT의 모든 메소드(섹션 6.1)를 포함하여

많은 메소드를 포함하고 있다.

또한 앞서 언급한 바와 같이 리스트 반복자를 사용하여

노드 리스트 ADT와 유사한 기능도 제공한다.

java.util.LinkedList 클래스의 성능

java.util.LinkedList 클래스에 대한 설명서는

이 클래스가 이중 연결 리스트로 구현되었음을 분명히 한다.

따라서 연결 리스트 반복자의 모든 업데이트 메소드는 각각 O(1) 시간으로 실행된다.

마찬가지로 데크 ADT의 모든 메소드도

리스트를 업데이트하거나 쿼리하는 것이기 때문에

각각 O(1) 시간으로 실행된다.

그러나 배열 리스트 ADT의 메소드도

java.util.LinkedList에 포함되어 있으므로

일반적으로 이중 연결 리스트를 구현하는 데 적합하지 않다.

특히 연결 리스트는 요소에 대한 색인화된 접근을 허용하지 않으므로

get(i) 연산을 수행하여 주어진 인덱스 i에서 요소를 반환하려면

인덱스 i가 있는 요소를 저장하는 노드를 찾을 때까지

리스트의 끝 중 하나에서 위 또는 아래로 계산하여 링크 "호핑"을 수행해야 한다.

약간의 최적화를 위해 리스트의 더 가까운 끝에서 이 호핑을 시작하여

다음의 실행 시간을 달성할 수 있다
O(min(i + 1, n − i)),

여기서 n은 리스트에 있는 요소의 수이다.

이런 종류의 탐색에서 최악의 경우는 다음과 같다
r= n/2.
따라서 이 때 실행 시간은 여전히 O(n)이다.

add(i,e)와 remove(i) 연산도 링크 호핑을 수행하여

인덱스 i가 있는 요소를 저장하는 노드를 찾은 다음 노드를 삽입하거나 삭제해야 한다.

이러한 add(i,e) 및 remove(i) 구현의 실행 시간은

마찬가지로 O(min(i+1, n-i+1)), 즉 O(n))이다.

이 접근법의 한 가지 장점은

6.1.1절에 주어진 데크 ADT에 배열 리스트 ADT를 적용시키는 경우와 같이

i = 0 또는 i = n - 1이면

O(1) 시간에 add 및 remove를 실행한다는 것이다.

그러나 일반적으로 java.util.LinkedList 객체를 사용하는 배열 리스트 메소드는 비효율적이다.

6.4.3 수열

수열(sequence):

데크 ADT(섹션 5.3), 배열 리스트 ADT(섹션 6.1),

노드 리스트 ADT(섹션 6.2)의 모든 메소드를 지원하는 ADT

즉, 인덱스 또는 위치에 따라 리스트에 있는 요소에 명시적으로 접근할 수 있다.

또한 이러한 이중 접근 기능을 제공하므로,

우리는 또한 인덱스와 위치 간의 연결을 제공하는

다음 두 가지 "브릿지" 방법을 수열 ADT에 포함한다:

atIndex(i): 인덱스 i로 요소의 위치를 반환한다.

i < 0 또는 i > size() - 1인 경우 오류 조건이 발생한다.

indexOf(p): p 위치에 있는 요소의 인덱스를 반환한다.

수열 ADT에서 다중 상속

3개의 서로 다른 ADT로부터의 모든 메소드를 포함하는 것으로

수열 ADT의 정의는 다중 상속(multiple inheritance)의 예이다(섹션 2.4.2).

즉 수열 ADT는 3개의 "슈퍼" 추상 데이터 형식으로부터 메소드를 상속한다.

즉, 그 메소드에는 이러한 슈퍼 ADT의 메소드의 조합이 포함된다.

수열 ADT의 자바 인터페이스로서의 자바 사양은 코드 조각 6.18을 참조하라.

코드 조각 6.18: 다중 상속을 통해 정의된 수열 인터페이스.

Deque, IndexList, PositionList 인터페이스의 모든 메소드를 포함하며

(어떠한 일반 타입 E에 대해서도 정의됨) 두 가지 메소드를 더 추가한다.

/**
 * An interface for a sequence, a data structure supporting all
 * operations of a deque, indexed list and position list.
 */
public interface Sequence<E>
     extends Deque<E>, IndexList<E>, PositionList<E> {
  /** Returns the position containing the element at the given index. */
  public Position<E> atIndex(int r) throws BoundaryViolationException;
  /** Returns the index of the element stored at the given position. */
  public int indexOf(Position<E> p) throws InvalidPositionException;
}

배열을 사용한 수열 구현

만약 우리가 이중 연결 리스트로 수열 S ADT를 구현한다면,

java.util.LinkedList 클래스의 성능과 유사한 성능을 갖게 될 것이다.

그래서 대신 S의 각 요소 e를 배열 A의 셀 A[i]에 저장함으로써

수열 S를 구현하고자 한다고 가정한다.

이 경우, 우리는 인덱스 i와

배열 A에 대한 참조를 가지는 위치 객체 p를

인스턴스 변수로 정의할 수 있다.

그런 다음 단순히 A[i]를 반환함으로써 메소드 element(p)를 구현할 수 있다.

그러나 이 접근법의 주요 단점은 A의 셀이 해당 위치를 참조할 방법이 없다는 것이다.

따라서 addFirst 연산을 수행한 후

S의 기존 위치에 인덱스가 각각 1씩 상승했음을 알릴 방법이 없다

(수열의 위치는 항상 인덱스가 아닌 인접 위치에 상대적으로 정의됨을 기억하자).

따라서 배열로 일반적인 수열을 구현하려면 다른 접근법이 필요하다.

그렇다면 S의 요소들을 배열 A에 저장하는 대신

A의 각 셀에 새로운 종류의 위치 객체를 저장하고,

요소들을 위치에 저장하는 대안적 해결책을 생각해 보자.

새로운 위치 객체 p는 인덱스 i와 p와 관련된 요소 e를 유지한다.

그림 6.8과 같은 이 자료 구조를 사용하면

배열을 통해 쉽게 스캔하여

삽입 또는 삭제로 인해 인덱스가 변경되는

각 위치에 대한 인덱스 변수 i를 업데이트할 수 있다.

그림 6.8: 수열 ADT의 배열 기반 구현.

배열 기반 수열을 통한 효율성 절충

이 수열의 배열 구현에서

addFirst, addBefore, addAfter와 remove 메소드는 O(n) 시간이 소요되는데,

새 위치를 위한 공간을 만들기 위해 또는

(인덱스를 기반으로 한 insert 및 remove 메소드와 같이)

이전 위치의 제거로 생성된 구멍을 채우기 위해

위치 객체를 이동해야 하기 때문이다.

다른 모든 위치 기반 메소드는 O(1) 시간이 소요된다.

6.5 사례연구: 전진 이동 휴리스틱

각 요소가 접근되는 횟수를 추적하면서

요소의 컬렉션을 유지하고 싶다고 가정해 보겠다.

예를 들어, 이러한 접근 횟수를 유지하면

어떤 요소가 가장 인기 있는 "톱 10"에 속하는지 알 수 있다.

이러한 시나리오의 예로는

사용자가 방문하는 가장 인기 있는 웹 주소(또는 URL)를 추적하는 웹 브라우저 또는

사용자가 보는 가장 인기 있는 이미지의 리스트를 유지하는 사진 앨범 프로그램이 있다.

또한 즐겨찾기 리스트는

그래픽 사용자 인터페이스(GUI)에서

풀다운 메뉴에 사용되는 가장 인기 있는 버튼을 추적하고

가장 인기 있는 옵션을 포함하는 축약된 풀다운을 사용자에게 표시하는 데 사용될 수 있다.

풀다운(pull-down): 주로 화면 상단에서 아래로 내릴 때 나타나는 메뉴

따라서 이 절에서는 다음과 같은 메소드뿐만 아니라

size() 및 Empty() 메소드를 지원하는

즐겨찾기 리스트(favorite list) ADT를 구현하는 방법을 고려한다:

access(e):
e 요소에 액세스하여 액세스 수를 늘리고,

e 요소가 아직 존재하지 않는 경우 즐겨찾기 리스트에 추가한다.

remove(e):
e 요소가 이미 있는 경우 즐겨찾기 리스트에서 e 요소를 제거한다.

top(k):
가장 많이 접근한 요소의 반복 가능한 컬렉션을 반환한다.

6.5.1 정렬된 리스트 및 중첩 클래스 사용

코드 조각 6.19–6.20에서 고려하는 즐겨찾기 리스트의 첫 번째 구현은

FavoriteList 클래스를 구축하는 것이다.

FavoriteList 클래스:

접근 횟수를 늘리지 않고 순서대로 연결 리스트에 접근한 객체에 대한 참조를 저장하는 클래스

또한 둘러싸인 클래스 정의 내부에 관련된 중첩 클래스를 정의할 수 있는 자바의 기능을 사용한다.

이러한 중첩 클래스(nested class)는 static으로 선언되어야만

이 정의가 해당 클래스의 특정 인스턴스가 아닌 둘러싸인 클래스와 관련이 있음을 나타낼 수 있다.

중첩 클래스를 사용하면

외부 사용으로부터 보호할 수 있는

"도움말" 또는 "지원" 클래스를 정의할 수 있다.

이 경우 중첩 클래스 Entry는 리스트에 있는 각 요소 e에 대해 쌍 (c,v)을 저장한다.

c: e에 대한 접근 횟수

v: 요소 e 자체에 대한 값 참조

요소가 접근 될 때마다 연결 리스트에서 요소를 찾아 접근 카운트를 증가시킨다.

요소를 제거하는 것은 요소를 찾아서 연결 리스트에서 제거하는 것과 같다.

가장 많이 접근 된 k개의 요소를 반환하는 것은

단순히 내부에 연결된 리스트의 순서에 따라

'엔트리 값을 출력 리스트으로 복사하는 것을 포함한다.

코드 조각 6.19-6.20:

요소와 접근 횟수를 나타내는 중첩 클래스, Entry를 포함한

클래스 FavoriteList.

/** List of favorite elements, with their access counts. */
public class FavoriteList<E> {
  protected PositionList<Entry<E>> flist; // List of entries
  /** Constructor; O(1) time */
  public FavoriteList() { fList = new NodePositionList<Entry<E>>(); }
  /** Returns the number of elements in the list; O(1) time */
  public int size() { return fList.size(); }
  /** Returns whether the list is empty; O(1) time */
  public boolean isEmpty() { return fList.isEmpty(); }
  /** Removes a given element, provided it is in the list; O(1) time */
  public void remove(E obj) {
    Position<Entry<E>> p = find(obj);  // search for obj
    if (p != null)
       fList.remove(p);        // remove the entry
  }
  /** Increments the access count for given element and inserts it
    * if it not already present; O(n) time */
  public void access(E obj) {
    Position<Entry<E>> p = find(obj);  // find the position for obj
    if (p != null)
      p.element().incrementCount();   // increment access count
    else {
      fList.addLast(new Entry<E>(obj));  // add the new entry at the end
      p = fList.last();
    }
    moveUp(p);       // moves the entry to its final position
  }
  /** Finds the position of a given element, or return null; O(n) time */
  protected Position<Entry<E>> find(E obj) {
    for(Position<Entry<E>> p; fList.positions())
      if(value(p).equals(obj))
        return p;      // found at position p
    return null;     // not found
  }
  /** Moves up an entry to its correct position in the list;  O(n) time */
  protected void moveUp(Position<Entry<E>> cur) {
    Entry<E> e = cur.element();
    int c = count(cur);
    while (cur != fList.first()) {
      Position<Entry<E>> prev = fList.prev(cur);     // previous position
      if (c <= count(prev)) break;  // entry is at correct position
      fList.set(cur, prev.element());   //move down previous entry
      cur = prev;
    }
  }
  /** Returns the k most accessed elements, for a given k; O(1) time */
  public Iterable<E> top(int k) {
    if (k < 0|| k > size())
      throw new IIegalArgumentException("Invalid argument");
    PositionList<E> T = new NodePositionList<E>();  //top-k list
    for(Entry<E> e: fList) {
      if (i++ >= k)
        break;        // all the k entries have been added
      T.addLast(e.value());   //add one entry to the list
    }
    return T;
  }
  /** String representation of the favorite list */
  public String toString() { return fList.toString(); }
  /** Helper method that extracts the value of the entry at a given position */
  protected E value(Position<Entry<E>> p) P return (p.element()).value(); }
  /** Helper method that extracts the counter of the entry at a given position */
  protected E count(Position<Entry<E>> p) P return (p.element()).count(); }
  /** Inner class storing elements and their access counts. */
  protected static class Entry<E> {
    private E value;   // element;
    private int count;  // access count
    /** Constructor */
    Entry(E v) { count = 1; value = v; }
    /** Returns the element */
    public E value() { return value; }
    /** Returns the access count */
    public int count() { return count; }
    /** Increments the access count */
    public int incrementCount() { return ++count; }
    /** String representation of the entry as [count,value] */
    public String toString() { return "[" + count + "," + value + "]";}
  }
} // End of FavoriteList class

6.5.2 전진 이동 휴리스틱과 함께 리스트 사용

즐겨찾기 리스트의 이전 구현은

즐겨찾기 리스트의 e의 인덱스에 비례하여 access(e) 메소드를 시간적으로 수행한다.

즉, e가 즐겨찾기 리스트에서 k번째로 인기 있는 요소라면 접근은 O(k) 시간이 걸린다.

참조의 지역성(locality of reference):

수열 접근에서 한 번 접근되면 요소에 가까운 미래에 다시 접근할 가능성이 높은 것

ex) 웹 페이지에 대한 사용자의 방문을 통해 형성되는 것

휴리스틱: 경험의 법칙

전진 이동 휴리스틱(move-to-front heuristic):

접근 순서에 존재하는 참조의 지역성을 이용하려고 시도하는 휴리스틱이

휴리스틱을 적용하기 위해 요소에 접근할 때마다 요소를 리스트의 맨 앞까지 이동시킨다.

물론 우리의 희망은 이 요소가 가까운 미래에 다시 접근하는 것이다.

예를 들어 n개의 요소와 다음 n^2개의 연쇄적인 접근이 가능한 시나리오를 생각해 보자:

• 요소 1이 n번 접근됨
• 요소 2가 n번 접근됨
• ...
• 요소 n은 n번 접근된다.

접근 횟수에 따라 정렬된 요소를 저장하면 처음 접근할 때 각 요소를 삽입한다.
• 요소 1에 대한 각 접근은 O(1) 시간 내에 실행된다
• 요소 2에 대한 각 접근은 O(2) 시간 내에 실행된다
•...
• 요소 n에 대한 각 접근은 O(n) 시간 내에 실행된다.

따라서, 일련의 접근를 수행하기 위한 총 시간은

n + 2n + 3n+ ... n·n = n(1 + 2 + 3 + ...+n) = n · n · (n + 1)/2,

즉 O(n^3)에 비례한다.

반면에, 우리가 전진 이동 휴리스틱을 사용한다면,

각 요소를 삽입하면 처음에 접근할 때는
• 요소 1에 대한 각 접근에는 O(1) 시간이 걸린다
• 요소 2에 대한 각 접근에는 O(1) 시간이 걸린다
•...
• n 요소에 대한 각 접근은 O(1) 시간 내에 실행된다.

따라서 이 경우 모든 접근을 수행하기 위한 실행 시간은 O(n^2)이다.

따라서, 이 시나리오에 대한 접근 시간은 전진이동 구현이 더 빠르다.

그러나 이 이점은 대가를 치러야 한다.

자바에서 전진이동 휴리스틱 구현

코드 조각 6.21에서는 전진이동 휴리스틱을 사용하여 즐겨찾기 리스트를 구현한다.

새로운 클래스 FavoritListMTF를 정의하여 구현한다.

1) FavoriteList 클래스를 확장한다.

2) moveUp 메소드 재정의:

연결 리스트의 현재 위치에서 접근한 요소를 제거한 다음

이 요소를 다시 앞에 이 리스트에 삽입한다.

3) top 메소드 재정의:

moveUp 메소드 재정의보다 더 복잡하다.

휴리스틱의 전진이동에 따른 절충점

이제 더 이상 즐겨찾기 리스트를

그 값의 접근 횟수로 정렬된 항목의 리스트로 유지하지 않으므로,

가장 많이 접근한 k개의 요소를 찾으라는 요청을 받으면 검색해야 한다.

특히 메소드 top(k)를 다음과 같이 구현할 수 있다:

1. 좋아하는 리스트의 항목을 다른 리스트인 C에 복사하고

빈 리스트인 T를 만든다.
2. 리스트를 C번 스캔한다.

각 스캔에서 접근 횟수가 가장 많은 C의 엔트리를 발견하고,

이 엔트리를 C에서 제거한 후 T의 끝에 그 값을 삽입한다.
3. 리스트 T를 반환한다.

메소드 top의 이러한 구현은 O(kn) 시간이 걸린다.

따라서 k가 상수일 때 메소드 top은 O(n) 시간에 실행된다.

예시) "상위 10개" 리스트를 얻고 싶을 때

그러나 k가 n에 비례하면 상위는 O(n^2) 시간에 실행된다.

예시) "상위 25%" 리스트를 원할 때

그럼에도 불구하고, 전진 이동 접근 방식은

단순히 접근 횟수에 따라 선호 리스트를 순서대로 유지하는 것보다

앞으로 이동 접근 방식을 사용하는 것이 느린 접근 수열이 있기 때문에

휴리스틱 또는 경험의 규칙에 불과하다.

또한 상위 요소에 대한 보고가 더 느리기 위해

참조의 지역성을 갖는 접근 수행의 잠재적 속도를 상쇄한다.

6.5.3 즐겨찾기 리스트의 사용 가능성

코드 조각 6.22에서는 즐겨찾기 리스트 구현의 예제 응용 프로그램을 사용하여

가장 인기 있는 URL을 웹 페이지 접근의 시뮬레이션 순서로 유지하는 문제를 해결한다.

이 프로그램은 URL 집합을 내림차순으로 접근한 다음

시뮬레이션에서 접근한 가장 인기 있는 웹 페이지를 보여주는 창을 팝업한다.

코드 조각 6.21:

클래스 FavoriteListMTF는 전진 이동 휴리스틱을 구현한다.

이 클래스는 FavoriteList(코드 조각 6.19–6.20)를 확장하고

메소드 moveUp 및 top을 재정의한다.

public class FavoriteListMTF<E> extends Favorite<E> {
  /** Default consructor */
  public FavoriteListMTF() { }
  /** Moves up an entry to the first position; O(1) time */
  protected void moveUp(Position<Entry<E>> pos) {
    fList.addFirst(fList.remove(pos));
  }
  /** Returns the k most accessed elements, for a given k; O(kn) time */
  public Iterable<E> top(int k) {
    if (k < 0|| k > size())
      throw new IllegalArgumentException("Invalid argument");
    PositionList<E> T = new NodePosiitonList<E>(); // top-k list
    if (!isEmpty()) {
      // copy entries into temporary list C
      Position<Entry<E>> C = new NodePosiitonList<Entry<E>>();
      for (Entry<E> e: fList)
        C.addLast(e);
      // find the top k elements, one at a time
      for (int i = 0; i < k; i++) {
        Position<Entry<E>> maxPos = null;  // position of top entry
        int maxCount = -1;                 // access count of top entry
        for (Position<Entry<E>> p: C.positions()) {
          // examine all entries of C
          int c = count(p);
          if (c > maxCount) { // found an entry with higher access count
            maxCount = c;
            maxPos = p;
          }
        }
        T.addLast(value(maxPos));    // add top entry to list T
        C.remove(maxPos);            // remove top entry from list C
      }
    }
    return T;
  }
}

코드 조각 6.22: 웹 페이지 접근 수를 계산하기 위해

FavoriteList 및 FavoriteListMTF 클래스의 사용을 보여준다.

이 시뮬레이션은 여러 웹 페이지에 무작위로 접근한 다음

가장 인기 있는 페이지를 표시한다.

import java.io.*;
import javax.swing.*;
import java.awt.*;
import java.net.*;
import java.util.Random;
/** Example program for the FavoriteList and FavoriteListMTF classes */
public class FavoriteTester {
  public static void main(String[] args) {
    String[] urlArray = {"http://wiley.com", "http://datastructures.net",
                   "http://algorithmdesign.net", "http://www.brown.edu",
                   "http://www.uci.edu"};
    FavoriteList<String> L1 = new FavoriteList<String>();
    FavoriteListMTF<String> L2 = new FavoriteListMTF<String>();
    int n = 20; // number of access operations
    Random rand = new Random();
    for (int k = 0; k < n; k++) {
      System.out.println("----------------------------------------------");
      int i = rand.nexInt(urlArray.length);   // random index
      String url = urlArray[i];
      System.out.println("Accessing: " + url);
      L1.access(url);
      System.out.println("L1 = " + L1);
      L2.access(url);
      System.out.println("L2 = " + L2);
    }
    int t = L1.size()/2;
    System.out.println("----------------------------------------------");
    System.out.println("Top " + t + " in L1 = " + L1.top(t));
    System.out.println("Top " + t + " in L2 = " + L2.top(t));
    // Pop up a browser window displaying the most popular URL in L1
    try {
      String popular = L1.top(1).iterator().next(); // most popular URL in L1
      JEditorPane jep = new JEditorPane(popular);
      jep.setEditable(false);
      JFrame frame = new JFrame(popular);
      frame.getContentPane().add(new JScrollPane(jep), BorderLayout.CENTER);
      frame.setSize(640, 480);
      frame.setVisible(true);
    } catch (IOException e) { // ignore I/O exceptions
      }
  }
}

'프로그래밍 공부 > Data Structure' 카테고리의 다른 글

7장 트리(2) (1)	2023.12.30
7장 트리(1) (2)	2023.12.29
5장 스택과 큐 (1)	2023.12.20
4장 분석 도구 (1)	2023.12.19
3장 배열, 연결 리스트, 재귀(2) (1)	2023.12.17

hystarbit의 블로그

태그

최근글

댓글

공지사항

아카이브