LinkedList 클래스 & 가비지 컬렉션

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

 

다음 소스코드를 살펴보자. (MyLinkedList.java)

public class MyLinkedList<E> implements List<E> {

    private int size; // 요소의 개를 추적합니다
    private Node head; // 첫 번째 노드에 대한 참조입니다

    public MyLinkedList() {
        head = null;
        size = 0;
    }

주석에 나와 있는 대로 size 변수는 MyLinkedList에 있는 요소 개수를 추적하고, head 변수는 리스트의 첫 번째 노드를 참조하거나 리스트가 비었으면 null이다.

 

요소 개수를 꼭 저장할 필요는 없다. 그리고 일반적으로 중복 정보를 유지하는 것은 위험한데, 정보를 올바르게 갱신하지 않으면 리스트를 순회하여 요소 개수를 세는 선형 시간이 필요하다.

 

size 변수를 명시적으로 저장하므로 요소를 더하거나 제거할 때마다 갱신해야 한다. 이에 따라 메서드가 약간 느려지지만, 증가 차수를 변경하지 않으므로 그만한 가치가 있다. 

 

생성자는 head 변수를 null로 만들어 빈 리스트임을 알려준다. size 변수는 0으로 설정한다.

 

public boolean add(E element) {
    if (head == null) {
        head = new Node(element);
    } else {
        Node node = head;
        // 마지막 노드까지 반복합니다
        for (; node.next != null; node = node.next) {}
        node.next = new Node(element);
    }
    size++;
    return true;
}

이 add 메서드는 두 가지 패턴을 보여준다.

1. 많은 메서드에서 리스트의 첫 번째 요소를 특별한 경우로 처리해야 한다. 이 예제에서는 리스트에 첫 번째 요소를 추가하면 head 변수를 변경해야 한다. 그렇지 않으면 리스트를 순회하여 끝을 찾아 새로운 노드를 추가해야 한다.
2. add 메서드는 for 문으로 리스트에 있는 노드를 순회하는 방법을 보여준다.반복문에 앞서 node를 선언해야 반복이 끝난 후 접근할 수 있음에 주의해라. 

앞에 MyArrayList 클래스는 필요하면 배열이 늘어나지만 결코 줄어들지는 않는다. 배열은 가비지 컬렉션을 하지 않고 그 요소도 리스트 자체가 파괴될 때 까지 가비지 컬렉션(garbage collection) 대상이 아니다.

 

연결 리스트 구현의 한 가지 장점은 요소를 제거하면 리스트 크기가 줄어들고 사용하지 않는 노드는 즉시 가비지 컬렉션이 될 수 있다는 것이다.

 

public void clear() {
	head = null;
    size = 0;
}

clear 메서드 코드이다. head 변수를 null로 만들면 첫 번째 Node에 대한 참조를 제거한다. 해당 Node에 대한 다른 참조가 없다면(당연히 없어야 한다.) 가비지 컬렉션을 한다. 이때 두 번째 Node에 대한 참조가 제거되고 이것도 가비지 컬렉션을 한다. 이 절차는 모든 노드를 가비지 컬렉션할 때까지 계속된다.

 

clear 메서드는 어떻게 분류할까? 이 메서드 자체는 두 개의 상수 시간 연산을 포함하므로 상수 시간으로 보인다. 하지만 이것을 호출할 때는 요소의 개수에 비례하여 가비지 컬렉터가 동작한다. 따라서 선형으로 간주해야 한다.

 

이것이 때때로 성능 버그(performance bug)라고 불리는 예이다. 올바른 일을 한다는 점에서는 정확한 프로그램이지만, 증가 차수는 기대한 만큼 나오지 않는다. 자바와 같은 언어는 가비지 컬렉션처럼 뒷단에서 많은 일을 하기 때문에 이런 종류의 버그를 찾아내기가 어렵다.