ch4 LinkedList 클래스

[jeongabae]

4.1 MyLinkedList 메서드 분류하기

• indexOf 메서드

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

  indexOf메서드의 증가 차수?

  1. 반복마다 상수 시간인 equals메서드를 호출. 반복문의 다른 연산또한 상수 시간
  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++;
  }

• 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;
  }

  add 메서드의 증가 차수?

  1. getNode 메서드는 선형
  2. add메서드에서 getNode메서드 전과 후 모두가 상수 시간 ---> add 메서드는 선형

• 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 메서드의 증가 차수? remove 메서드의 모든 것은 선형인 get과 getNode 메서드를 제외하면 상수시간. ---> remove 메서드는 선형

[jeongabae]

4.2 MyArrayList와 MyLinkedList 비교하기

• MyArrayList
  • 끝에 추가, 제거 / get과 set 메서드 연산에 이점.
• MyLinkedList
  • 시작에 추가, 제거

*** 다른 연산에서는 두 구현의 증가 차수가 같음

[jeongabae]

4.3 프로파일

• Profiler 클래스
  • 문제 크기의 범위를 인자로 받아 실행하는 코드를 포함하며 실행시간을 측정하고 결과를 그래프에 출력.
  • Timeable 객체 생성해야함
  • set메서드 - 빈 리스트 생성
  • timeMe 메서드 - n개의 요소 추가
  • Profiler 객체 생성
  • Timeable 객체를 사용하는 timingLoop 메서드 제공
  • timingLoop 메서드 인자 (인자1) startN - 시간 측정을 시작하는 n 값 (인자2) endMillis - 밀리 초 단위로 임계치(threshold)를 지정.(임계치를 넘으면 timingLoop 메서드 중단됨)

[jeongabae]

4.4 결과 해석하기

....?