[자료구조] 가변크기 배열(ArrayList, StringBuilder)

ArrayList와 가변크기 배열

동적가변크기 배열: 입력된 데이터에 따라 동적으로 크기가 변하는 배열

삽입, 삭제 시간복잡도

• 일반적으로는 O(1)

• 배열의 용량이 꽉 찼을때

  • 어레이 리스트는 기존보다 2배 더 큰 배열을 생성하고 이전 배열의 모든 원소를 새 배열로 복사한다.
  • O(2N) = O(N)

• 전체 삽입 시간은?

  • 상환시간 ---> 분할 상환분석 --->O(1)

StringBuilder

문자열 리스트가 주어졌을 때, 하나의 문자열로 이어붙이려고 한다. 이때의 수행시간은?

len(str_list) = n, len(tmp) = x 일때

String str = ''
for tmp in str_list:
  str = str + tmp
  
return str

시간복잡도

하지만 StringBuilder를 사용하면 필요한 경우에만 문자열을 복사하여 시간복잡도를 크게 단축할 수 있다.

StringBuilder str = new StringBuilder()
for tmp in str_list:
  str.append(tmp)

return str

String, StringBuilder와 StringBuffer

• String

  • 변경 불가능(immutable) 수정해야할 경우 새로 생성해야한다. O(N)
  • literal 방식으로 생성되면 그 인스턴스의 메모리 공간은 절대 변하지 않는다
    • String str = "hihihi";
  • 사용 적절한 경우
    • 문자열 연산이 적고 자주 조회해야하는 경우
    • 멀티쓰레드 환경

• StringBuilder(동기화 지원안함)

  • 변경 가능(mutable)하다
  • new 방식으로 생성되며 인스턴스의 메모리 공간은 가변가능하다
  • 변경가능한 문자열이지만 synchronization이 적용되지 않았다.
  • 사용 적절한 경우
    • 문자열 연산이 많은 경우
    • 싱글쓰레드 환경, 또는 멀티쓰레드 환경이어도 굳이 동기화가 필요 없는 경우

• StringBuffer(동기화 지원함)

  • Thread-safe, multiple thread환경에서 안전한 클래스
  • 비동기적으로 동작한다
  • 사용 적절한 경우
    • 문자열 연산이 많은 경우
    • 멀티쓰레드 환경

참고 블로그