ArrayList 클래스

상수 시간

 

상수 시간

인덱스가 유효하지 않으면 예외를 던지는 get 메서드를 호출.

get 메서드 호출을 포함한 set 메서드의 모든 것은 상수 시간.

 

단일 인자 버전 메서드인 add(E)를 호출하고 add(E) 메서드는 새로운 인자를 마지막에 넣습니다. 

그다음 다른 요소를 오른쪽으로 이동시키고 올바른 자리에 새로운 요소를 넣습니다.

 

일련의 호출에서 평균 시간을 계산하는 알고리즘 분류 방법을 분할 상환 분석이라고 합니다. 핵심 개념은 일련의 호출을 하는 동안 배열을 복사하는 추가 비용이 분산되거나 분할 상환되었다는 것입니다. 

 

add(E) 메서드가 상수 시간이라면 add(int, E) 메서드는 어떨까요? add(E) 메서드를 호출한 후에 배열 일부에 반복문을 실행하고 요소를 시프트합니다. 이 반복문은 리스트의 끝에 요소를 추가하는 특별한 경우만 제외하면 선형입니다.

 

반복문이 한 개라면 알고리즘은 보통 선형입니다. 반복문 두 개가 중첩되었다면 이 알고리즘은 보통 이차입니다. 

하지만, 반복 횟수가 항상 n에 비례하지 않는다면 좀 더 고민해봐야 합니다. 

 

연결 자료구조

자료구조가 연결되었다함은 노드라는 객체들이 다른 노드에 대한 참조를 포함한 형태로 저장된 것을 의미합니다. 연결 리스트에서 각 노드는 리스트의 다음 노드에 대한 참조를 포함합니다. 

 

package com.allendowney.thinkdast;

/**
 * @author downey
 *
 */
public class ListNode {

   public Object data;
   public ListNode next;

   public ListNode() {
      this.data = null;
      this.next = null;
   }
   
   public ListNode(Object data) {
      this.data = data;
      this.next = null;
   }
   
   public ListNode(Object data, ListNode next) {
      this.data = data;
      this.next = next;
   }
   
   public String toString() {
      return "ListNode(" + data.toString() + ")";
   }
}

ListNode node1 = new ListNode(1);

ListNode node1 = new ListNode(2);

ListNode node1 = new ListNode(3);

 

node1.next = node2;

node2.next = node3;

node3.next = null;

 

ListNode node0 = new ListNode(0, node1);

 

<가비지 컬렉션>

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