数据结构和算法，双向链表的实现增删改查(kotlin版)

数据结构和算法，双向链表的实现增删改查(kotlin版)

1.定义接口，我们需要实现的方法

interface LinkedListAction<E> {fun push(e: E)fun size(): Intfun getValue(index: Int): E?fun insert(index: Int,e: E)fun remove(index: Int)
}

2.定义节点，表示每个链表节点。

data class Node<E>(var next: Node<E>? = null, var prev: Node<E>? = null, var value: E)

3.push(e: E)，链表尾部新增一个节点

override fun push(e: E) {linkLast(e)len++}
private fun linkLast(e: E) {var l = lastval newNode = Node(null, last, e)last = newNodeif (head != null) {l?.next = newNode} else {head = newNode}}

4.size(): Int，返回链表的长度

override fun size(): Int {return len}

5.getValue(index: Int): E?，获取列表的value值

   override fun getValue(index: Int): E? {if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("数组越界.....")}return node(index)?.value}//找到对应index下标的节点。private fun node(index: Int): Node<E>? {if (index < (len shr 1)) {var cur = headfor (i in 0 until index) {cur = cur?.next}return cur} else {var cur = lastfor (i in (len - 1) downTo index + 1) {cur = cur?.prev}return cur}}

6.insert(index: Int,e: E)，从任意位置插入一个节点

override fun insert(index: Int, e: E) {if (index < 0 || index > len) {throw ArrayIndexOutOfBoundsException("数组越界.....")}if (index == len) {linkLast(e)} else {linkBefore(node(index), e)}len++}
private fun linkLast(e: E) {var l = lastval newNode = Node(null, last, e)last = newNodeif (head != null) {l?.next = newNode} else {head = newNode}}private fun linkBefore(cur: Node<E>?, e: E) {val prev = cur?.prevval newNode = Node(cur, prev, e)cur?.prev = newNodeif (prev != null) {prev.next = newNode} else {head = newNode}}

7.remove(index: Int)，任意位置删除一个节点

override fun remove(index: Int) {if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("数组越界.....")}unlike(node(index))len--}
private fun unlike(cur: Node<E>?): E? {val value = cur?.valueval prev = cur?.prevval next = cur?.nextif (prev != null) {prev.next = next} else {head = next}if (next != null) {next.prev = prev} else {last = prev}return value}

8.完整Demo

package day5class LinkedList<E> : LinkedListAction<E> {//头节点指针private var head: Node<E>? = null//尾部节点指针private var last: Node<E>? = null//链表总长度private var len = 0//尾插法override fun push(e: E) {linkLast(e)len++}//尾插法private fun linkLast(e: E) {//保存last指针val l = last//新创建的节点val newNode = Node(null, last, e)//last指针指向新节点last = newNode//如果head不为空，next赋值为新节点if (head != null) {l?.next = newNode} else {//否则头节点为最新节点head = newNode}}//返回链表的长度override fun size(): Int {return len}//获取节点的Value值override fun getValue(index: Int): E? {//判断是否index越界if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("越界异常.............")}//拿到index节点的valuereturn node(index)?.value}//获取index对应的节点private fun node(index: Int): Node<E>? {//右移一位，相当于 len / 2return if (index < (len shr 1)) {//从前面往后便利，临时指针cur指向headvar cur = head//移动nextfor (i in 0 until index) {cur = cur?.next}//找到对应的index节点cur} else {//否则从后往前便利var cur = lastfor (i in (len - 1) downTo index + 1) {cur = cur?.prev}//找到对应的index节点cur}}//指定位置插入节点override fun insert(index: Int, e: E) {if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("越界异常.............")}//判断插入的index == len就插入在后面if (index == len) {linkLast(e)} else {//否则插入对应的节点的位置上linkBefore(node(index), e)}len++}//链接到对应的节点位置的前面private fun linkBefore(cur: Node<E>?, e: E) {//保存prev指针val prev = cur?.prev//创建新节点val newNode = Node(cur, prev, e)//插入到index的节点的前面cur?.prev = newNode//prev不为空if (prev != null) {//prev.next接入新节点prev.next = newNode} else {//prev为空的话,插入头节点位置head = newNode}}//删除元素override fun remove(index: Int) {if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("越界异常.............")}unlike(node(index))len--}//找到index对应节点删除private fun unlike(cur: Node<E>?): E? {//获取当前节点valuevar value = cur?.value//获取当前节点的前驱节点val prev = cur?.prev//获取next指针val next = cur?.next//判断临界值if (prev != null) {//前驱节点的next指向cur当前节点的nextprev.next = next} else {//没有前驱节点head = next}//判断临界值if (next != null) {//后驱节点的prev指向cur当前节点的prevnext.prev = prev} else {//没有后驱节点last = prev}return value}
}