Examples of Implementation Methods of Stack and LinkedList in Kotlin

Preface

This article mainly introduces the basic data structure of Kotlin, Stack and LinkedList, which are shared for everyone's reference and study. The following words are not much to say, let's take a look at the detailed introduction.

Stack

Stack in Java is implemented by List, Kotlin has MutableList, and the basic definition of Stack class is as follows, inheriting Iterator for iterative traversal:

class Stack<T : Comparable<T>>(list : MutableList<T>) : Iterator<T> 

Basic attribute implementation

// stack Adj. count
 var itCounter: Int = 0

// stack The internal implementation is MutableList
 var items: MutableList<T> = list

//  Judge stack Whether it is null
fun isEmpty(): Boolean = this.items.isEmpty()

//  Get stack Adj. items counte
fun count(): Int = this.items.count()

// tostring Operation 
 override fun toString(): String {
  return this.items.toString()
 }

Basic operation implementation

// pop Operation, the top element of the stack, that is, the end element of the linked list, can be null
 fun pop(): T? {
 if (this.isEmpty()) {
  return null
 } else {
  val item = this.items.count() - 1
  return this.items.removeAt(item)
 }
}

//  Read-only operation, no pop-up 
fun peek(): T? {
 if (isEmpty()) {
  return null
 } else {
  return this.items[this.items.count() - 1]
 }


}

// hasNext Operation 
override fun hasNext(): Boolean {
 val hasNext = itCounter < count()
 if (!hasNext) itCounter = 0
 return hasNext
}

//  Take next Element 
override fun next(): T {
 if (hasNext()){
  val topPos : Int = (count() - 1) - itCounter
  itCounter++
  return this.items[topPos]
 }else{
  throw NoSuchElementException("No such element") //  Exceptionally unused new Oh 
 }
}

LinkedList

The implementation of LinkedList requires Node, and then implements first, last, count, append and other operations.

Node Definition

class Node<T>(value : T){
 var value : T = value // value Can be of any type 
 var next : Node<T>? = null // next Can be null
 var previous : Node<T>? = null // pre It can also be used for null
}

Basic Operation 1

//  Head node, guiding function 
var head : Node<T>?= null

//  Depend on head Whether it is null
var isEmpty : Boolean = head == null

//  Get first
fun first() : Node<T>? = head

//  Get last Node, required 1 Straight next To reach last Node 
fun last() : Node<T>?{
 var node = head
 if (node != null){ 
  while (node?.next != null){
   node = node?.next
  }
  return node
 }else{
  return null
 }
}

Basic Operation 2

//  Get count , also passed next Calculation 
fun count():Int {
 var node = head
 if (node != null){
  var counter = 1
  while (node?.next != null){
   node = node?.next
   counter += 1
  }
  return counter
 } else {
  return 0
 }
}

// append Operation , In last On a node append
fun append(value : T){
 var newNode = Node(value)
 //  Gets the last of the current node 1 Nodes 
 var lastNode = this.last()
 if (lastNode != null){
  newNode.previous = lastNode
  lastNode.next = newNode
 }else{
  head = newNode
 }
}

//  Delete operation 
fun removeNode(node : Node<T>) : T{
 val prev = node.previous
 val next = node.next

 if (prev != null){
  prev.next = next
 }else{
  head = next
 }
 next?.previous = prev

 node.previous = null //  Place the disconnected node forward and backward null
 node.next = null

 return node.value //  Returns the of the deleted node value
}

Above, the basic data structures stack and linkedlist are realized by kotlin.

Summarize