LinkedLisk
unknown
kotlin
2 years ago
2.6 kB
4
Indexable
package linkedlist sealed class Option<out T> { data class Some<T>(val unwrappedValue: T): Option<T>() object None: Option<Nothing>() } data class Node<T>(val value: T, val next: LinkedList<T>) class LinkedList<T>(private var head: Option<Node<T>>) : Collection<T> { constructor() : this(Option.None) override var size: Int = 0 override fun isEmpty(): Boolean = this.head is Option.None override fun iterator(): Iterator<T> = IteratorImpl() override fun containsAll(elements: Collection<T>): Boolean { TODO("Not yet implemented") } override fun contains(element: T): Boolean { TODO("Not yet implemented") } fun addToFront(data: T): LinkedList<T> { val t = this.head // Either Some or None head = Option.Some(Node(data, LinkedList(t))) size++ return this } fun addToBack(data: T, list: LinkedList<T> = this): LinkedList<T> { when(val iter = list.head) { is Option.Some -> list.addToBack(data, iter.unwrappedValue.next) is Option.None -> list.head = Option.Some(Node(data, LinkedList())) // OR call this.addToFront(..) } size++ return this } fun get(index: Int): T { return when(val result = getNode(index)) { is Option.Some -> result.unwrappedValue.value is Option.None -> throw IndexOutOfBoundsException("index: $index is out of bounds") } } tailrec fun print(curr: Option<Node<T>> = this.head) { when(curr) { is Option.Some -> { print(curr.unwrappedValue.value) if (curr.unwrappedValue.next.head !is Option.None) print("->") this.print(curr.unwrappedValue.next.head) } is Option.None -> return } } private fun getNode(index: Int): Option<Node<T>> { var current = this.head var currentIndex = index while (currentIndex > 0) { current = when (current) { is Option.Some -> current.unwrappedValue.next.head is Option.None -> return Option.None } currentIndex-- } return current } private open inner class IteratorImpl : Iterator<T> { /** the index of the item that will be returned on the next call to [next]`()` */ protected var index = 0 override fun hasNext(): Boolean = index < size override fun next(): T { if (!hasNext()) throw NoSuchElementException() return get(index++) } } }
Editor is loading...