链表的创建、遍历、插入、删除、查找、更新

以下内容基于kotlin语言，讲解都在注释里面，都是我自己的理解，错误的地方还请多多指教

• 创建一个链表

//创建链表
class Node{
    var id:Int? = null
    var next:Node? = null
}

• 初始化链表

//初始化链表
fun createLinkedList():Node?{
    var head:Node? = null //头结点
    var newnode:Node //每次需要创建的节点
    var last:Node = Node() //尾节点
    for (i in 0 until 10){
        //创建新的节点
        newnode = Node()
        newnode.id = i + 10086
        if (i == 0){//列表为空时，头结点 -> 新创建的这个节点
            head = newnode
        }else{//不为空时，就把最后一个节点的next -> 新创建的节点
            last.next = newnode
        }
        last = newnode//保证last是最后一个节点
    }
    //这一步可以忽略，因为在初始化未赋值时next为null，但是next对象在初始化时不能接受null时，这一步就不能少
    last.next = null
    return head
}

• 遍历链表

//遍历链表
fun Node?.loopThroughLinkedList(){
    var tmp:Node? = this
    if (tmp == null){
        return
    }else{
        print("Current:$tmp  Id:${tmp.id} Next:${tmp.next}\n")
        tmp = tmp.next
    }
    tmp.loopThroughLinkedList()
}

• • 获取链表长度

//获取链表长度
fun Node?.linkedListLength():Int{
    if (this == null){
        return  0
    }
    var length:Int = 0
    var tmp:Node? = this
    while (tmp?.next != null){
        tmp = tmp?.next
        length += 1
    }
    length += 1//把最后一个节点也算进去
    return length
}

• 插入

//插入
fun Node?.insert(insertNode: Node,index:Int):Node?{
    val length = this.linkedListLength()
    var tmpNode:Node? = this

    if (index < 0 || index > length-1){
        throw IllegalArgumentException("超出链表范围")
    }
    if (index == 0){//头部插入
        insertNode.next = tmpNode//1、将插入节点指向头结点
        tmpNode = insertNode//2、将头指针指向插入的节点
        return  tmpNode
    }else if (index == length-1){//尾部插入
        while (tmpNode?.next != null){//1、当tmpNode为最后一个节点时跳出while循环
            tmpNode = tmpNode.next
        }
        tmpNode?.next = insertNode//2、然后将尾节点指向插入的节点
        insertNode.next = null//3、保持插入节点是最后一个节点，因为插入节点的next初始化时就为null，所以这一步也可以省略
        return this
    }else{//中间位置插入

        var node:Node? = Node()
        for (i in 0 until (index - 1)){
            if (tmpNode?.next != null){
                tmpNode = tmpNode.next//1、找到第n-1个节点
            }
        }
        //2、找到第n个节点
        tmpNode?.next = insertNode//3、将第n-1个节点指向插入的节点
        insertNode.next = node//4、将插入的节点指向原来的第n个节点
        return this
    }
}

• 删除

//删除
fun Node?.delete(index:Int):Node?{
    val length = this.linkedListLength()
    var i = if (index >= length) length else index
    var tmp = this
    var pre:Node? = Node()
    for (i in 0 until index){
        if (tmp?.next != null){
            pre = tmp//获取要删除节点的前一个节点
            tmp = tmp.next//要删除的节点
        }
    }
    if (tmp == this){//如果要删除的是头结点
        return tmp?.next
    }
    pre?.next = tmp?.next//重新进行指向
    tmp = null//释放被删除的节点
    return this
}

• 查找

//查找
fun Node?.find(index: Int):Node?{
    var tmp = this
    val length = this.linkedListLength()
    if (index < 0 || index > length-1){
        throw IllegalArgumentException("超出链表范围")
    }

    for (i in 0 until index){
        if (tmp?.next != null){
            tmp = tmp.next
        }
    }
    return tmp
}

• 更新

//更新
fun Node?.update(index: Int,id:Int):Node?{
    var tmp = this
    val length = this.linkedListLength()
    if (index < 0 || index > length-1){
        throw IllegalArgumentException("超出链表范围")
    }
    for (i in 0 until index){
        if (tmp?.next != null){
            tmp = tmp.next
        }
    }
    tmp?.id = id
    return this
}