JavaScript实现一个链表结构源码分享

写在前面

链表结构介绍

• 单向链表

• 双向链表

• 单向循环链表

• 双向循环链表

• 环形链表

源码实现

/**
 * @author clearlove
 * @class Node   当前节点
 * @class LinkedList 当前链表
 * @function appendNode  添加节点
 * @function getNode  根据索引查找节点元素
 * @function appendAt  根据位置插入节点
 * @function remove    移除节点
 * @function searchCurrIndexof 根据元素查找索引
 * @function sort  链表排序
 * @function linkedToArr 链表转为数组
 * @function arrToLinked 数组转为链表
 * 
 */
//声明一个Node节点
class Node {
    constructor(data) {
        this.data = data
        this.next = null
    }
}
class LinkedList {
    constructor() {
            this.size = 0
            this.head = null
        }
        //增加一个节点
    appendNode(tempNode) {
            let node = new Node(tempNode)
                //判断一下当前的链表是不是一个空的 this.head === null 或者是当前的链表的长度为0
            if (this.head === null) {
                //如果是空的，那么我们的当前的节点就是第一位
                this.head = node
            } else {
                //如果不是空的，我们要做的是，将当前的节点追加到当前链表的最后一位的后面，
                //也就是我们首先需要找到当前链表的最后一位，让后将他的next给当前的node
                let current = this.getNode(this.size - 1) //找到当前的最后一位
                current.next = node
            }
            //链表的长度追加
            this.size++
        }
        //找到当前一个 的节点
    getNode(index) {
            if (index < 0 || index >= this.size) {
                throw new Error('error')
            }
            let current = this.head
            for (let i = 0; i < index; i++) {
                current = current.next
            }
            return current
        }
        //按照指定位置增加
    appendAt(position, tempNode) {
            //首先要知道当前的位置是不是小于0  或者是大于当前链表的长度
            if (position < 0 || position > this.size) {
                throw new Error('error')
            }
            let node = new Node(tempNode)
            if (position === 0) {
                //从第一位开始追加，说明我们需要将当前的node的下一位等于之前的第一位，再将head等于当前的node
                node.next = this.head
                this.head = node
            } else {
                //如果当前位置插入一个节点，需要做的就是将插入位置的之前节点的位置找到即可
                let pre = this.getNode(position - 1)
                node.next = pre.next
                pre.next = node
            }
            this.size++
        }
        //删除指定节点的元素
    remove(position) {
        //首先要知道当前的位置是不是小于0  或者是大于当前链表的长度
        if (position < 0 || position > this.size) {
            throw new Error('error')
        }
        //先将当前头部节点找到
        let currentHead = this.head
        if (position === 0) {
            //说明当前我要删除的是第一位的节点,那么更新头部的信息为之前的节点的next
            this.head = currentHead.next
        } else {
            //如果链表中的某一个节点的删除的时候，我们需要做的就是找到删除的节点的前一个节点，然后将前一个节点的next等于被删除的节点的next
            let pre = this.getNode(position - 1)
            currentHead = pre.next
            pre.next = currentHead.next
        }
        this.size--
    }

    //按照指定元素的索引
    searchCurrIndexof(tempNode) {
            //从头部开始找
            let current = this.head
            for (let i = 1; i < this.size; i++) {
                if (current.data === tempNode) {
                    return i
                }
                current = current.next
            }
            //完全找不到的时候我们直接返回-1或者false都可以
            return -1
        }
        //排序
    sort(tempLinked) {
            let tempArr = this.linkedToArr(tempLinked)
            let maxL = tempArr.length - 1
            for (let j = 0; j < maxL; ++j) {
                let flag = true
                for (let i = 0; i < maxL - j; ++i) {
                    if (tempArr[i] > tempArr[i + 1]) {
                        let temp = tempArr[i]
                        tempArr[i] = tempArr[i + 1]
                        tempArr[i + 1] = temp
                        flag = false
                    }
                }
                if (flag) {
                    break
                }
            }
            return this.arrToLinked(tempArr)
        }
        //链表转为数组
    linkedToArr(tempLinked) {
            let result = []
            let headNode = tempLinked.head
            while (headNode) {
                result.push(headNode.data)
                headNode = headNode.next
            }
            return result
        }
        //数组转为链表
    arrToLinked(tempArr) {
        let ll = new LinkedList()
        tempArr.map(res => {
            ll.appendNode(res)
        })
        return ll
    }
}

测试结果

//测试
let ll = new LinkedList()
ll.appendNode(1)
ll.appendNode(2)
ll.appendNode(3)
ll.appendAt(3, 'jim')
ll.appendNode(4)
//这里是为了将结果全部展开，所以序列化一下
console.log(JSON.stringify(ll))

最后