目录

一、单链表

二、实现

三、小结

一、单链表

单链表是线性表的链式存储，逻辑上相邻的数据在计算机内的存储位置不一定相邻。通过节点进行寻找下一个元素的位置，节点包括：指针和数据。因为指针的指向都是一个方向，所以叫单链表。

二、实现

package Algorithm.list

/*
* 集合
*/
public interface List<E> {
    func add(element: E): Unit
    func remove(index: Int64): Option<E>
    func clear(): Unit
    func isEmpty(): Bool
    func size(): Int64
    func deepClone(): List<E>
    func indexOf(element: Option<E>): Int64
    func contains(element: Option<E>): Bool
    func get(index: Int64): Option<E>
}

/*
* 单链表需要的Node
*/
private class Node<E> {
    // 指针
    private var _next: Option<Node<E>>
    // 数据
    private var _element: Option<E>

    public init(_next: Option<Node<E>>, _element: Option<E>) {
        this._element = _element
        this._next = _next
    }

    public mut prop next: Option<Node<E>> {
        get() {
            return this._next
        }
        set(_next) {
            this._next = _next
        }
    }

    public mut prop element: Option<E> {
        get() {
            return this._element
        }
        set(_element) {
            this._element = _element
        }
    }
}

/*
* 单链表数组
*/
public class MyLinkedList<E> <: List<E> {
    // 保存当前元素长度
    private var length = 0
    private static let NOT_FOUND: Int64 = -1
    // 头节点
    private var first: Option<Node<E>> = Option<Node<E>>.None

    /*
    * 集合长度
    */
    public override func size(): Int64 {
        return this.length
    }

    /*
    * 集合是否为空
    */
    public override func isEmpty(): Bool {
        return this.length == 0
    }

    /*
    * 判断元素是否存在
    */
    public override func contains(element: Option<E>): Bool {
        return indexOf(element) != NOT_FOUND
    }

    /*
    * 检查数组是否越界
    */
    public func checkIndex(index: Int64): Unit {
        if (index < 0 || index >= this.length) {
            throw IndexOutOfBoundsException("索引越界, 允许范围(0, ${this.length - 1}),当前索引: ${index}")
        }
    }
    
    /*
    * 在末尾添加元素
    */
    public override func add(element: E): Unit {
        var node = Node(Option<Node<E>>.None, element)
        if(first.isNone()){
            this.first = node
        } else {
            var last = this.first
            while(last.getOrThrow().next.isSome()){
                last = last.getOrThrow().next
            }
            last.getOrThrow().next = node
        }
        this.length++
    }

    /*
    * 根据索引删除元素
    */
    public override func remove(index: Int64): Option<E> {
        checkIndex(index)
        var oldNode = this.first
        if (index == 0) {
            this.first = this.first.getOrThrow().next
        } else {
            var pre = node(index - 1)
            oldNode = pre.next
            var next = pre.next.getOrThrow().next
            pre.next = next
        }
        this.length--
        return oldNode.getOrThrow().element
    }

    /*
    * 清空链表
    */
    public override func clear(): Unit {
        this.length = 0
        first = Option<Node<E>>.None
    }


    /*
    * 深克隆数组
    */
    public override func deepClone(): List<E> {
        let newElement = MyLinkedList<E>()
        var node = this.first
        for (_ in 0..this.length) {
            newElement.add(node.getOrThrow().element.getOrThrow())
            node = node.getOrThrow().next
        }
        return newElement
    }

    /*
    * 查找元素对应的下标
    */
    public override func indexOf(element: Option<E>): Int64 {
        var node = this.first
        if (element.isNone()) {
            for (i in 0..this.length) {
                if (node.getOrThrow().element.isNone()) {
                    return i
                }
                node = node.getOrThrow().next
            }
        } else {
            for (i in 0..this.length) {
                if (node.getOrThrow().element.isSome()) {
                    return i
                }
                node = node.getOrThrow().next
            }
        }
        return NOT_FOUND
    }

    /*
    * 获取对应索引的值
    */
    public override func get(index: Int64): Option<E> {
        // 越界处理
        checkIndex(index)
        return node(index).element
    }

    /*
    * 获取节点
    */
    private func node(index: Int64): Node<E> {
        // 越界处理
        checkIndex(index)
        // 获取头节点
        var optNode = this.first.getOrThrow()
        for (_ in 0..index) {
            optNode = optNode.next.getOrThrow()
        }
        return optNode
    }
}

测试代码

package Algorithm
import Algorithm.list.*
 
main(): Int64 {
    let arr = MyLinkedList<Int64>()
    println("添加元素")
    arr.add(0)
    arr.add(11)
    arr.add(22)
    arr.add(33)
    arr.add(44)
    arr.add(55)
    arr.add(66)
    arr.add(77)
    arr.add(88)
    arr.add(99)
    arr.add(100)
    for (i in 0..arr.size()) {
        print("${arr.get(i).getOrThrow()} ")
    }
    println("数组长度: ${arr.size()}")
    println("删除元素")
    arr.remove(0)
    for (i in 0..arr.size()) {
        print("${arr.get(i).getOrThrow()} ")
    }
    println("数组长度: ${arr.size()}")

    println("克隆数组")
    let newArr = arr.deepClone()
    newArr.add(1000)
    for (i in 0..newArr.size()) {
        print("${newArr.get(i).getOrThrow()} ")
    }
    println("数组长度: ${newArr.size()}")
    println("原始数组")
    for (i in 0..arr.size()) {
        print("${arr.get(i).getOrThrow()} ")
    }
    println("数组长度: ${arr.size()}")
    return 0
}

三、小结

本章为大家详细的介绍了仓颉数据结构与算法中单链表的内容，下一章，为大家带来双向链表的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！