[JAVA로 배우는 자료구조] 분할 상환 분석과 LinkedList

1. 분할 상환 분석(Amortized Analysis)

정체되었던 자료구조 공부를 O'REILLY에서 출판한 [JAVA로 배우는 자료구조]를 보며 다시 이어나가려 합니다. Bio-O시간 복잡도 기법 중 분할 상환 분석(Amortized Analysis)는 극단의 값을 평균으로 절충해 시간 복잡도를 도출하는 분석 기법입니다. 책에서 영문 위키를 링크로 주석 첨부해 봤더니 The amortized analysis considers both the costly and less costly operations... 라는 문장이 나옵니다. 호출 시간이 짧게 반환되거나 길게 반환될 때를 평균치로 계산해야 효율적이기 때문에 나온 기법이 분할 상환 분석인 것입니다.

2. LinkdedList

LinkdedList는 List 인터페이스에서 파생된 자료구조입니다. 리스트 안에는 객체로 된 노드들이 연결되어 있는데 인자값(data)와 다음 노드의 참조값(next) 변수를 가지고 있습니다. Array나 List와 다르게 참조값이 있고 앞뒤 순서가 자유롭기 때문에 생소한 개념입니다. 이런 특징 덕분에 삽입, 삭제가 자유롭다는 장점이 있고 속도면에선 느린 단점이 있습니다. 

LinkdedList 메서드 중 indexOf 코드를 완성하는 예제가 있었는데 틀렸습니다. get 메서드를 사용해 data 구현까진 했는데 반복문을 돌면서 왜 node = node.next를 설정하는지 모르겠습니다. 내일 알아볼 예정입니다.

    @Override
    public int indexOf(Object target) {
        //TODO: FILL THIS IN!
        Node node = head;
        for (int i = 0; i < size; i++) {
            if(equals(target, get(i))) {
                return i;
            }
            node = node.next;
        }
        return -1;
    }