첫 시작은 Stack을 직접 구현해보는 것이었는데 어쩌다보니 ArrayList를 직접 구현해보는 중
그 다음은 LinkedList를 할 예정이다! 움하하
일단 ArrayList를 구현하게 된 계기는 ArrayList와 LinkedList의 차이에 대해 서칭해보던 중 한 블로그를 발견했다.
그 글은 ArrayList에 대한 설명이었는데, 글 가장 하단에는 ArrayList를 직접 구현해보셨다는 문장을 보고 해보고싶어져서 해보았다.
List interface 작성
interface MyList {
fun get(index: Int): Int
fun add(element: Int)
fun add(index: Int, element: Int)
fun remove(element: Int): Int
fun remove(index: Int, element: Int): Int
fun indexOf(element: Int): Int
fun lastIndexOf(element: Int): Int
fun size(): Int
}
List 했을 때 떠오르는 기능들을 먼저 작성했다. (사실 List에 있는 내용이다)
가장 먼저 쉽게 Int로만 데이터를 취급했고, 그 이후에는 제네릭을 통해 다양한 데이터 타입을 받도록 수정할 예정이다.
Test 작성
class MyArrayListTest {
@Test
fun `원소 1개를 추가할 수 있다`() { ... }
@Test
fun `원소 1개를 가장 맨 앞에 추가할 수 있다`() { ... }
@Test
fun `원소 1개를 리스트 중간에 추가할 수 있다`() { ... }
@Test
fun `꽉 찬 배열에서 1개의 원소를 추가할 수 있다`() { ... }
@Test
fun `원소를 통해 리스트 내 인덱스를 구할 수 있다`() { ... }
@Test
fun `존재하지 않은 원소를 찾는 경우 예외가 발생한다`() { ... }
}
테스트를 작성한 이유는 .. 하나하나 실행을 돌려서 데이터를 입력하는 반복작업을 줄이기 위해서이긴하지만 생각지못했던 부분까지 구현해 볼 수 있도록 한 것도 있다 ..
현재 글쓰는 시점에는 데이터 추가, 데이터의 인덱스 구하기까지 구현을 완료했다.
MyList의 구현체 클래스, MyArrayList
class MyArrayList(initialCapacity: Int = 0) : MyList {
private var elementData: Array<Int> = if (initialCapacity == 0) Array(DEFAULT_CAPACITY) { 0 } else Array(initialCapacity) { 0 }
private var size = 0
...
fun printList() {
for (i in 0..< size) {
println(elementData[i])
}
}
companion object {
private const val DEFAULT_CAPACITY = 5
}
}
MyList를 구현하고 있는 MyArrayList 클래스이다!
기본적으로 물리적인 공간을 5정도로 잡아놓았고, 생성자를 통해 capacity를 전달받도록 하였다.
그리고 리스트 원소들을 출력해보기 위해 printList() 도 추가해주었다.
elementData는 MyArrayList 안에서 조작하는 배열이다.
데이터를 추가하면 elementData 배열에 추가되고, 이를 반환하여 사용자에게 보여주는 형식
size는 elementData의 물리적인 크기(capacity)가 아닌 진짜 데이터가 들어있는 크기를 나타낸다.
그래서 데이터를 넣을 때마다 size를 1씩 올려주어야 한다! (물론 삭제한다면 1씩 빼주어야 한다.)
구현한 함수
add(index: Int, element: Int)
override fun add(index: Int, element: Int) { ... }
add(element: Int)는 맨 마지막에 데이터를 넣는 것이라 금방금방 구현을 했다면 사용자가 원하는 위치에 데이터를 넣는 것은 조금 어려웠다. 어려웠다는 것이 구현이 어렵다기보다는 어떻게 해야 더 좋은 방법일까?에 고민했던 것 같다. 그리고 다른 방법으로는 할 수 없나?도
일단 고려할 수 있는 부분을 if문으로 나누어보았다.
1) elementData에 추가적인 데이터를 넣을 수 있는지?
1-1) 넣을 수 있다면, 해당 index에 넣기
1-2) 넣을 수 없다면, elementData의 크기보다 하나 더 큰 새로운 배열을 만들기
2) index가 0인지? (가장 맨 앞인지)
2-1) 0이라면 가장 맨 앞에 넣고, 그 이후에 기존의 배열을 옮겨준다.
2-2) 0이 아니라면 ..
1️⃣ 첫번째 구현 : 맨 앞에 데이터를 추가하는 경우
override fun add(index: Int, element: Int) {
// elementData에 물리적인 공간(capacity)이 존재할 때
if (size.plus(1) < elementData.size) {
val newArrayList = Array(size+1) { 0 }
var newSize = 0
// 맨 앞에 원소를 추가
if (index == 0) {
newArrayList[index] = element
newSize++
for (i in 0..< size) {
newArrayList[newSize++] = elementData[i]
}
elementData = newArrayList
size = newSize
} else {
// 중간에 원소를 추가
...
}
} else {
// elementData에 물리적인 공간(capacity)이 존재하지 않을 때 -> 배열의 크기를 증가시켜야 함
...
}
}
새로운 데이터들을 담기 위해 가장 먼저 newArrayList라는 새로운 배열을 생성해주었다.
가장 맨 앞에 데이터를 추가하는 부분을 구현하였기 때문에 index = 0에 데이터를 추가하고, for문을 통해 기존의 배열 데이터들을 newArrayList에 넣어주었다.
그리고 elementData 변수가 기존 배열의 메모리주소가 아닌 새로운 newArrayList 배열의 메모리주소를 가지도록 할당해주었다.
2️⃣ 두번째 구현 : 중간에 데이터를 추가하는 경우
override fun add(index: Int, element: Int) {
// elementData에 물리적인 공간(capacity)이 존재할 때
if (size.plus(1) < elementData.size) {
val newArrayList = Array(size+1) { 0 }
var newSize = 0
// 맨 앞에 원소를 추가
if (index == 0) { ... } else {
// 중간에 원소를 추가
(0..<index).forEach {
newArrayList[newSize++] = elementData[it]
}
newArrayList[newSize++] = element
(index.plus(1)..<size).forEach {
newArrayList[newSize++] = elementData[it]
}
elementData = newArrayList
}
size = newSize
} else {
// elementData에 물리적인 공간(capacity)이 존재하지 않을 때 -> 배열의 크기를 증가시켜야 함
...
}
}
가장 먼저 들었던 생각은 index를 기점으로
1) index 앞 데이터를 새로운 배열에 저장하고
2) index에 맞게 데이터를 넣고
3) index 후 데이터를 다시 index 이후에 넣어주면 되겠다.
그런데 이렇게 2개의 for문으로 작성하는 것이 맞을까? 이게 괜찮은 방법일까? 하는 의문이 들었다.
3️⃣ 세번째 구현 : 중간에 데이터를 추가하는 경우 -2
override fun add(index: Int, element: Int) {
// elementData에 물리적인 공간(capacity)이 존재할 때
if (size.plus(1) < elementData.size) {
val newArrayList = Array(size+1) { 0 }
var newSize = 0
// 맨 앞에 원소를 추가
if (index == 0) { ... } else {
// 중간에 원소를 추가
val backArrayList = elementData.copyOfRange(index, size)
elementData[index] = element
newSize = index+1
// 뒷부분에 복사
backArrayList.forEach {
elementData[newSize++] = it
}
}
size = newSize
} else {
// elementData에 물리적인 공간(capacity)이 존재하지 않을 때 -> 배열의 크기를 증가시켜야 함
...
}
}
두번째 시도한 방법은 새로운 배열이 아닌 기존 배열을 이용해보자! 였다.
하지만 index 기점 뒤에 있는 데이터들을 보관하고 있을 배열이 필요해서 배열 복사를 통해 또다시 새로운 배열을 만들게 되었다. (어쩔 수 없는 부분)
아무튼 index 뒤의 데이터들을 복사해놓고, index 위치에 데이터를 넣어주었다.
그리고 또 다시 for문을 통해 복사해놓았던 배열의 데이터들을 elementData에 넣어주었다.
3개의 for문이 1개의 for문으로 줄어들었고, 배열의 복사를 이용한 시도였다.
그런데 의문인거지. for문 없이도 가능하지않을까?
4️⃣ 네번째 구현 : 중간에 데이터를 추가하는 경우 -3
override fun add(index: Int, element: Int) {
// 새로 들어갈 원소의 자리가 없다면 -> 새로운 배열 생성
if (size == elementData.size) {
val newArray = Array(size+1) { 0 }
System.arraycopy(elementData, 0, newArray, 0, size)
elementData = newArray
}
System.arraycopy(elementData, index, elementData, index+1, size-index)
elementData[index] = element
size += 1
}
이번에도 배열 복사를 이용하였다. 세번째 구현과 다른 점은 for문이 없다는 점 !
일단 새로 들어갈 공간이 없다면 새로운 배열을 생성해서 기존의 배열 데이터를 복사해주었다.
그리고 elementData 변수에 새로 만든 배열 메모리 주소를 할당해주었고, 이를 다시 옆으로 한 칸씩 옮기는 복사 작업을 해주었다.
코드가 길어지지도 않고, 반복문이 들어가지도 않는다.
그리고 조건문도 줄어들었다.
가장 처음에 고려할 수 있는 것들을 다시 가져와서 보면
1) elementData에 추가적인 데이터를 넣을 수 있는지?
1-1) 넣을 수 있다면, 해당 index에 넣기
1-2) 넣을 수 없다면, elementData의 크기보다 하나 더 큰 새로운 배열을 만들기
2) index가 0인지? (가장 맨 앞인지)
2-1) 0이라면 가장 맨 앞에 넣고, 그 이후에 기존의 배열을 옮겨준다.
2-2) 0이 아니라면 ..
2개의 조건문에서 1개로 줄어들었다 !
그런데 궁금증이 남았따 .. 만약 배열이 엄청 크다면, 배열 복사를 가지고 있는 이 코드는 괜찮은가?
하지만 그럴땐 삽입/삭제를 할 때 공간을 만들고 or 공간을 제거해주어야 하는 단점을 가진 배열 기반의 리스트인 ArrayList가 아닌 LinkedList를 사용하겠지?
이제 남아있는 건 삭제 부분이다 ! 아자잣!
'Kotlin > note' 카테고리의 다른 글
| [Kotlin] Scope Functions (let/run/with/apply/also) (0) | 2023.08.16 |
|---|---|
| data class의 변수들을 private로 선언하는 사람이 있다? (0) | 2022.01.10 |
