class DoublyLinkedList<T> {

    // We'll keep this class a secret to ourselves; no one using
    // a doubly linked list has to know about how we've stored the
    // data and pointers.
    //
    // Food for thought: why do we need next and prev, in particular,
    // to be declared with var instead of val?
    private data class Node<T>(
        var item: T,
        var next: Node<T>?,
        var prev: Node<T>?)

    // The list knows which nodes, if any, are at its
    // head and tail
    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    // Let's make it easy to print
    override fun toString(): String {
        var result: String = ""
        var current: Node<T>? = head
        while (current != null) {
            result = result + current.item + " "
            current = current.next
            // ponder: why don't we need !! in the above two lines?
        }
        return result.trim() // take off that extra " "
    }

    // We should, at the least, be able to insert somewhere
    fun insertAtBeginning(item: T) {
        // Our new node has the current head as its next (which may be null)
        // and no prev, because it'll be at the beginning
        val newNode = Node(item, head, null)

        // Wire up the previous head to have our new node as its prev
        val oldHead: Node<T>? = head
        if (oldHead != null) {
            oldHead.prev = newNode
        }

        // Now see if this new node is also the tail (ponder: it what
        // situation is this true?)
        if (tail == null) {
            tail = newNode
        }

        // Now properly update the head pointer for the list
        head = newNode
    }
}

    // TODO: get the length of the list
    fun length(): Int {
        return 0
    }

    // TODO: insert at the tail
    fun insertAtEnd(item: T) {

    }

    // TODO: find an element in the list
    fun search(target: T): Boolean {
        return false
    }
    
    // TODO: look up the node at a given position
    private fun findNodeAtPosition(position: Int): Node<T>? {
        return null
    }

    // TODO: insert at a given position
    fun insertAtPosition(position: Int, item: T) {

    }

fun main() {
    // First, test basic inserts and prints
    val mylist = DoublyLinkedList<String>()

    mylist.insertAtBeginning("Lulu")
    mylist.insertAtBeginning("Hobbes")
    mylist.insertAtBeginning("Cheddar")

    println()
    println("List with 3 elements: $mylist")

    // Now try checking the length and inserting at the end
    println("Length: ${mylist.length()}")
    mylist.insertAtEnd("Marshmallow")
    println()
    println("List with 4 elements: $mylist")
    println("Length: ${mylist.length()}")

    // What if we look for an element?
    println()
    println("List contains \"Lulu\": ${mylist.search("Lulu")}")
    println("List contains \"LULU\": ${mylist.search("LULU")}")

    // Can we insert just anywhere?
    mylist.insertAtPosition(2, "Sadie")
    mylist.insertAtPosition(1, "Therese")
    println()
    println("List with 6 elements: $mylist")
}

    // TODO: swap the given node with its next neighbor
    // (make sure to update head/tail if appropriate)
    // NOTE: assumes curr is not the tail
    private fun swapWithNeighbor(curr: Node<T>) {

    }

    // Swap the node at the given position with its next neighbor
    // (fails if position is out of bounds or corresponds to the tail)
    fun swapPositionWithNeighbor(position: Int) {
        // Find the node, if it exists
        val current: Node<T>? = findNodeAtPosition(position)

        // If the node to swap is the tail, that's a problem
        if (current == tail) {
            throw RuntimeException("Cannot swap the tail with its next!")
        }

        // Swap the node with its next neighbor
        swapWithNeighbor(current!!)
    }

    // What if we swap some nodes?
    mylist.swapPositionWithNeighbor(1)
    println()
    println("List after swapping node at position=1 with its next: $mylist")
    mylist.swapPositionWithNeighbor(4)
    mylist.insertAtEnd("Milo")
    println("List after swapping node at position=4 with its next and adding to tail: $mylist")