LinkedList 클래스 2

>>>>>>> 소스코드.git

 

indexOf 메서드를 살펴보자. (MyLinkedList.java)

public int indexOf(Object target) {
    Node node = head;
    for (int i = 0; i < size; i++) {
        if (equals(target, node.cargo)) {
            return i;
        }
        node = node.next;
    }
    return -1;
}

초기에 node 변수는 head의 사본을 얻는다. 따라서 둘은 같은 Node를 참조한다. 반복문 변수인 i는 0에서 size-1까지 반복한다. 각 반복에서 equals 메서드를 호출하여 목적 값을 찾았는지 확인한다. 찾았다면 i를 즉시 반환하고 그렇지 않으면 다음 Node로 넘어간다.

 

보통 다음 Node가 null인지 아닌지 확인해야 하지만, 이 경우에는 리스트 끝까지 가면 반복문이 종료되므로 안전하다(size 변수는 리스트의 실제 노드 개수와 일치한다고 가정한다). 목적 값을 찾지 못하면 -1을 반환한다.

 

그럼 이 메서드의 증가 차수는?

1. 반복마다 상수 시간인 equals 메서드를 호출한다(이 메서드는 target이나 data의 크기에는 의존하지만, 리스트의 크기에는 의존하지 않는다). 반복문의 다른 연산 또한 상수 시간이다.
2. 반복은 n번 실행된다. 운이 없으면 전체 리스트를 순회할 수도 있기 때문이다.

따라서 이 메서드의 실행시간은 리스트의 크기에 비례(O(n))한다.

 

public void add(int index, E element) {
    // no need to check bounds; getNode does it.
    if (index == 0) {
        head = new Node(element, head);
    } else {
        Node node = getNode(index - 1);
        node.next = new Node(element, node.next);
    }
    size++;
}

다음은 두 개의 인자를 가진 add 메서드의 구현이다. index가 0이라면 새로운 Node 객체를 시작에 추가한다. 이것은 특별한 경우로 처리된다. 그렇지 않으면 리스트를 순회하여 index-1 위치에 있는 요소를 가져온다. 이때 getNode라는 헬퍼 메서드를 사용한다.

private Node getNode(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    Node node = head;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

getNode 메서드는 index가 범위 밖에 있는지 확인한다. 범위 밖에 있다면 에외를 던지고, 아니라면 리스트를 순회하여 요청한 Node 객체를 반환한다.

 

다시 add 메서드로 돌아가서 올바른 Node 객체를 찾으면 새로운 Node 객체를 생성하고 이를 node 객체와 node.next 객체 사이에 넣는다. 

 

그러면 add 메서드의 증가 차수는 무엇일까?

1. getNode 메서드가 indexOf 메서드와 유사하므로 같은 이유로 선형이다.
2. add 메서드에서 getNode 메서드 전과 후 모두가 상수 시간이다.

따라서 add 메서드는 선형이다.

 

public E remove(int index) {
    E element = get(index);
    if (index == 0) {
        head = head.next;
    } else {
        Node node = getNode(index - 1);
        node.next = node.next.next;
    }
    size--;
    return element;
}

마지막으로 remove 메서드이다. get 메서드를 호출하여 index에 있는 요소를 찾고 저장한 다음 index를 포함한 Node 객체를 제거한다.

 

index 변수가 0이면 다시 특별한 경우로 처리한다. 그 외에는 index-1 위치에 있는 노드를 찾아 node.next 객체는 건너뛰고 node.next.next 객체로 직접 연결하도록 코드를 수정한다. 이렇게 하면 node.next 객체를 리스트에서 효과적으로 제거하고 가비지 컬렉션도 수행할 수 있다.

 

마지막으로 size 변수를 줄이고 처음에 찾은 요소를 반환한다.

 

그러면 remove 메서드의 증가 차수는 무엇일까? remove 메서드의 모든 것은 선형인 get과 getNode 메서드를 제외하면 상수 시간이다. 따라서 remove 메서드는 선형이다.

 

이렇게 두 개의 선형 메서드를 보면 때때로 결과를 이차로 생각하지만, 이것은 어떤 연산이 다른 연산 내부에 중첩되었을 때만 해당한다. 어떤 연산에 이어 다른 연산을 호출하면 실행시간은 더해진다. 이 연산이 둘 다 O(n)이라면 합 또한 O(n)이 된다.

 

---

MyArrayList와 MyLinkedList 비교하기

다음 표는 MyArrayList와 MyLinkedList 클래스의 비교를 요약한 것이다. 1은 O(1) 또는 상수 시간을 의미하고, n은 O(n) 또는 선형을 의미한다.

 

구분	MyArrayList	MyLinkedList
add(끝)	1	n
add(시작)	n	1
add(일반적으로)	n	n
get/set	1	n
indexOf/lastIndexOf	n	n
isEmpty/size	1	1
remove(끝)	1	n
remove(시작)	n	1
remove(일반적으로)	n	n

MyArrayList 클래스는 끝에 추가하고 끝에서 제거하고 get과 set메서드 연산에 이점이 있다. MyLinkedList 클래스는 시작에 추가하고 시작에서 제거하는 연산에 이점이 있다. 다른 연산에서는 두 구현의 증가 차수가 같다.

 

어느 구현이 나은지는 가장 자주 사용하는 연산으로 결정된다. 이것이 자바에서 한 개 이상의 구현 클래스를 제공하는 이유이기도 하다. 사용 예에 따라 유용한 클래스가 다르다.