ch3 ArrayList 클래스

[jeongabae]

3.1 MyArrayList 메서드 분류하기

• MyArrayList

  • get메서드

    public T get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    return array[index]; //---> O(1)
    }

    -get 메서드에 있는 모든 것은 상수 시간

  • set메서드

    public T set(int index, T element){
                    T old = get(index); 
        array[index] = element;
        return old; 
    }

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

  • indexOf 메서드

    public int indexOf(Object target) {
    for(int i=0; i<size; i++){ //
        if(equals(target, array[i])){
            return i; //이 목록에서 지정한 요소의 첫 번째 발생에 대한 인덱스를 반환
        }
    }
    return -1; //요소가 없는 경우 -1 반환
    }

    -메서드를 호출하므로 equals 메서드도 살펴보면

    private boolean equals(Object target, Object element) {
    if (target == null) {
        return element == null;
    } else {
        return target.equals(element);
    }
    }

    -indexOf 메서드는 선형.

  • remove 메서드

    public T remove(int index) {
    T element = get(index);
    
    for (int i=index; i<size-1; i++) {
        array[i] = array[i+1]; // 요소 옮기기
    }
    size--; //요소 제거해서 사이즈 감소
    return element;
    }

    -상수 시간인 get 메서드를 사용하고 index부터 배열에 반복문을 실행, ...-> remove 메서드는 선형으로 간주

3.2 add 메서드 분류하기

• add메서드

  public void add(int index, T element) {
      if (index < 0 || index > size) {
          throw new IndexOutOfBoundsException();
      }
      // 크기 조정을 통해 요소를 추가
      add(element);
  
      // 다른 요소를 시프트함
      for (int i=size-1; i>index; i--) {
          array[i] = array[i-1];
      }
      // 올바른 자리에 새로운 값을 넣음
      array[index] = element;
  }

  public boolean add(T element) {
      if (size >= array.length) {
            //큰 배열을 만들어 요소들을 복사
          T[] bigger = (T[]) new Object[array.length * 2];
          System.arraycopy(array, 0, bigger, 0, array.length);
          array = bigger;
      }
      array[size] = element;
      size++;
      return true;
  }

  add(int,T)는 선형

3.2 문제 크기

• removeAll 메서드

  public boolean removeAll(Collection<?> collection) {
      boolean flag = true;
      for (Object obj: collection) {
          flag &= remove(obj);
      }
      return flag;
  }

  collection의 요소가 m개고 제거할 리스트에 요소가 n개 있다면 이 메서드는 O(nm) 일반적으로 collection이 제거할 리스ㅡㅌ에 있는 요소의 1%를 포함한다면 removeAll 메서드는 이차

3.4 연결 자료구조

• 노드에 대한 클래스 정의

  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() + ")";
  }
  }

  새로운 리스트를 만드는 방법 방법1. ListNode 객체의 집합을 생성 후, 연결 방법2. 노등와 링크를 동시에 생성

[jeongabae]

3.5 실습3