Array와 ArrayList의 차이

Array란?

크기가 고정적이며 연속적, 순차적으로 데이터 저장

시간복잡도

• 접근: O(1)
  • 랜덤 엑세스
    

    💡 랜덤 액세스란? - 데이터 구조에서 원하는 위치에 직접 접근할 수 있는 방식 - 예) 배열의 주소와, 데이터 크기, 인덱스 번호를 알고 있으면 해당 블럭으로 바로 참조 가능

• 탐색: O(N)
• 삽입: O(N)
  • 해당 자리 이후 데이터를 전부 뒤로 미루고
    해당 자리에 데이터 덮어쓰기
• 삭제: O(N)
  • 해당 자리 데이터 지우고
    해당 자리 이후 데이터 전부 앞으로 땡기기
• 잦은 삭제와 추가가 발생하는 경우, Array 요소들을 이동시켜야 하기 때문에 오버헤드 발생

 

ArrayList란?

배열의 크기를 동적으로 다룰 수 있는 자료구조

• 시간 복잡도는 Array와 동일
• 데이터의 크기가 불확실할 때 좋음 (추가, 삭제 용이)