JS数据结构与算法（单向链表的封装）

链表有什么用？
链表的作用是存储数据，跟数组不同的是链表性能更优，比如占用内存等
但无法通过下标快速索引,只能通过线性查找
链表基本模型.png
// 封装链表类
function linkedLists() {
    //定义链表默认属性
    this.head = null
    this.length = 0
    //定义节点类Node
    function Node(data) {
        this.data = data
        this.next = null
    }
    // 定义链表的追加方法
    this.append = function (data) {
        // 1、创建对象节点newNode
        const newNode = new Node(data)
        // 2、判断链表当前是否有节点
        if (this.length === 0) { // 2.1、没有节点 把对象节点赋值给head **追加成功
            this.head = newNode
        } else {
            // 2.2、有节点  查找最后一个节点 此时head必定有值
            let current = this.head
            // 当head的next节点不为空时
            while (current.next) {
                current = current.next
            }
            // 循环完毕后的current 为最后一个节点 把newNode赋值给他 **追加成功
            current.next = newNode
        }
        // 添加节点成功length+1
        this.length += 1
    }

    // 定义链表的插值方法
    this.insert = function (position, data) {
        // 1、判断position值是否合理   👇不能在链表后面留空
        if (position < 0 || position > this.length) return false
        // 2、创建新节点
        const newNode = new Node(data)
        // 3、进行插值操作
        // 3.1、情况1 插入为第一个节点 需要把head指向插入节点  插入节点next指向原来的第一个节点
        if (position === 0) {
            newNode.next = this.head
            this.head = newNode
        }
        // 3.2情况2、 插入到后续节点 只需要知道插入位置原来的节点的索引 原来的节点会往后移动
        let index = 0
        let current = this.head
        let previousCurrent = null
        // 利用while循环获得前一个节点以及当前节点
        while (index++ < position) {
            previousCurrent = current
            current = current.next
        }

        // 插入节点
        newNode.next = current
        previousCurrent.next = newNode
        // 4、length+1
        this.length += 1
        return true
    }

    // 定义链表的get方法 返回对应值
    this.get = function (position) {
        // position不能等于链表长度 因为最后一个链指向的是null
        if (position < 0 || position >= this.length) return null
        let index = 0
        let current = this.head
        while (index++ < position) {
            current = current.next
        }
        return current.data
    }

    // 定义链表的indexOf方法 返回索引
    this.indexOf = function (data) {
        if (this.length === 0) return null
        let index = 0
        let current = this.head
        while (index++ < this.length) {
            if (current.data === data) {
                return index - 1
            }
            current = current.next
        }
        return '-1'
    }

    // 定义链表的update方法 更新数据
    this.update = function (position, data) {
        if (position < 0 || position >= this.length) return false
        let current = this.head
        let index = 0
        while (index++ < position) {
            current = current.next
        }
        current.data = data
        return true
    }

    // 定义链表的removeAt方法 删除特定位置数据
    this.removeAt = function (position) {
        if (position < 0 || position >= this.length) return false
        let index = 0
        let current = this.head
        let previousCurrent = null
        if (position === 0) {
            // 一个节点没有被引用就会被回收 所以不需要将current赋值为空
            this.head = current.next
            return true
        }
        while (index++ < position) {
            // 前一个
            previousCurrent = current
            // 当前
            current = current.next
        }
        previousCurrent.next = current.next
        this.length -= 1
        return current.data
    }

    // 定义链表的remove方法 删除指定数据
    this.remove = function (data) {
        let position = this.indexOf(data)
        this.removeAt(position)
    }

    // 定义链表的isEmpty方法 判断链表是否为空
    this.isEmpty = function () {
        if (this.length === 0) {
            return true
        } else {
            return false
        }
    }

    // 定义链表的size方法 获取链表长度
    this.size = function () {
        return this.length
    }

    // 定义链表的toString方法
    this.toString = function () {
        // 此时的head已经为链表结构
        let current = this.head
        let listStr = ''
        // 一开始不用判断current.next 因为只追加一个节点的话next为空
        while (current) {
            listStr += current.data + ' '
            // 避免死循环 如果next无值循环break
            current = current.next
        }
        // 否则返回空字符串
        return listStr
    }
}

// 创建实例对象
const link = new linkedLists()
// 调用方法
link.append('abc')
link.append('fgh')
link.insert(1, '这是插入到1的字符')
console.log(link.toString()) // abc 这是插入到1的字符 fgh 

console.log(link.get(1)) // 这是插入到1的字符

console.log(link.indexOf('这是插入到1的字符')) // 1

link.update(2, '这是更新后的2')
console.log(link.toString()) // abc 这是插入到1的字符 这是更新后的2 

// 调用删除方法一 接续上方
// console.log(link.removeAt(0)) // abc 这是插入到1的字符 
// link.removeAt(2)
// console.log(link.toString()) // abc 这是插入到1的字符 
// console.log(link.length) // 2

// 调用删除方法二 接续上方
link.remove('这是更新后的2')
console.log(link.toString()) // abc 这是插入到1的字符 
console.log(link.length) // 2
总结:
1、底层封装需要自己定义类对象的默认属性，无法调用任何api
2、封装方法时先进行越界判断利用while循环找出目标节点
3、链表模型可以抽象成火车，前后必须用next引用连接,最后一节的node节点next引用为null