[자바로 배우는 핵심 자료구조와 알고리즘] 4장 LinkedList 클래스

LinkedList 클래스

MyLinkedList 메서드 분류하기

indexOf 메서드 구현

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

• 보통 다음 Node가 null이 아닌지 확인해야 하지만, 이 경우에는 리스트 끝까지 가면 반복문이 종료되므로 안전
  • size 변수는 리스트의 실제 노드 개수와 일치한다고 가정
• 이 메서드의 증가 차수는?
  1. 반복마다 상수 시간인 equals 메서드를 호출함
     • 이 메서드는 target이나 data의 크기에는 의존하지만, 리스트의 크기에는 의존하지 않음
     • 반복문의 다른 연산 또한 상수 시간
  2. 반복은 n번 실행됨. 운이 없으면 전체 리스트를 순회할 수도 있기 때문
     => 이 메서드의 실행시간은 리스트의 크기에 비례(O(n))

두 개의 인자를 가진 add 메서드 구현

public void add(int index, E element) {
    if(index == 0) {
        head = new Node(element, head);
    } else{
        Node node = getNode(index - 1);
        node.next = new Node(element, node.next);
    }
    size++;
}

• 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 메서드의 증가 차수는 무엇?
  1. getNode 메서드가 indexOf와 유사하므로 같은 이유로 선형
  2. add 메서드에서 getNode 메서드 전과 후 모두가 상수 시간
     => 선형

remove 메서드 구현

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 메서드는 선형

MyArrayList와 MyLinkedList 비교하기

구분	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 클래스는 시작에 추가하고 시작에서 제거하는 연산에 이점이 있음
• 어느 구현이 나은지는 가장 자주 사용하는 연산으로 결정

프로파일

• 책 참고