前面讲解了数组, 栈和队列. 其实大家回想一下. 它们有很多相似的地方. 甚至栈和队列这两种数据结构在 js 中的实现方式也都是基于数组. 无论增删的方式, 遵循的原则如何, 它们都是有序集合的列表. 在 js 中, 我们新建一个数组并不需要限定他的大小也就是长度, 但是实际上, 数组的底层仍旧为初始化的数组设置了一个长度限制. 我们想要在数组中任意的插入和删除元素的成本很高, 虽然在 js 中我们有便捷的方法可以操作数组, 但是其底层原理仍旧是这样的. 只是我们对它并没有感觉, 比如在 java 中, 声明一个数组是必须要限制它的长度的. 并且在扩容的情况下, 操作起来也不是十分方便. 这就需要用到其它的数据结构来应对我们不同的需要, 比如链表.
链表 https://baike.baidu.com/item/链表/9794473 存储有序的元素的集合, 但是和数组不同的是, 链表中的元素在内存中的存储并不是连续的. 每一个链表元素都包含了一个存储元素本身的节点和一个指向下一个元素的引用. 看起来就像这样:
相对于传统的数组, 链表的一个好处就是增删的时候无需移动其它元素, 只要更改指针的指向就可以了. 但是缺点就是如果想要访问链表中的元素, 需要从头开始循环迭代到你想要的元素.
那么简单介绍了什么是链表之后, 我们看看如何用 js 来实现链表, 同样的链表有其自身的几种方法.
1,append(element), 向列表尾部添加一个新的元素, 注意这里所指的列表并不是我们想象中的有序列表, 链表是无序的.
2,insert(position,element), 在链表的指定位置插入一个新的元素.
3,remove(element), 从列表中移除一项.
4,indexOf(element), 返回该元素在列表中的索引, 如果列表中没有该元素就返回 - 1.
5,removeAt(position), 从列表的指定位置移除元素.
6,isEmpty(), 判断该链表是否为空
7,size(), 返回该链表包含的元素个数.
8,toString(), 返回链表元素的字符串值.
以上描述了链表包含的各种方法, 其实说到底也就是增删改查, 任何的数据结构的方法种类也就几乎如此. 下面我们来看下具体的实现.
- function LinkedList(){
- let Node = function (element) {
- this.element = element;
- this.next = null;
- }
- let length = 0;
- let head = null;
- this.append = function (element) {};
- this.insert = function (position,element){};
- this.removeAt = function (position) {};
- this.remove = function (element) {};
- this.indexOf = function (element) {};
- this.isEmpty = function () {};
- this.size = function () {};
- this.getHead = function () {};
- this.toString = function () {};
- this.print = function () {};
- }
这是整个 LinkedList 类的基本架子, 其中 Node 类就是我们链表中的每一个节点元素, 每一个节点元素都包含一个自身的值 (element) 和指向下一个节点的指针(next),length 自然就是我们记录链表长度的变量, 而 head 是指向第一个元素的指针, 初始值跟 next 是一样的, 都是 null.
既然架子搭完了, 我们接下来看看如何实现每一个具体的方法. 链表的方法要比栈或队列的实现稍微复杂些, 希望大家仔细阅读.
代码着实有点长, 注释是重点, 如果你认真读下来, 链表的基本构成和原理想必你也就理解了.
- // 下面的所有的注释所解释的语句都是注释下面的语句. 以下所有的 "节点元素" 都代表 node
- function LinkedList(){
- //node 才是链表中的单独元素, 但是这个元素中又包含自身的值和指向下一个 node 的指针
- let Node = function (element) {
- //node 的自身元素
- this.element = element;
- /*
- 这个 next 要特别注意, 它在理论上是指向链表下一个节点元素的指针, 但是在 js 的实现中, 其实这个指针不过是一个对象的索引, 而这个索引所包含的就是下一个 node
- 就像是这样{element:1,next:{element,next:{element:3,next...}}}, 这种对象的一层层嵌套, 这样也可以解释了为什么在中间插入链表元素时,
- 需要一层一层的迭代到需要插入的位置.
- */
- /*
- 换句话说, 这里的 next 指针, 指向的是下一个 node 节点元素的整体, 不单单只是 node 中的 element 元素.
- */
- this.next = null;
- }
- let length = 0;// 链表长度初始化
- let head = null;// 在链表中, 我们需要存储第一个节点元素的引用, 也就是 head, 在没有节点元素的时候初始化为 null.
- //append 方法类似于 js 数组的 push, 向链表的尾部添加节点元素.
- // 在 append 方法中有两种情况, 一种是没有节点元素, 链表的长度是 0, 另一种是已经存在了至少一个节点元素, 应对这两种不同的情况会有不同的操作.
- this.append = function (element) {
- // 声明变量, append 添加的 element 应该是 node, 所以通过 Node 类进行包装
- let node = new Node(element);
- // 这里就存在了一个问题, 那么就是我们在给链表添加节点元素的时候只有 head 的引用, 也就是我们只知道 head 是什么, 但是其他的我们一概不知.
- // 所以这里声明一个 current 变量, 用来存储我们当前的节点是什么.
- let current;
- // 这里, 如果 head 是 null, 说明该链表是没有节点元素的, 因为有节点元素的话 head 不可能为 null(head 会指向第一个节点元素), 那么既然如此, 我们的 head=node 就可以了.
- // 还有, 这里的 "=", 实在是让人很迷茫, 既然是指针, 为什么要 "赋值"?
- // 因为无论是 head,node.next(链表节点元素的指针)还是 current 还是下面会声明的 previous. 都是存储当前位置信息的一个存储器.
- // 也就是说, 这些变量所代表的是一个值信息的存储, 他们存储的值代表他们所指向的节点元素.
- // 嗯,,,, 希望我说明白了....
- console.log(head);// 你可以看到 head 以及链表在 js 中展现大概是什么样的.
- if(head === null) {
- head = node;
- } else {
- // 这里, 如果 head!=null, 说明该链表至少有一个节点元素, 那么当前的 current 自然就是 head, 因为我们要从 head 开始迭代到结尾.
- current = head;
- // 这里容易让人疑惑的地方是 current.next 是啥?
- // 上面 current 已经是 head 了, 那么无论是只有一个节点元素还是多个节点元素, 最后一个节点元素的 next 必为 null, 别问我为啥了.
- // 所以这里只要 current.next 不为 null(也就是有实际意义的值), 那么就循环到 current.next 是 null 为止.
- // 因为只有这样才说明当前的 current 是链表中的最后一个节点元素
- while(current.next) {
- current = current.next;
- }
- // 既然我们找到了链表中的最后一个节点元素, 那么把该节点元素的 next=node 就好了.
- // 那么这里还要说的是, 每一个新 node 的 next 必然是 null, 嗯, 就是这么定义的, 没有为啥.
- // 所以在我们将 current.next 指向 node 的时候, 链表最后一个节点元素的指向自然就是 null 了.
- current.next = node;
- }
- // 嗯... 别忘了增加一个单位长度
- length++;
- };
- // 在链表的任意 "合法" 位置插入节点元素, position 代表要插入的位置, element 不多说, 代表要插入的元素.
- this.insert = function (position,element){
- // 这个判断比较有趣, 如果 position 小于 0 并且大于该链表的长度, 说明这个 position 不合法. 直接返回 false
- // 如果在大于等于 0 并且小于等于 length,OK, 插入位置合法, 继续...
- if(position>= 0 && position <= length) {
- // 同样的, 要建个 node
- let node = new Node(element),
- // 同样的, 当前的 current 是 head
- current = head,
- // 新增了一个 previous, 这个 previous 是为了衔接需要插入的节点元素的.
- previous,
- // 这个 index 不是 length, 它是为了记录限定循环的计数器, 作用类似于 current 和 previous.
- index = 0;
- // 这里, 如果 position 是 0, 意味着我要在同步插入元素.
- if(position === 0) {
- // 那么自然, 新建的节点元素的指针 (next) 就指向了当前元素. 而 head 自然就是新建的节点元素 (node) 了.
- node.next = current;
- head = node;
- } else {
- // 那么如果想要在除了第一个元素的其他位置插入元素.
- // 在没有到达想要插入的位置的时候, 我们需要迭代替换 previous 和 current, 使其依次的往后移动.
- while (index++ <position) {
- // 这里就是每一次的移动, 前一个等于当前, 当前的又变成了下一个(就这样依次移动到指定的 position 位置)
- previous = current;
- current = current.next;
- }
- // 那么在到达了这个位置后, 我们需要把新建的 node 节点元素插入近 previous 和 current.
- // 也就是改变 node 节点元素和 previous 的指针. 使 node 节点元素指向当前的 current. 而 previous 的指针指向 node.
- // 这样也就完成了节点元素在指定位置的插入
- node.next = current;
- previous.next = node;
- }
- // 插入成功, 长度增加一个单位并返回 true
- length ++ ;
- return true;
- } else {
- return false;
- }
- };
- // 这个方式是移除制定位置的节点元素.
- this.removeAt = function (position) {
- // 同样的合法值范围限制.
- if(position> -1 && position < length) {
- // 同样的变量声明.
- let current = head,previous,index = 0;
- // 这里比较有趣, 如果是要移除第一个节点元素, 那么直接把 head 的指针指向当前节点元素 (current) 的下一个 (.next) 就可以了.
- // 因为我们中断了 head 和 current 的链接, 直接使 current 不存在于链表中了, 这样我们无论如何迭代都获取不到此时的 current.
- // 这样操作之后, 我们只要等待 js 垃圾回收器回收它就好了.
- if(position === 0) {
- head = current.next;
- } else {
- // 同样的迭代移动
- while (index++ < position) {
- previous = current;
- current = current.next;
- }
- // 这里我们迭代到了我们想要移除的元素的位置, 同样中断了 current 的在链表中的链接. 也就删除了该节点元素
- previous.next = current.next;
- }
- // 长度减少一个单位.
- length --;
- // 返回删除的元素值
- return current.element;
- } else {
- return null;
- }
- };
- // 获取该元素在链表中的位置
- this.indexOf = function (element) {
- let current = head,index = -1;// 不解释了, 这里 index 为 - 1
- // 那么这里又比较有趣了, 这里的 current 无非两种情况, null 或者一个具体的值.
- // 如果是 null, 说明该链表是空的, 不然 current=head 不可能为 null
- // 如果不为 null, 继续判断
- while(current) {
- // 那么如果 current 不为 null, 并且如果 element 和 current 的 element 相等. 说明找到了, 直接返回 index
- if(element === current.element) {
- return index;
- }
- // 这里其实可以是为上面 if 判断的 else 分支, 如果不相等, 那么计数器 index 就加一个单位, 并且 current 指针往后移动.
- index ++;
- current = current.next;
- }
- return -1;
- };
- // 我们既然有了 indexOf 和 removeAt, 这个 remove 方法我就不多说了.
- this.remove = function (element) {
- let index = this.indexOf(element);
- console.log(index)
- return this.removeAt(index);
- };
- // 下面的方法也都很简单, 无需多说
- this.isEmpty = function () {
- return length === 0;
- };
- this.size = function () {
- return length;
- };
- this.getHead = function () {
- return head;
- };
- this.toString = function () {
- let current = head,string = '';
- while(current) {
- string += current.element + (current.next ? 'n' : '');
- current = current.next;
- }
- return string;
- };
- this.print = function () {
- console.log(this.toString());
- };
- }
- var list = new LinkedList();
- list.append(1);
- list.append(2);
- list.append(3);
- list.append(4);
- list.append(5);
- list.print();//1n2n3n4n5
- list.insert(2,99);
- list.print();//1n2n99n3n4n5
- list.removeAt(1);
- list.print();//2n3n4n5
这就是基本的链表实现方式了. 大家在实践的时候可以先去掉注释, 自己思索一遍敲一遍代码, 然后回过头来带着疑问看注释. 我相信会有不小的帮助.
那么这一篇尽量不写的那么长. 到这里就告一段落. 下一篇文章会详细的介绍一下双向链表以及其实现的方式.
最后, 由于本人水平有限, 能力与大神仍相差甚远, 若有错误或不明之处, 还望大家不吝赐教指正. 非常感谢!
来源: https://www.cnblogs.com/zaking/p/8870705.html