More than 3 years have passed since last update.

CodeKataをKotlinでやってみた〜Simple Lists編〜

Last updated at 2021-01-17Posted at 2021-01-17

今回もCodeKataをKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"CodeKataをKotlinでやってみた〜Karate Chop編〜"をご参照ください。
自学として続けてきたKodeCataも今回で最後になります。

トライしてみる

今回の課題は21あるKataのうち21つ目に当たる"Simple Lists"です。

For this kata we’re going to code up three implementations of a list that has the following basic interface:

The list consists of nodes. Each node has a string value, along with whatever housekeeping the list itself needs.
New nodes are added to the end of the list.
You can ask the list if it contains a given string. If it does, it returns the node containing that string.
You can delete a node from the list.
You can ask the list to return an array of all its values.
Here’s a basic set of unit tests to illustrate the behavior.

list = List.new
assert_nil(list.find("fred"))
list.add("fred")
assert_equal("fred", list.find("fred").value())
assert_nil(list.find("wilma"))
list.add("wilma")
assert_equal("fred",  list.find("fred").value())
assert_equal("wilma", list.find("wilma").value())
assert_equal(["fred", "wilma"], list.values())
>
list = List.new
list.add("fred")
list.add("wilma")
list.add("betty")
list.add("barney")
assert_equal(["fred", "wilma", "betty", "barney"], list.values())
list.delete(list.find("wilma"))
assert_equal(["fred", "betty", "barney"], list.values())
list.delete(list.find("barney"))
assert_equal(["fred", "betty"], list.values())
list.delete(list.find("fred"))
assert_equal(["betty"], list.values())
list.delete(list.find("betty"))
assert_equal([], list.values())

つまり、上記のテストケースで呼び出されている様な追加（"add"）・検索（"find"）・削除（"delete"）などの機能性を持っているリストをスクラッチで実装していくことが今回の課題となります。
ブログ内では「3つの実装方法で試してみよう」と紹介していますが、今回はSinglyLinkedListでのみ実装を行っていきます。

SinglyLinkedListとは

片方向リスト（singly-linked list）は、最も単純な連結リストであり、ノード毎に1つのリンクを持つ。このリンクはリスト上の次のノードを指し、リストの最後尾ならNull値を格納するか、空のリストを指す。

（引用：Wikipedia　連結リストより）

各値をnodeとして保持する際に、そのnodeに次のnodeのリンクを保持することで値を単方向に辿っていく様なデータ構造になります。原理的にはnodeの持つ必要のあるデータは"データ値"と"次nodeへのポインター"の2つのみなので、比較的単純に実装が行えることが特徴です。

実装

class SinglyLinkedList {
    // node which has next pointer to next node
    data class SingleNode(val value: String, var next: SingleNode?)
    // node stored as first one at SinglyLinkedList instance
    var firstNode: SingleNode? = null

    /**
     * add element to singly linked list
     */
    fun add(newValue: String) {
        // if first node is not assigned, set "newValue" as first one
        if (firstNode == null)
            firstNode = SingleNode(newValue, null)
        else
            assignNewValue(newValue, firstNode)
    }

    /**
     * assign new value as last element
     */
    private fun assignNewValue(newValue: String, node: SingleNode?) {
        // if "node" is the last element, assign new node as the last one
        if (node?.next == null)
            node?.next = SingleNode(newValue, null)
       else
            // call the method recursively to reach the last element
            assignNewValue(newValue, node.next)
    }

    /**
     * find and return SingleNode if exist
     */
    fun find(value: String): SingleNode? {
        var node: SingleNode? = firstNode

        while (true) {
            if (node?.value == value) return node
            // if target not found, return null
            if (node?.next == null) return null

            node = node.next
        }
    }

    /**
     * delete node from singly linked list
     */
    fun delete(targetNode: SingleNode) {
        var node: SingleNode? = firstNode
        // if `firstNode` is `targetNode`, just delete that and  
        // return to finish the process
        if (targetNode == node) {
            firstNode = node.next
            return
        }

        while (true) {
            if (targetNode == node?.next) deleteNextNode(node)
            // if target not found, return and finish the process
            if (node?.next == null) return

            node = node.next
        }
    }

    /**
     * delete next node by setting next next node as next one
     */
    private fun deleteNextNode(node: SingleNode) {
        val nextNextNode = node.next?.next
        node.next = nextNextNode
    }

    /**
     * return all values stored at singly linked list
     */
    fun values(): List<String>{
        val values = mutableListOf<String>()
        var node: SingleNode? = firstNode

        while (true) {
            node?.value?.let { values.add(it) }
            // if "node" is the last element, break and finish the process
            if (node?.next == null) break

            node = node.next
        }

        return values
    }
}

今回はブログ内で紹介されていたテストケースを前提として考えるので、値をStringとして保持することを想定しています。値valueと次nodeのポインターnextを保持するデータクラスとしてSingleNodeを作成しています。最後のnodeは次nodeへのポインターを持たないため、nextはnullableとしています。

ユーザ向けのインターフェースとして実装しているメソッドは下記4つです。

add
- 引き渡されたString値を持つnodeをSinglyLinkedListの最後に追加するメソッドです。もし1番目のnodeであるfirstNodeが設定されていない場合には引き渡されたString値を元にfirstNodeを設定し、そうでない場合にはassignNewValueを再帰的に呼び出すことでSinglyLinkedListの最後に値を追加します。
find
- 引き渡されたString値をvalueとして保持するnodeを検索するメソッドです。SinglyLinkedListが持つ値を走査し、一致するものが存在する場合にはそのnodeを返却し、存在しない場合にはnullを返却します。
delete
- 引き渡されたnodeがSinglyLinkedListに存在する場合に該当nodeを削除するメソッドです。削除処理の結果に関わらず値を返却しない様にしていますが、例えば削除対象のnodeを返却するなどすると使い道が広がるかもしれません。
values
- 保持する全nodeのvalueをリストとして返却するメソッドです。SinglyLinkedListが持つ全ての値をリストに追加していき、次のnodeが存在しなくなった段階で全String値を保持するリストを返却します。

テスト

それではテストケースを整備してアルゴリズムが意図通り動作しているか確認してみます。ブログで紹介されている2つのケースをほぼそのまま利用しますが、そちらはRubyで書かれているためKotlinで記述するに当たり多少変更しています。

class SimpleListsTest {
    @Test
    fun testSinglyLinkedList1() {
        val list = SinglyLinkedList()

        assertNull(list.find("fred"))
        list.add("fred")
        assertEquals("fred", list.find("fred")?.value)

        assertNull(list.find("wilma"))
        list.add("wilma")

        assertEquals("fred",  list.find("fred")?.value)
        assertEquals("wilma", list.find("wilma")?.value)
        assertEquals(listOf("fred", "wilma"), list.values())
    }

    @Test
    fun testSinglyLinkedList2() {
        val list = SinglyLinkedList()

        list.add("fred")
        list.add("wilma")
        list.add("betty")
        list.add("barney")
        assertEquals(listOf("fred", "wilma", "betty", "barney"), list.values())

        list.delete(list.find("wilma")!!)
        assertEquals(listOf("fred", "betty", "barney"), list.values())

        list.delete(list.find("barney")!!)
        assertEquals(listOf("fred", "betty"), list.values())

        list.delete(list.find("fred")!!)
        assertEquals(listOf("betty"), list.values())

        list.delete(list.find("betty")!!)
        assertEquals(listOf(), list.values())
    }
}

無事にテストケースを通過し、意図通りプログラムが動いていることを確認できました！

まとめ

コロナのこともあり年末暇だなあということで初めてみたCodeKataですが、楽しんで取り組めたかなと思います。業務では使えていないKotlinで色々プログラムを書けたのもよかったです。

お読みいただきまして、ありがとうございました！

関連記事一覧

CodeKataをKotlinでやってみた〜Karate Chop編〜
CodeKataをKotlinでやってみた〜Data Munging編〜
[CodeKataをKotlinでやってみた〜Bloom Filters編〜]
(https://qiita.com/Takuyaaaa/items/eaa3848bce3bccdd946f)
[CodeKataをKotlinでやってみた〜Anagrams編〜]
(https://qiita.com/Takuyaaaa/items/df06e24e6f2c7f8ced35)
[CodeKataをKotlinでやってみた〜Checkout編〜]
(https://qiita.com/Takuyaaaa/items/0a4b82e30c977444c0bc)
[CodeKataをKotlinでやってみた〜Sorting it Out編〜]
(https://qiita.com/Takuyaaaa/items/b5210c53bff3ff5f0512)
[CodeKataをKotlinでやってみた〜Counting Code Lines編〜]
(https://qiita.com/Takuyaaaa/items/cb9143fbcb9e0b2a7822)
[CodeKataをKotlinでやってみた〜Tom Swift Under the Milkwood編〜]
(https://qiita.com/Takuyaaaa/items/feccf69d2b9d95196a72)
[CodeKataをKotlinでやってみた〜Transitive Dependencies編〜]
(https://qiita.com/Takuyaaaa/items/9b43473b8feffe1ce9f7)
[CodeKataをKotlinでやってみた〜Word Chains編〜]
(https://qiita.com/Takuyaaaa/items/2539338252ad7e19ba18)
[CodeKataをKotlinでやってみた〜Simple Lists編〜]
(https://qiita.com/Takuyaaaa/items/36ef73522bfe8d054448)

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

CodeKataをKotlinでやってみた 〜Simple Lists編〜

トライしてみる

SinglyLinkedListとは

実装

テスト

まとめ

CodeKataをKotlinでやってみた〜Simple Lists編〜