链表LinkedList的实现

所谓链表是由一组不必相连【不必相连:可以连续也可以不连续】的内存结构 【节点】,按特定的顺序链接在一起的抽象数据类型。

每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(可以称为指针)组成。

链表
链表(图片来源于网络)

现实中也有不少链表的例子,例如火车一节一节的车厢,每节车厢之间都是相互连接的,我们就可以把每节车厢看做一个元素,车厢与车厢之间的连接就是指针。

LinkedList类包括如下的这些方法:

  • append(element):向列表尾部添加一个新元素。
  • removeAt(position):删除列表中指定位置的元素。
  • insert(position, element):删除列表中指定位置的元素。
  • indexOf(element):返回指定元素在列表中的位置。
  • remove(element):删除指定元素。
  • isEmpty():列表是否为空。
  • size():列表的大小。

append(element)为例,向LinkedList对象尾部添加一个元素时,可能存在两种情况:列表为空,添加是列表的第一个元素;列表不为空,则向其追加元素。

使用head记录链表的第一个元素,当链表为空时,直接将元素赋值给head。当不为空时,使用current维护当前元素便于理解,然后一直遍历到链表的末尾,在末尾追加该元素,即将原链表最后一个元素的next指向新元素。最后,维护length的值。

其余的实现方式不再赘述,具体看实现细节。

const LinkedList = (function () {
    let head = null,
        length = 0

    const Node = class {
        constructor(element) {
            this.element = element
            this.next = null
        }
    }

    class LinkedList {
        //向列表尾部添加一个新元素
        append(element) {
            let node = new Node(element)
            if (head === null) {
                head = node
            } else {
                let current = head
                while (current.next) {
                    current = current.next
                }
                current.next = node
            }
            length++
        }

        //删除列表中指定位置的元素
        removeAt(position) {
            if (position > -1 && position < length) {
                let current = head
                if (position === 0) {
                    head = current.next
                } else {
                    let index = 0,
                        prev = null
                    while (index++ < position) {
                        prev = current
                        current = current.next
                    }
                    prev.next = current.next
                }
                length--
                return current.element
            }
            return null
        }

        //向列表指定位置新增一个元素
        insert(position, element) {
            if (position > -1 && position < length) {
                let current = head,
                    node = new Node(element)
                if (position === 0) {
                    node.next = current
                    head = node
                } else {
                    let index = 0,
                        prev = null
                    while (index++ < position) {
                        prev = current
                        current = current.next
                    }
                    prev.next = node
                    node.next = current
                }
                length++
                return true
            }
            return false
        }

        //返回指定元素在列表中的位置
        indexOf(element) {
            let current = head,
                index = -1
            while (current) {
                if (current.element === element) {
                    return index
                }
                current = current.next
                index++
            }
            return -1
        }

        //删除指定元素
        remove(element) {
            const position = this.indexOf(element)
            return this.removeAt(position)
        }

        //是否为空
        isEmpty() {
            return length === 0
        }

        //列表长度
        size() {
            return length
        }

        //第一个元素,便于外部迭代
        getHead() {
            return head
        }

        toString() {
            let current = head,
                str = ''
            while (current) {
                str += `element:${current.element} next: ${current.next ? `${current.next.element}\r\n` : 'null'}`
                current = current.next
            }
            return str
        }
    }

    return LinkedList
}())

const linkedList = new LinkedList()
linkedList.append('a')
linkedList.append('b')
linkedList.insert(1, 'c')
linkedList.append('hello wolrd')
linkedList.removeAt(2)
console.log(linkedList.toString());

//输出结果为
// element:a next: c
// element:c next: hello wolrd
// element:hello wolrd next: null
如果您觉得本文对您有用,欢迎捐赠或留言~
微信支付
支付宝

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注