单链表

链表节点

节点的创建和定义；每个节点会有一个保存自己数据的属性(element)，然后有一个指针(next)

// 单向链表节点：这个节点的下一个节点暂时为空
class Node{
    constructor(element,next = null){
        this.element = element
        this.next = next
    }
}

创建单链表

class LinkedList{
    constructor(){
        this.head = null // 头部
        this.length  = 0
    }

    // 查：获取位置节点(遍历：每次指向下一节点，直到position)：非递归！
    getElementAt(position) {
        if(position >= 0 && position <= this.length) {
            let node = this.head;
            for (let i = 0; i < position; i++) {
                node = node.next;
            }
            return node;
        }
        return undefined;
    }
    // 查：链表长度
    size(){
        return  this.length
    }
    // 查：是否为空
    isEmpty() {
        return this.size() === 0;
    }

    // 增:向链表末尾中添加元素
    append(element){
      const node = new Node(element);
        let current = this.head;
        if(current == null) {
            //console.log('第一次')
            this.head = node;
        } else {
            while (!current.next) {
                current = current.next;
            }
            // 插入到最后节点.next
            current.next = node
        }
        this.length ++;
        return element;
    }
    // 增:向链表指定位置中添加元素
    insert (position,element){
        // 防御性
        if (element === undefined) {
            throw Error('缺少需要插入的元素');
            return;
        }
        // 大于等于当前链表长度，插入底部
        if(position >= this.length){
            return this.append(element);
        }
        /**
        *  小于当前链表长度
        */
        const node = new Node(element);
        // 获取当前元素
        const targetNode = this.getElementAt(position)
        // targetNode不存在，插入到顶部
        if(!targetNode){
            let prev = this.head;
            this.head = node;
            node.next = prev;
        }else{
        // 位置交换
            let temp
            temp = targetNode.next
            targetNode.next = node
            node.next = temp
        }
        this.length ++
        return element
    }

    // 删：删除一个元素
    removeAt(position){
        // 获取当前元素
        const targetNode = this.getElementAt(position)

        // 获取当前元素父级
        const targetParentNode = this.getElementAt(position-1) || this.head

        if (position >= 0 && position < this.length) {
        // 获取当前元素子级
        const next = targetNode.next

        if(position === 0){
            this.head = next
        }else{
            targetParentNode.next = next
        }
        this.length --
        }
    }
    // 删：删除链表末端元素
    remove(){
        return this.removeAt(this.size()-1)
    }
    // 删：删除链表所有元素
    clear(){
        this.length = 0
        return this.head = null
    }
}

使用方法:

const list = new LinkedList()
// 增
list.append(1)
list.insert(0,2)
list.append(3)
list.append(4)

// 删
// list.removeAt(0)
// list.remove()
// list.clear()

// 查
// list.size()
// list.isEmpty()
list.getElementAt(0) // 获取位置节点(遍历：每次指向下一节点，直到position)：非递归！

console.log(list)