코딩테스트를 공부하기 위해 코틀린을 이용한 자료구조, 알고리즘 강의나 서적을 찾아봤지만,
이제 막 떠오르는 언어라 그런지 아직까지는 없는 듯 했습니다.
그래서 기존에 알고 있던 파이썬과 "자료구조와 함께 배우는 알고리즘 입문 - 자바편"
이라는 책을 기반으로 해서 코틀린을 기반한 모든 자료구조와 알고리즘을 다뤄볼 것입니다.
두 언어 모두 객체 지향이고 JVM에서 실행되는 코틀린이기 때문에 자바를 기준으로 하되,
파이썬의 간결함을 결합시켜 최대한 이해하기 쉽게 작성해봤습니다.
그럼 전체 코드를 먼저 살펴보겠습니다.
class LinkedList<E> {
private var head: Node<E>? = null
private inner class Node<E>(
var data: E,
var next: Node<E>? = null
)
private fun addFirst(item: E) {
head = Node(item)
}
fun add(item: E) {
if (head == null) addFirst(item)
else {
var node = head
while (node?.next != null) node = node.next
node?.next = Node(item)
}
}
fun delete(item: E) {
if (head == null) return println("노드가 존재하지 않습니다.")
else {
if (head?.data == item) {
head = head?.next
} else {
var node = head
while (node?.next?.data != item) node = node?.next
node?.next = node?.next?.next
}
}
}
fun desc() {
var node = head
while (node != null) {
print("${node.data} ")
node = node.next
}
println()
}
}제네릭 표현 타입을 이용해서 어느 자료형이든 LinkedList를 사용할 수 있습니다.
다음은 코드 상세 설명입니다.
private var head: Node<E>? = null
아무것도 설정되지 않은 LinkedList는 head를 가지고 있지 않기 때문에 null로 설정합니다.
private inner class Node<E>(
var data: E,
var next: Node<E>? = null
)
Node 클래스 부분입니다.
LinkedList 클래스와 같이 제네릭 타입을 설정하고 클래스 괄호 안에 data, next를 넣어서 생성자를 구현합니다.
코틀린 문법을 이용해 next는 디폴트 값으로 null을 설정합니다.
fun add(item: E) {
if (head == null) head = Node(item)
else {
var node = head
while (node?.next != null) node = node.next
node?.next = Node(item)
}
}
노드를 추가하는 함수입니다.
1. head가 null이라면 아무 것도 존재하지 않으므로 head에 노드를 추가합니다.
2. head가 null이 아니라면
마지막 노드까지 읽어들인 후, null을 가리키고 있는 next를 새로운 Node를 가리키게 합니다.
fun delete(item: E) {
if (head == null) return println("노드가 존재하지 않습니다.")
else {
if (head?.data == item) {
head = head?.next
} else {
var node = head
while (node?.next?.data != item) node = node?.next
node?.next = node?.next?.next
}
}
}
노드를 삭제하는 함수입니다.
다음과 같이 3가지로 분류합니다.
- head가 존재하지 않는 경우
- null check를 통해 함수를 종료합니다.
- head에 삭제하려는 데이터가 존재하는 경우
- head가 다음 노드를 가리키게(head.next) 해서 첫번째 노드를 삭제시킵니다.
- 중간 노드 혹은 마지막 노드에 삭제하려는 데이터가 존재하는 경우
- 삭제하고자 하는 데이터가 다음 노드를 가리킬 때까지 찾습니다.
- node?.next = node?.next?.next는
node?.next는 현재 기준의 node의 다음 노드, 즉 삭제하려는 노드를 가리킵니다.
해당 next를 node?.next?.next를 가리키게 해서 삭제하려는 노드 기준으로
이전과 이후의 노드를 연결시키면 삭제하는 방식입니다.
마지막 노드 제거 시에도 node?.next?.next 가 가리키는 것은 null이기 때문에 충족합니다.
fun desc() {
var node = head
while (node != null) {
print("${node.data} ")
node = node.next
}
println()
}
전체 노드를 조회하는 함수입니다.
node가 존재할 때까지 반복하여 print함수로 데이터를 찍고, 노드는 다음 노드를 가리킵니다.
결과 확인
fun main() {
val linkedList = LinkedList<Int>()
linkedList.add(0) // 0
for (i in 1..10) {
linkedList.add(i) // 0 1 2 3 4 5 6 7 8 9 10
}
linkedList.desc() // 0 1 2 3 4 5 6 7 8 9 10
linkedList.delete(0) // 1 2 3 4 5 6 7 8 9 10
linkedList.delete(10) // 1 2 3 4 5 6 7 8 9
linkedList.desc() // 1 2 3 4 5 6 7 8 9
}
보시는 바와 같이 모든 함수가 잘 작동합니다.
다음 게시글은 DoubleLinkedList를 직접 구현해보겠습니다.
