이포스트는 Data Structures & Algorithms in Kotlin을 참고하여 작성하였습니다.

Kotlin Collection Interface

이번 포스트에서는 Kotlin Collection Interface에 대해 다뤄보겠습니다.

Kotlin Collection Interface 은 무엇일까요? Kotlin Library의 인터페이스는 어떤 타입을 리턴하는지 말해주고 각 타입은, 각각의 특성을 가지고 있습니다. 그리고 Collection Interface는 4 티어로 나눠집니다.

	인터페이스	설명
Tier 1	Iterable	Iterable 타입은 element를 Iterator를 통해 순차적으로 접근합니다.
Tier 2	Collection	Iterable 타입인 동시에, element와 Collection의 연결관계를 확인 가능합니다.
Tier 3	MutableIterable	아이템을 지울수있습니다.
Tier 4	MutableCollection	아이템을 지우거나 추가하거나 수정가능합니다.

각 티어를 하나씩 만들어보겠습니다.

Mutable Collection 구현 및 사용예제

Tier 1을 만들기 이해서는 LinkedList에 iterable을 지정해주면 됩니다. 전 포스트에서 LinkedList를 만들었을 때 size를 지정해준 것처럼 size를 먼저 만들어주겠습니다.

var size = 0 
private set

그리고 LinkedList클래스에 Iterable 인터페이스를 추가해줍니다.

class LinkedList<T> : Iterable<T> {
	...
}

↑이 코드는 Iterable Interface를 충족하기 위해

override fun iterator(): Iterator<T> {
	return LinkedListIterator(this)
}

↑ LinkedList class안에 interator 함수를 오버라이드 한 것입니다.

LinkedListIterator를 리턴해주었지만 class를 만들어주지 않았습니다. 아래에서 linkedListIterator를 만들어주겠습니다.

class LinkedListIterator<T>(
	private val list: LinkedList<T>
): Iterator<T> {
	override fun next(): T{
    	TODO("not implemented")
    }
    override fun hasNext(): Boolean{
    	TODO("not implemented")
    }
}

↑ LinkedList Iterator클래스를 만들어주고, 2가지 함수를 override 해주겠습니다. 주어진 리스트 위치에 node가 있는 재확인하는 함수를 override 해보겠습니다.

private var index = 0

override fun hasNext(): Boolean {
	return index < list.size
}

↑ has next를 먼저 implement 해보겠습니다.일단 정해진 위치에 값을 확인하기 위해 index var을 추가해주었습니다. hasNext() 함수를 보면 index크기가 list의 사이즈보다 작을 때, index값 위치에 node가 있는 걸 알 수 있습니다. list의 사이즈와 index를 비교해서 index가 작다면 true를 반환하고 이 의미는 index자리에 값이 있다는 뜻입니다.

다음은 마지막 노드를 찾아보도록 하겠습니다.

private var lastNode: Node<T>? = null

next() 함수를 만들어 활용해서 lastNode를 찾아보겠습니다. 먼저 implement를 해야 합니다.

override fun next(): T {
//1
if(index >= list.size) throw IndexOutOfBoundsException()

//2
lastNode = if(index == 0 ){
	list.nodeAt(0)
	}  else{
	lastNode?.next
	}
//3
	index++
return lastNode!!.value
}

1. index자리에 값이 있는지 확인하고 만약 없다면, exception을 리턴합니다. 정상적인 Iterator를 썼다면 exception이 리턴되면 안 됩니다.

2. 마지막 node가 현재 node인지 확인하기 위한 step입니다. list에 단 하나에 node가 있다면 첫 번째 value를 리턴합니다. 만약 다음 node가 lastNode라면 lastNode.next를 lastNode로 지정해줍니다.

3. lastNode가 업데이트되었기 때문에, index값도 업데이트돼야 합니다. index +1을 해줍니다.

이제 MutableCollection의 특징인 list에 있는 값을 수정해보겠습니다. 수정할 때 for 루프를 사용해서 리스트에 있는 각 아이템에 접근해 보겠습니다.

fun main에 아래 함수를 실행시켜보겠습니다.

"printing Doubles" example{
	val list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    println(list)
    
    for (item in list) {
    	println("Double: ${item * 2}")
    }
}

결과는 다음과 같습니다.

--Example of printing doubles--

1 -> 2 -> 3

Double: 2 
Double: 4
Double: 6

Collection 구현 및 사용 예제

Collection을 만들기 위해서 먼저 collection을 상속시킨 LinkedList class를 만들어주겠습니다.

class LinkedList<T> : Collection<T>{
	...
}

오버라이드를 통해 간단하게 이미 만들어져 있는 size와 isEmpty를 추가해주겠습니다.

override var size = 0
	private set
    
override fun isEmpty(): Boolean{
	return size == 0
}

Contains 함수를 오버라이드 해주겠습니다. 이 함수는 인자로 받는 element가 리스트에 있는지 for 루프로 반복하며 체크합니다.

override fun contains(element:T): Boolean{
	for (item in this) {
    	if (item == element) return true
    }
    return false
}

Mutable Iterable 구현 및 사용 예제

Mutable Iterable을 만들기 위해, LinkedList를 MutableIterable 하게 만들어야 합니다.

class LinkedListIterator<T>(
	private val list: LinkedList<T>
) : Iterator<T>, MutableIterator<T> {
	...
}

위 테이블에서 보았듯이 MutableIterator은 Iterator가 없는 기능인, "데이터를 수정할 수 있는 기능"이 있습니다.

MutableIterator이기 때문에 node를 수정할 수 있게 되었습니다. node를 지울 수 있는 remove함수를 오버라이드 해보겠습니다.

먼저 node를 지우는 pop함수를 만들어준 후

fun pop(): T? {
	if(!isEmpty()) size--
    val result = head?.value
    head = head?.next
}

remove함수에 활용해 보겠습니다.

override fun remove() {
	//1
    if(index == 1){
    	list.pop()
    } else {
    //2
    	val prevNode = list.nodeAt(index - 2) ?: return
    //3
        list.removeAfter(prevNode)
        lastNode = prevNode
    }
    index --
}

위 코드를 차례대로 설명해보겠습니다.

1. pop이라는 새로운 함수는 LinkedList에서 가장 앞에 있는 node를 제거합니다.

2. iterator가 리스트 어딘가에 있다면, 전 node를 찾아야 합니다. 그래야 아이템을 지울 수 있습니다.

3. next()가 다시 lastNode를 지정해주고 index를 지우기 줄이기 위해서, Iterator는 다시 뒤로 돌아가야 합니다.

이제 LinkList 클래스와 Iterator에 MutableIterable과 MutableIterator를 추가해줍니다.

class LinkedList<T>: Iterable<T>, Collection<T>, MutableIterable<T> {
	...
}

override fun iterator(): MutableIterator<T> {
	return LinkedListIterator(this)
}

Mutable Collection 구현 및 사용 예제

Mutable Collection 인터페이스를 LinkedList에 추가해줍시다.

class LinkedList<T>: Iterator<T>, Collection<T>, MutableIterable<T>, MutableCollection<T> {
	...
}

MutuableCollection을 추가하면 아래 6가지 함수를 추가해야 합니다.

override fun add(element:T):Boolean {
	TODO("not impletmented")
}
override fun addAll(elements: Collection<T>):Boolean {
	TODO("not impletmented")
}
override fun clear() {
	TODO("not impletmented")
}
override fun remove(element:T):Boolean {
	TODO("not impletmented")
}
override fun removeAll(element:Col):Boolean {
	TODO("not impletmented")
}
override fun add(element:T):Boolean {
	TODO("not impletmented")
}

위 코드는 implement를 해주어야 합니다. 맨 앞줄부터 3개 함수를 먼저 Implement 해보겠습니다.

override fun add(element:T): Boolean {
	append(element)
    return true
}

override fun addAdd(elements: Collection<T>): Boolean {
	for(element in elements){
    	append(element)
    }
    return true
}

override fun clear() {
	head = null
    tail = null
    size = 0
}

LinkedList는 고정된 사이즈가 아니기 때문에, add()와 addAll() 함수를 사용할 때 항상 실행될 수 있기 때문에, 언제나 true를 리턴하게 됩니다.

Mutable Collection에서 element를 지울 때는 mutableIterable LinkedList에서 했던 것과 다른 방식으로 iterator를 사용해야 합니다.

override fun remove(element:T): Boolean{
	//1
    val iterator = iterator()
    //2 
    while (iterator.hasNExt()){
    	val item = iterator.next()
        //3
        if (item ==element) {
        	iterator.remove()
            return true
        }
    }
    //4 
    return false
}

위 코드를 설명해보겠습니다.

1. 먼저 Itertator를 불러옵니다.

2. 남은 element가 있는지 확인하는 루프를 만듭니다 그리고 다음 element를 val item에 가져옵니다.

3. item이 내가 찾던 element인지 확인합니다. 맞다면, 지웁니다.

4. 지워지지 않았다면 false를 리턴합니다.

removeAll도 implment 해보겠습니다.

override fun removeAll(elements: Collection<T>): Boolean {
	var result = false
    for(item in elements) {
    	result = remove(item) || result
    }
    return result
}

마지막으로 Implement 할 함수는 retainAll입니다. 그러면 이 함수로 선택된 element를 삭제할 수 있습니다.

override fun retainAll(elements: Collection<T>): Boolean{
	val result = false
    val iterator = this.iterator()
    while (iterator.hasNExt()){
    	val item = iterator.next()
        if(!elements.contains(item)){
        	iterator.remove()
            return = true
        }
    }
    return result
}

이제 Mutable Collection에 Implement는 끝났습니다.

main.kt에서 활용해보겠습니다.

"removing elements" example{
	val list: MutableCollection<Int> = LinkedList()
    list.add(3)
    list.add(2)
    list.add(1)
    
    println(list)
    list.remove(1)
    println(list)
}

"retaining elements" example{
	val list: MutableCollection<Int> = LinkedList()
    list.add(3)
    list.add(2)
    list.add(1)
    list.add(4)
    list.add(5)
    
    println(list)
    list.retainAll(listOf(3,4,5))
    println(list)
}

"remove all elements" example {
	val list: MutableCollection<Int> = LinkedList()
    list.add(3)
    list.add(2)
    lsit.add(1)
    list.add(4)
    list.add(5)
    
    println(list)
    list.removeAll(listOf(3,4,5))
    println(list)
}

다음 편에서는 LinkedList에 관련된 몇 가지 알고리즘 문제와 풀이를 다뤄보겠습니다.

'개발공부 > Algorithm' 카테고리의 다른 글

[알고리즘] Tree 트리 : 기본정리 - 트리 구성, 깊이우선순회(Depth-First Traversal), 레벨순회(LevelOrderTraversal), 검색(Search) - Kotlin (0)	2021.09.24
[알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐),ArrayList, Stack으로 Queue 구현하기 - Kotlin (0)	2021.09.16
[알고리즘] Stack 스택: 기본정리 - pop, push, peek, count - Kotlin (0)	2021.09.09
[알고리즘] LinkedList 링크리스트: 활용 예제 - 뒤집기, 합치기, 가운데 값 찾기 - Kotlin (0)	2021.09.07
[Algorithm] Kotlin LinkedList 개념 및 구현 - 지정한 위치에 node 추가하기, node 제거하기 (0)	2021.07.28

[알고리즘] 기본으로 알아야할 Kotlin Collection Interface 종류 및 구현 - Iterable, Collection, MutableIterable, MutableCollection 사용예제