[Kotlin] 자료구조 1 (배열, 스택, 큐, 링크드리스트)

[Java] array(배열)과 arrayList(리스트)의 차이(arrayList는 어떻게 동적으로 늘어나는가?)

배열

장점: index 를 통해 아이템에 바로 접근가능

단점: 아이템의 추가, 삭제가 느리다.

크기 변경: 불가

• Size 초과시 새 배열에 복사해야 된다.

메모리 사용량: 아이템의 값만 저장하므로 메모리 사용량이 비교적 작다.

• 크기가 5이고 요소가 2개일 경우 나머지 공간은 낭비될 수 있다.

시간 복잡도:

• 접근: Random Access - O(1)
• 추가, 삭제:
  • 맨 뒤에 삭제 - O(1)
  • 맨 뒤에 추가 - O(1)
    • 배열은 크기가 고정이므로 새 배열에 복사해야됨
  • 맨 앞 또는 중간에 추가, 삭제 - O(N)
    • 추가, 삭제후 데이터를 한칸씩 밀어야 하므로 최대 n번 순회