목표
- ArrayList의 특징을 이해한다.
- 접근, 검색, 추가, 삭제를 위한 시간 복잡도가 어떻게 도출되는지 이해한다.
ArrayList
ArrayList는 내부가 배열(Array)형태로 된 List이다.
ArrayList는 List인데 연속된 메모리 공간을 차지하는 Array의 형태를 가지고 있다. 따라서 특정원소에 Index를 이용해 접근이 가능하다.
ArrayList는 List의 성질인 가변성을 위해서 ArrayList는 <그림1>과 같이 처음부터 일정량의 메모리 공간을 잡고 들어간다.
만약 <그림2와> 같이 List에 인스턴스가 더해져 메모리 공간이 모두 찬다면 다시 해당 메모리 공간보다 더 큰 메모리 공간을 잡아 기존 객체를 복사한 다음 연산을 이어간다.
예를 들면 하나의 메모리 공간만 필요한데 향후 값이 추가될 것을 대비해서 10개의 공간을 잡는 것이다. 이후 값이 추가되면 남은 9개의 메모리 공간을 이용해서 값을 추가한다. 9개의 원소가 더해져 공간이 모두 찬다면 새로운 20개의 공간을 잡아 기존 10개의 메모리 공간을 복사한다.
시간 복잡도
접근
ArrayList는 연속적인 공간을 차지하므로, 특정한 특정한 위치의 변수에 대한 Random access가 가능해 접근에 대한 속도가 빠르다. 찾고자 하는 원소의 위치만 안다면 O(1)의 시간 복잡도로 접근이 가능하다.
*mutableListOf는 ArrayList를 생성한다.
val mutableList = mutableListOf<Int>(1, 2, 3, 4, 5, 6)
mutableList[3] // 4특정 원소 접근에 대한 시간 복잡도 : O(1)
검색
크기 N의 ArrayList에서 검색을 하기 위해서는 O(N)의 시간 복잡도가 필요하다. 하나하나 확인을 하며 찾아가야 하기 때문이다.
val mutableList = mutableListOf<Int>(1, 2, 3, 4, 5, 6)
for (i in 0..mutableList.size)
if(mutableList[i] == 4)
println(i)
// 3검색에 대한 시간 복잡도: O(N)
코틀린에서는 검색을 위한 다양한 확장함수를 제공해준다. 하나하나 확인하면서 즐거움을 느끼도록 하자.
val mutableList = mutableListOf<Int>(1, 2, 3, 4, 5, 6)
println(mutableList.find { it == 4 } ) // 4 있을 때만 자기 자신 반환 없으면 null 반환
추가
ArrayList에는 추가할 수 있다. <그림3>과 같이 기존 Array는 연속적인 공간을 차지하기 때문에 다음 공간이 비어있을지 알 수 없기 때문에 값을 추가할 수 없었다. 하지만, ArrayList는 항상 여유 공간을 두고 있기 때문에 값의 추가가 가능하다.
예를 들어 <그림4>와 같이 크기가 10인 ArrayList에 9개의 원소가 채워져 있다고 해보자. 여기에 10을 더하기 위해서는 단순히 10번째 원소에 추가하는 작업만 하면 된다. 따라서 ArrayList에 값을 추가하는 것은 O(1)의 시간 복잡도를 가진다.
ArrayList에 추가를 하는 시간 복잡도 : O(1)
그렇다면 ArrayList에 여유공간이 없을 때는 어떻게 해야할까? ArrayList는 값을 추가하기 위해 조금 소모적이지만 유용한 방법을 사용한다.
바로 <그림6>과 같이 기존 공간을 사용하지 않고 더 큰 메모리를 잡은 후 기존 메모리의 복사를 통해 크기를 늘리는 것이다. 이 때 항상 여유 메모리를 두고 메모리를 추가한다. 이러한 ArrayList의 특성 때문에 값이 자주 변경되어야 할 때는 ArrayList를 사용하는 것이 좋지 않다.
val mutableList = mutableListOf<Int>(1, 2, 3, 4, 5, 6) // 메모리 공간을 10만 잡음
mutableList[3]
mutableList.addAll(listOf(4, 5, 6, 7, 8, 9, 10, 11)) // 메모리 공간 20으로 늘리고 값을 더함
삭제
ArrayList는 기존 공간을 사용하면서 원소를 삭제하는 것이 가능하다. 바로 arrayCopy를 이용하는 방법이다. 아래 <그림5>를 참고하자
예를 들어 1..10의 원소를 가진 ArrayList가 있다고 했을 때 이중 1을 제거하기 위해서는 2..10을 앞으로 땡겨오는 방법을 사용한다. 이러한 과정을 통해 원소 삭제 시 Index가 유효하게 유지된다.
따라서 크기 N의 ArrayList에서 삭제를 하기 위해서는 O(N)의 시간 복잡도가 필요하다.
삭제를 위한 시간 복잡도 : O(N)
