文章目录
- 数据结构和算法,单链表的实现(kotlin版)
- b站视频链接
- 1.定义接口,我们需要实现的方法
- 2.定义节点,表示每个链表节点。
- 3.push(e: E),链表尾部新增一个节点
- 4.size(): Int,返回链表的长度
- 5.getValue(index: Int): E?,获取列表的value值
- 6.insert(index: Int,e: E),从任意位置插入一个节点
- 7.remove(index: Int),任意位置删除一个节点
- 8.完整Demo
数据结构和算法,单链表的实现(kotlin版)
b站视频链接
单链表的实现–koltin版本
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 value: E)
3.push(e: E),链表尾部新增一个节点
override fun push(e: E) {val newNode = Node(null, e)if (head != null) {
// val lastNode = node(len - 1)//O(1)时间复杂度last?.next = newNode} else {head = newNode}last = newNodelen++}
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>? {var h = head//O(n)时间复杂度for (i in 0 until index) {h = h?.next}return h}
6.insert(index: Int,e: E),从任意位置插入一个节点
override fun insert(index: Int, e: E) {val newNode = Node(null, e)//考虑边界if (index == 0) {val h = headhead = newNodenewNode.next = h} else {//考虑最后一个位置val prev = node(index - 1)val next = prev?.nextprev?.next = newNodenewNode.next = next}len++}//找到对应index下标的节点。private fun node(index: Int): Node<E>? {var h = head//O(n)时间复杂度for (i in 0 until index) {h = h?.next}return h}
7.remove(index: Int),任意位置删除一个节点
override fun remove(index: Int) {if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("数组越界.....")}if (index == 0) {val h = headhead = h?.nexth?.next = null} else {val prev = node(index - 1)val current = prev?.nextprev?.next = current?.nextcurrent?.next = null}len--}//找到对应index下标的节点。private fun node(index: Int): Node<E>? {var h = head//O(n)时间复杂度for (i in 0 until index) {h = h?.next}return h}
8.完整Demo
package day1class LinkedList<E> : LinkedListAction<E> {//头指针private var head: Node<E>? = null//优化时间复杂度private var last: Node<E>? = null//集合的长度private var len = 0override fun push(e: E) {val newNode = Node(null, e)if (head != null) {
// val lastNode = node(len - 1)//O(1)时间复杂度last?.next = newNode} else {head = newNode}last = newNodelen++}//找到对应index下标的节点。private fun node(index: Int): Node<E>? {var h = head//O(n)时间复杂度for (i in 0 until index) {h = h?.next}return h}override fun size(): Int {return len}override fun getValue(index: Int): E? {if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("数组越界.....")}return node(index)?.value}override fun insert(index: Int, e: E) {val newNode = Node(null, e)//考虑边界if (index == 0) {val h = headhead = newNodenewNode.next = h} else {//考虑最后一个位置val prev = node(index - 1)val next = prev?.nextprev?.next = newNodenewNode.next = next}len++}override fun remove(index: Int) {if (index < 0 || index >= len) {throw ArrayIndexOutOfBoundsException("数组越界.....")}if (index == 0) {val h = headhead = h?.nexth?.next = null} else {val prev = node(index - 1)val current = prev?.nextprev?.next = current?.nextcurrent?.next = null}len--}}