js链表实现

一、节点的实现 我都知道链表就是用有向线段把多个节点按顺序串起来，要实现链表首先要实现节点，而每一个节点，有一个自己的 value 值，还有一个 next 值用于指向下一个节点。

比如可以这么实现一个节点： 

function Node(value) { 

 this.value = value; //当前节点的值 

 this.next = null; //下一个节点链接 

} 

以上代码用构造函数的方式声明一个 Node 类，Node 类有两个属性 value 和 next，value 指向自身的值，next 声明为 null。 

二、链表操作 链表的基本操作包括：增、删、改、查，因此一个列表对象应该具备这些基本功能. 

1、元素查找 需要插入一个新值到链表之前，我们需要找到这个值的位置，所以先来看看链表查找的 demo： class ListClass { constructor() { this.head = new Node("head"); //头节点 } //查找给定节点 find(item) { let currNode = this.head; while (currNode.value != item) { currNode = currNode.next; } return currNode; } } 该链表类有一个 head 属性，即，链表的头部，指向 node 对象，也就是 this.head = {value: 'head', next: null} ，在 find 函数中，声明 currNode 变量，指向头部，遍历链表，对比每个节点的值跟需要查找值，若相等，则找到了，返回当前节点。 

2、插入、替换元素 以上讲了插入元素之前，我们需要先查找元素，找到之后，把新的节点插入到找到的元素后面，也就是找到元素的 next 指向新的元素，再把新元素的 next 指向当前节点的 next class ListClass { constructor() { this.head = new Node("head"); //头节点 } //查找给定节点 find(item) { let currNode = this.head; while (currNode.element != item) { currNode = currNode.next; } return currNode; } //插入节点 insert(newElement, item) { let newNode = new Node(newElement); let currNode = this.find(item); newNode.next = currNode.next; currNode.next = newNode; } } 替换元素值，比以上简单点，找到对应的元节点，把该节点的 value 赋予新值，就到达到了修改的目的。 

3、删除元素 要删除一个元素，需要查找被删除元素的前一个节点，然后把前一个元素的 next 指向被删除元素的下一个节点，实现如下： class ListClass { constructor() { this.head = new Node("head"); //头节点 } //查找带删除节点的前一个节点 findPrev(item) { let currNode = this.head; while (!(currNode.next == null) && currNode.next.element != item) { currNode = currNode.next; } return currNode; } // 删除节点 remove(item) { let prevNode = this.findPrev(item); if (!(prevNode.next == null)) { prevNode.next = prevNode.next.next; } } } 

4、显示元素 操作完元素，我们想看看效果，这个时候需要显示链表，通过打印每一个元素我们可以看到链表的完整结构 class ListClass { constructor() { this.head = new Node("head"); //头节点 } //显示链表元素 display() { let currNode = this.head; while (!(currNode.next == null)) { console.log(currNode.next); currNode = currNode.next; } } } 以上就是我对 js 链表的完整实现，写这篇文章是因为今天跟同事聊天意识到自己对链表不是很熟，查阅资料，自己实现了一下，加深理解，再写篇文章以备以后忘了可以查阅。 本文首发于我的个人博客：https://canace.site/2019/11/29/js%E9%93%BE%E8%A1%A8%E5%AE%9E%E7%8E%B0/ ，转载请注明出处。

本文章由javascript技术分享原创和收集