How to find last node that satisfies where predicate in singly linked list?

user_12382562 0
Viewed 147

  1. write a method "lastWhere" that accepts a function called "where" of type (T) -> Boolean. The method returns the last element of type T to which the "where" function applies. If no matching element is found, null is returned.

  2. call the method "lastwhere" on the linked list below. Find the last game that is more than 10 euros.

So far I've got this Code going for me.

I assume the only important piece of Code I need to edit is the "fun lastWhere" for task number 1)

the second task wants me to implement a way on the main function to find the last Game that is cheaper than 10 Euros.

class LinkedList<T> {
    data class Node<T>(val data: T, var next: Node<T>?)

    private var first: Node<T>? = null

    override fun toString(): String = first?.toString() ?: "-"

    fun isEmpty() = first == null

    fun addLast(data: T) {
        if (first == null) {
            first = Node(data, first)
            return
        }

        var runPointer = first
        while (runPointer?.next != null) {
            runPointer = runPointer.next
        }
        runPointer?.next = Node(data, null)
    }

    fun lastWhere (where: (T) -> Boolean): T? {   // "where" function needs to be implemented
        if (isEmpty()) return null
        else {
            var runPointer = first
            while (runPointer?.next != null ) {
                runPointer = runPointer.next
            }
            return runPointer?.data
        }
    }

}

data class Game(val title: String, val price: Double)

fun main() {
    val list = LinkedList<Game>()
    list.addLast(Game("Minecraft", 9.99))
    list.addLast(Game("Overwatch", 29.99))
    list.addLast(Game("Mario Kart", 59.99))
    list.addLast(Game("World of Warcraft", 19.99))

    var test = list.lastWhere ({it.price >= 10.00})  // This is probably wrong too, since I haven't got task 1) working
    println (test)
}

Would appreciate any help!

kotlin higher-order-functions linked-list
1 Answers

Since you only store a reference to first node, you don't have any choice but to start at first and iterate. you will also have to keep a reference to last item that satisfied the where predicate, and keep updating this reference with every iteration.

fun lastWhere (where: (T) -> Boolean): T? { 
    var runPointer = first
    var item: T? = null    // init item to null, if nothing is found we return null
    while (runPointer != null ) {
        // For every node, execute the where function and if it returns true
        // then update the return value 
        if(where(runPointer.data)) { item = runPointer.data }
        runPointer = runPointer.next
    }
    return item
}
user_44130980
Related