Exercises for Lesson 9

Back to Lesson 9

Exercise 1: Using a Linked List to implement a Stack

Consider the following start of a linked-list implementation in Kotlin (we saw this in Lesson 8). We’re going to implement it such that it conforms to the Stack ADT:

/*
 * LinkedStack.kt
 * 
 * Based on Dave Musicant's LinkedStack.kt from Fall 2024.
 * 
 * Illustrates an implementation of the Stack ADT using
 * a linked list.
 */

/*
 * Stack interface: implements a stack
 */
interface Stack<T> {
    fun push(item: T)
    fun pop(): T
    fun peek(): T
    fun isEmpty(): Boolean
}

class LinkedStack<T> : Stack<T> {

    // This "private" "data class" is visible only within the LinkedStack
    // class, and contains only data with no additional functions (besides a
    // few that Kotlin provides, like for printing it)
    private data class Node<T>(
        var item: T,
        var next: Node<T>?)

    // We'll maintain just a reference to the head of the linked list
    // (which may be null, in the case the list is empty)
    private var head: Node<T>? = null

    /*
     * TODO: add method stubs for the interface (one is started for you)
     */

    override fun peek(): T {
        if (isEmpty()) {
            throw RuntimeException("The stack is empty!")
        }

        // What to do if it doesn't crash??
    }
    
    override fun toString(): String {
        // TODO: update this so it looks like a stack,
        // not just a linked list
        var s: String = ""
        var current: Node<T>? = head
        while (current != null) {
            s += current.item.toString() + " -> "
            current = current.next
        }
        
        s += "(null)"
        return s
    }
}

Add in stubs

Our first step is to add method stubs (simple methods that allow our code to almost compile, but do nothing interesting).

Fill in methods to make your LinkedStack conform to this interface:

interface Stack<T> {
    fun push(item: T)
    fun pop(): T
    fun peek(): T
    fun isEmpty(): Boolean
}

You won’t be able to compile yet because you don’t know what to return for a default value of T, but this is enough to get you started.

Implement your stack

Draw out a linked list on paper. How could you use this data structure to implement a stack? Try it out! Fill in the four methods above and use this main function to test it:

fun main() {
    val s = LinkedStack<Int>()
    s.push(2025)
    s.push(10)
    s.push(3)
    
    println("Elements present in stack: ")
    println(s)
    
    println("" + s.pop() + " popped from stack")
    println("Top element is: " + s.peek())

    println("Elements present in stack: ")
    println(s)
}

Time complexity

The implementation choices you make impact the runtime. How does your stack implementation scale? Think through the time complexity of each of the four methods you implemented, assuming there are already n items in the stack.

Back to Lesson 9