import java.util.Random val random = Random() // Get a random number in the range fun rand(from: Int, to: Int) = random.nextInt( to-from+1)+from // Single node template of the linked list storing // a value of whatever type, a pointer to the // previous node, and a pointer to the next node. data class Node(var value: T, var previous: Node? = null, var next: Node? = null) // Create an iterator class allocating the list and // the current & end positions. class ListIterator(private val self: List, start: Int, private val end: Int): Iterator { private var current = start // Test to see if any more elements exist. override fun hasNext(): Boolean = current <= end // Return the value of the current element // incrementing to the next one. override fun next(): T = self[current++]!! } // ListIterator // Class providing a first in first out template for // a linked list. Updated to insert or remove // anywhere. class List { // Pointers to the head and tail of the list. private var head: Node? = null private var tail: Node? = null var size: Int = 0 private set // Create an interator over the list. operator fun iterator(): Iterator = ListIterator(this, 0, size-1) // Provide this[index] to get read access to the // value within the node in that position. Head // points at index of zero. operator fun get(index: Int): T? = // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. Return // null or the node's value. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while node?.value // Otherwise, the index isn't valid so return // null. } else null // Provide this[index] to get write access to the // value within the node in that position. Head // points at index of zero. operator fun set(index: Int, value: T) { // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while // If we have found the node, update it's // value. if (node != null) node.value = value; } // if } // set // Push a new value on to the tail of the list. fun push(value: T) { // Allocate the new node with the passed in value. // If the head is null, make it point to the new // node. val newNode = Node(value) if (tail == null) head = newNode // Otherwise, make the current last node point to // the new node and the new node point back at it. else { tail?.next = newNode newNode.previous = tail } // if // The tail must point to the new node in either // case and increment the size. tail = newNode size++ } // push fun insert(index: Int, value: T) { // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while // If the node was found, insert the new node // before it. if (node != null) { // Increment the size and if the previous // node doesn't exist, change the list // head to the new node. size++ val newNode = Node(value) if (node?.previous == null) head = newNode // Otherwise, the previous node must point // to the new one. else { var prev = node.previous!! prev.next = newNode newNode.previous = prev } // if // Make the node's next & previous pointer // null. newNode.next = node node?.previous = newNode // Otherwise, we were asked to insert beyond // the last element so put it at the end. } else push(value) // Otherwise, we were asked to insert at an // invalid position so put it at the end. } else push(value) } // insert // Pop the first value off the list. fun pop(): T? = // If the head is null, return it. if (head == null) null // Otherwise, decrement the size, grab the // first node, make next node the new head, // make it's previous null, make the first // node's next pointer null, and return the // value. Note: testing for null shouldn't // be needed, but head might be changed // asynchronously so it is required. else { size-- val node = head head = head?.next head?.previous = null node?.next = null node?.value } // if fun remove(index: Int): T? = // If we have a valid index, find the node. // Start with the head node and copy of the // index. While there is another node and we // haven't found the right one, decrement the // position and move down the list. if (index >= 0) { var node = head var position = index while (node != null && position != 0) { position -= 1 node = node.next } // while // If the node wasn't found, return null. if (node == null) null // Otherwise, remove the node. else { // Decrement the size and if the previous // node doesn't exist, change the list // head to the next node. size-- if (node.previous == null) head = node.next // Otherwise, the previous node must point // to the next one. else { var prev = node.previous!! prev.next = node.next } // If the next node doesn't exist, change // the list tail to the previous node. if (node.next == null) tail = node.previous // Otherwise, the next node must point // to the previous one. else { var next = node.next!! next.previous = node.previous } // Make the node's next & previous pointer // null and return the value. node.next = null node.previous = null node.value } // Otherwise, the index isn't valid so return // null. } else null // This function is called by default to print this // class so make a list of the values in the list. // An integer list will look like: [1, 2, 3]. override fun toString(): String { // Start the finished string with the open // bracket and process the list. var s = "[" var node = head while (node != null) { // Add the current node's value to the string, // move on the next node, and, if there is one, // add the comma to the string. s += "${node.value}" node = node.next if (node != null) s += ", " } // while // Return the finished string with the close // bracket. return s+"]" } // toString } // List // Test the list out. fun main(args: Array) { // Push 20 values on to the list. val list = List() for (value in 1..10) if (value <= 5) list.push(value) else { val index = rand(3, list.size) list.insert(index, value) } // if // Print the completed list and the 3rd element. // Change it's value and print how many elements // there are. println(list) val save = list[3]!! println("save=$save,size=${list.size}") list[3] = 11; // Print list using an iterator. for (element in list) print("$element ") println() // Remove the 3rd node, print the list, and it's // size. list.remove(3) print(list) println(",size=${list.size}") // Insert the save value back into a new node // inserted prior to the current 3rd node and // print the list. list.insert(3, save) println(list) // Pop all of the values and print them. do { if (list.size > 5) { val index = rand(3, list.size-1) print("${list.remove(index)}@$index ") } else print("${list.pop()} ") } while (list.size > 0) println() } // main

LinkList mn