js 创建一条通用链表
javascript 开发需要「链表」吗？
图解链表
实现双向链表
·
·
JavaScript
1 2 3 4 5 6 7 | function generateNode(data) { return { data: data, // 数据域 next: null, // 前驱指针 prev: null // 后继指针 } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | let HEAD, TAIL, POINTER, length = 0; // 创建一条长度为5的双向链表 [0, 1, 2, 3, 4].forEach((data, index, arr) => { let node = generateNode(data); // 第一个节点 if(index === 0) { HEAD = node; } else { // 指定前驱后继指针 [node.prev, POINTER.next] = [POINTER, node]; // 最后一个节点 index === arr.length - 1 && (TAIL = node) } // 指向当前节点 POINTER = node; ++length; }); // 游标指针回退到头部 POINTER = HEAD; |
定制 APIs
Name | Detail | Name | Detail | Name | Detail | Name | Detail |
shift | 参见数组 | unshift | 参见数组 | pop | 参见数组 | push | 参见数组 |
slice | 参见数组 | splice | 参见数组 | concat | 参见数组 | reverse | 参见数组 |
sort | 参见数组 | indexOf | 参见数组 | length[属性] | 参见数组 | – | – |
at | 指针定位 | prev | 指针前移 | next | 指针后退 | curr | 当前指针 |
first | 头节点 | last | 尾节点 | remove | 删除节点 | clone | 克隆链表 |
insertAfter | 插入节点 | insertBefore | 插入节点 | insertChainAfter | 插入链表 | insertChainBefore | 插入链表 |
HEAD[属性] | 头指针 | TAIL[属性] | 尾指针 | setHead | 重置头指针 | setTail | 重置尾指针 |
POINTER[属性] | 游标指针（当前位置） | setPointer | 设置当前指针 | – | – | – | – |
循环链表
JavaScript
1 2 3 4 5 6 7 8 9 10 | Array.prototype.next = function() { var cur = this[0]; this.push(this.shift()); return cur; } var arr = [1, 2, 3, 4, 5]; var count = 0; while(count++<20) { console.log(arr.next()); } |
JavaScript
1 2 3 4 5 6 | let circle = new Chain([1, 2, 3, 4, 5]); // 链表头咬尾 circle.TAIL.next = circle.HEAD; for(let i = 0; i < 20; ++i) { console.log(chain.next()); } |
