JS数据结构与算法之单向链表实现

function SingleLinkedList() {
    //内部节点类
    function Node(ele) {
        this.ele = ele
        this.next = null
    }
    this.head = null
    this.length = 0
    //向链表尾部添加新元素
    SingleLinkedList.prototype.append = ele => {
        var newNode = new Node(ele)

        if (this.length == 0) { //是第一个节点
            this.head = newNode
        } else { //不是第一个节点
            // 找最后一个节点
            var current = this.head
            while (current.next) {
                current = current.next
            }
            //让最后节点的next指向新的节点
            current.next = newNode
        }
        //链表长度+1
        this.length += 1

    }
    //向链表的特定位置插入一个新元素
    SingleLinkedList.prototype.insert = (position, ele) => {


        //边界判断,小于0和等于自身长度时值为null
        if (position < 0 || position > this.length) return false
        //创建newNode
        var newNode = new Node(ele)
        //移除位置为0的情况
        if (position === 0) {
            newNode.next = this.head
            this.head = newNode
        } else {
            //查找下标
            var index = 0
            //当前所在
            var current = this.head
            //前一个 ， 默认为null
            var previous = null
            //position要插入元素的位置
            while (index++ < position) {
                //每次循环改变当前所在，将值给previous ， 当前变前一个
                previous = current
                //当前值的下一个赋值给当前
                current = current.next
            }
            newNode.next = current
            previous.next = newNode
        }
        this.length += 1
    }
    //获取对应位置的元素
    SingleLinkedList.prototype.get = position => {
        if (position < 0 || position >= this.length) return null

        var current = this.head
        var index = 0
        while (index < position) {
            current = current.next
            index++
        }
        return current.ele
    }
    //返回元素在链表中的索引，没有则返回-1
    SingleLinkedList.prototype.indexOf = ele => {
        var current = this.head
        var index = 0
        while (current) {
            if (current.ele == ele) {
                return index
            }
            current = current.next
            index += 1
        }
        return -1
    }
    //修改某个位置的元素
    SingleLinkedList.prototype.update = (position, newEle) => {
        if (position < 0 || position >= this.length) return false

        var current = this.head
        var index = 0
        while (index++ < position) {
            current = current.next
        }
        current.ele = newEle
        return true
    }
    //从链表的特定位置移除元素
    SingleLinkedList.prototype.removeAt = position => {
        if (position < 0 || position >= this.length) return false

        if (position == 0) {
            this.head = this.head.next

        } else {
            var index = 0
            var current = this.head
            var previous = null
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = current.next

        }
        this.length -= 1
        return true

    }
    //从链表中移除元素
    SingleLinkedList.prototype.remove = ele => {
        var index = this.indexOf(ele)
        return this.removeAt(index)
    }
    //链表是否为空
    SingleLinkedList.prototype.isEmpty = () => {
        return this.length == 0
    }
    //链表包含的元素个数
    SingleLinkedList.prototype.size = () => {
        return this.length
    }
    //toString
    SingleLinkedList.prototype.toString = () => {
        let current = this.head
        let listStr = ''
        while (current) {
            listStr += current.ele + " "
            current = current.next
        }
        return listStr
    }
}

var list = new SingleLinkedList()
list.append('a')
list.append('b')
list.append('c')
console.log(list.size());
list.insert(0, 'd')
list.insert(2, 'e')
console.log(list);
console.log(list.toString());
console.log(list.get(2));
console.log(list.get(5));
console.log(list.indexOf('b'));
console.log(list.indexOf('A'));
console.log(list.update(0, 'F'));
console.log(list.toString());
console.log(list.removeAt(0));
console.log(list.toString());
console.log(list.remove('a'));
console.log(list.toString());
console.log(list.remove('x'));
console.log(list.toString());
console.log(list.isEmpty());
console.log(list.size());


res:
3
SingleLinkedList {
  head: Node { ele: 'd', next: Node { ele: 'a', next: [Node] } },
  length: 5
}
d a e b c 
e
null
3
-1
true
F a e b c 
true
a e b c 
true
e b c 
false
e b c 
false
3