js-数据结构-链表

数组

依次存储

• 缺点： 对数组做删除或者插入的时候，可能需要移动大量的元素

栈 ： push，pop
队列：push，shift

双向链表结构

• 可重复添加key值相同的元素
• 记录插入顺序

class ListNode {
    constructor(key) {
        // 指向前一个节点
        this.prev = null;
        // 指向后一个节点
        this.next = null;
        // 节点的数据(或者用于查找的键)
        this.key = key;
    }
}
/**
 * 双向链表
 */
class List {
    constructor() {
        this.head = null; //引用上一个数据
    }
    static createNode(key) {
        return new ListNode(key);
    }
    insert(node) {
        node.prev = null;	//父
        node.next = this.head; //子
        if (this.head) {
            this.head.prev = node;
        }
        this.head = node;
    }
    search(key) {
        let node = this.head;
        while (node !== null && node.key !== key) { //从底部查询，查询后退出
            node = node.next;
        }
        return node;
    }
    delete(node) {
        const { prev, next } = node;
        delete node.prev;
        delete node.next;

        if (node === this.head) {
            this.head = next;
        }

        if (prev) {
            prev.next = next;
        }
        if (next) {
            next.prev = prev;
        }
    }
}

let pop = new List();

pop.insert(List.createNode('lml1'))
pop.insert(List.createNode('lml2'))
pop.insert(List.createNode('lml3'))
pop.insert(List.createNode('lml2')) //可重复key
// 
// pop.insert({key:'lml1'})
// pop.insert({key:'lml2'})
// pop.insert({key:'lml3'})

console.log(pop);
console.log(pop.search('lml2'));

var kvArray = [["key1", "value1"], ["key2", "value2"]];
var myMap = new Map(kvArray);
myMap.set('key1','lml3')
console.log(Array.from(myMap));
// pop.delete(pop.search('lml2'))
// console.log(pop);
// console.log(pop.search('lml2'));

var a = new Set([1, 2, 3]);
var b = new Set([4, 3, 2]);
var difference = new Set([...a].filter(x => !b.has(x))); // {1}