JS实现单链表

要存储多个元素，数组（或列表）可能是最常用的数据结构。但这种数据结构有一个缺点：（在大多数语言中）数据的大小是固定的，从数组的起点或中间插入或移除项的成本很高。
链表存储有序的集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
相对于传统的数组，链表的一个好处是，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。
举个例子，我们玩寻宝游戏，你有一条线索，这条线索是指向寻找下一条线索的地点的指针。你沿着这条链接去下一个地点，得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法，就是从起点（第一条线索）顺着列表去寻找。
让我们用JS实现最简单的单链表:

function LinkedList() {

    // Node辅助类，表示要加入列表的项，element是即将添加到列表的值，next是指向列表中下一个节点项的指针
    let Node = function (element) {
        this.element = element
        this.next = null
    }

    let length = 0
    let head = null

    // 向链表尾部追加元素
    this.append = function (element) {
        let node = new Node(element)
        let current
        if (head === null) { // 列表中第一个节点
            head = node
        } else {
            current = head
            while (current.next) {
                current = current.next // 找到最后一项，是null
            }
            current.next = node // 给最后一项赋值
        }
        length++ // 更新列表的长度
    }

    // 从链表中移除指定位置元素
    this.removeAt = function (position) {
        if (position > -1 && position < length) { // 值没有越界
            let current = head
            let previous, index = 0
            if (position === 0) { //  移除第一项
                head = current.next
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = current.next // 将previous与current的下一项连接起来，跳过current，从而移除
            }
            length-- // 更新列表的长度
            return current.element
        } else {
            return null
        }
    }

    // 在链表任意位置插入一个元素
    this.insert = function (position, element) {
        if (position >= 0 && position <= length) { // 检查越界值
            let node = new Node(element),
                current = head,
                previous,
                index = 0
            if (position === 0) { // 在第一个位置添加
                node.next = current
                head = node
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                node.next = current // 在previous与current的下一项之间插入node
                previous.next = node
            }
            length++
            return true
        } else {
            return false
        }
    }

    // 把链表内的值转换成一个字符串
    this.toString = function () {
        let current = head,
            string = ''
        while (current) {
            string += current.element + ' '
            current = current.next
        }
        return string
    }

    // 在链表中查找元素并返回索引值
    this.indexOf = function (element) {
        let current = head,
            index = 0
        while (current) {
            if (element === current.element) {
                return index
            }
            index++
            current = current.next
        }
        return -1
    }

    // 从链表中移除指定元素
    this.remove = function (element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }

    this.isEmpty = function () {
        return length === 0
    }

    this.size = function () {
        return length
    }

    this.getHead = function () {
        return head
    }
}
let list = new LinkedList()
list.append(1)
list.append(2)
console.log(list.toString()) // 1 2
list.insert(0, 'hello')
list.insert(1, 'world')
console.log(list.toString()) // hello world 1 2
list.remove(1)
list.remove(2)
console.log(list.toString()) // hello world

单链表有一个变种 - 循环链表，最后一个元素指向下一个元素的指针，不是引用null，而是指向第一个元素，只需要修改下最后的next指向为head即可。

最后编辑于：2019.05.14 17:23:11