Open wingmeng opened 5 years ago
/** * 链表构造器 */ class LinkedList { constructor(...list) { this._head = new Node('head'); // 头节点 if (list.length) { this.insert('head', list[0]); for (let i = 1; i < list.length; i++) { this.insert(list[i - 1], list[i]) } } } // 查找节点 // 从头节点开始遍历,直至找到目标节点 find(value) { let curNode = this._head; while (curNode && curNode.value !== value) { curNode = curNode.next } return curNode; } // 通过索引值查找对应元素 findIndex(index) { let curNode = this._head; let tempIdx = 0; while (curNode !== null) { if (tempIdx === index + 1) { return curNode } tempIdx += 1; curNode = curNode.next; } return null; } // 查找目标节点的上一个节点 findPrev(value) { let curNode = this._head; while (curNode.next !== null && curNode.next.value !== value) { curNode = curNode.next } return curNode; } // 在目标节点的后面插入新节点 insert(value, newValue) { const newNode = new Node(newValue); const curNode = this.find(value); if (curNode) { newNode.next = curNode.next; curNode.next = newNode; } else { console.error(`insert error:链表中不存在 \`${value}\` 节点`) } } // 在目标索引插入新节点 insertIndex(index, newValue) { const newNode = new Node(newValue); const curNode = this.findIndex(index); if (curNode) { newNode.next = curNode.next; curNode.next = newNode; } else { console.error(`insertIndex error:链表中不存在 \`${index}\` 索引节点`) } } // 在链表末尾添加节点 push(newValue) { const newNode = new Node(newValue); let curNode = this._head; while (curNode.next !== null) { curNode = curNode.next } curNode.next = newNode; } // 删除指定链表节点 remove(value) { const preNode = this.findPrev(value); const curNode = preNode.next; if (preNode && curNode) { preNode.next = preNode.next.next } } // 删除指定索引对应的节点 removeIndex(index) { const preNode = this.findIndex(index - 1); const curNode = this.findIndex(index); if (preNode && curNode) { preNode.next = curNode.next } } // 获取链表长度(不含头部节点) size() { let curNode = this._head; let tempSize = 0; while (curNode.next !== null) { tempSize += 1; curNode = curNode.next; } return tempSize; } } /** * 节点构造器 * value - 当前节点的值 * next - 指向下一节点的指针 */ class Node { constructor(value) { this.value = value; this.next = null; } }
上述代码参考自(有改动):https://github.com/lvwxx/blog/issues/1#Linked%20List
const linkedList = new LinkedList('节点1', '节点2'); console.group('初始化插入节点:"节点1", "节点2"'); console.log(linkedList); console.log('链表长度:', linkedList.size()); console.groupEnd(); console.group('在"节点2"后面插入"节点3"'); linkedList.insert('节点2', '节点3'); console.log(linkedList); console.log('链表长度:', linkedList.size()); console.groupEnd(); console.group('查找节点'); console.log('节点2', linkedList.find('节点2')); console.log('节点100', linkedList.find('节点100')); console.log('索引0', linkedList.findIndex(0)); console.log('索引100', linkedList.findIndex(100)); console.groupEnd(); console.group('在索引1后面插入"Node"'); linkedList.insertIndex(0, 'Node'); console.log(linkedList); console.log('链表长度:', linkedList.size()); console.groupEnd(); console.group('在链表末尾插入"节点n"'); linkedList.push('节点n'); console.log(linkedList); console.log('链表长度:', linkedList.size()); console.groupEnd(); console.group('删除"节点1"'); linkedList.remove('节点1'); console.log(linkedList); console.log('链表长度:', linkedList.size()); console.groupEnd(); console.group('删除索引2对应的节点'); linkedList.removeIndex(2); console.log(linkedList); console.log('链表长度:', linkedList.size()); console.groupEnd();