双向链表[js实现] 【6】

用户4793865

发布于 2023-01-12 13:17:31

2690

发布于 2023-01-12 13:17:31

文章被收录于专栏：前端小菜鸡yym前端小菜鸡yym

removeAt(position)

用途： 移除指定位置的元素

越界判断

首先，对于position做一下负数和大于链表长度的越界判断。

 TwoWayLinkList.prototype.removeAt = function (position) {
          // 越界判断
          if (position < 0 || position >= this.length) {
            return false;
          }
   }

对于移除节点而言我们要考虑一下几种情况

只有一个节点
不止有一个节点
- 删除第一个节点
- 删除最后一个节点
- 删除中间的任意节点

只有一个节点

此时只需要将head和tail都指向null，就是移除节点了。

 // 判断是否只有一个节点
          if (this.length == 1) {
            this.head = null;
            this.tail = null;
          } else {
              // 不止一个节点
          }
复制代码

不止有一个节点

删除第一个节点

需要将head指向第二个节点，第二个节点的prev指向null。第一节点由于没有被引用就会被垃圾回收自动回收了。

 // 判断是否只有一个节点
          if (this.length == 1) {
            this.head = null;
            this.tail = null;
          } else {
            // 删除第一个节点
            if (position == 0) {
              //此时head指向第一个节点，所以 this.head.next就是第二个节点
              this.head.next.prev = null;
              this.head = this.head.next;
            } 
          }

删除最后一个节点

此时tail指向着最后一个节点，通过tail.prev找到tail的前一个节点，然后让其next变为空。最后吧tail指向这个"前一个节点"。

 if (this.length == 1) {
            this.head = null;
            this.tail = null;
          } else {
            if (position == 0) {
              this.head.next.prev = null;
              this.head = this.head.next;
            } else if (position == this.length - 1) {
              //判断是否是最后一个节点
              this.tail.prev.next = null;
              this.tail = this.tail.prev;
            } 
      }

删除中间任意节点

此时就需要current变量和index来寻找目标元素了。index小于position就进行++处理，同时current.next指向current，一直向下寻找。

current节点的上一个节点，的next需要指向current的下一个节点。current节点的下一个节点的prev需要指向current节点的上一个节点。

  // 判断是否只有一个节点
          if (this.length == 1) {
            this.head = null;
            this.tail = null;
          } else {
            if (position == 0) {
              this.head.next.prev = null;
              this.head = this.head.next;
            } else if (position == this.length - 1) {
              //判断是否是最后一个节点
              this.tail.prev.next = null;
              this.tail = this.tail.prev;
            } else {
              var current = this.head;
              var index = 0;
              while (index++ < position) {
                current = current.next;
              }
              current.prev.next = current.next;
              current.next.prev = current.prev;
              // current的这个节点因为没有被引用最后会被销毁
            }
          }

最后处理

不要忘记长度-1

 this.length -= 1;

我们还想要返回删除的数据。所以我们做下更改，把var current = this.head;提前。因为这个current记录的就是我们删除的节点。
对于最后一个节点的情况，我们还需要将tail指向current。完整代码

  TwoWayLinkList.prototype.removeAt = function (position) {
          // 越界判断
          if (position < 0 || position >= this.length) {
            return false;
          }
          var current = this.head;
          // 判断是否只有一个节点
          if (this.length == 1) {
            this.head = null;
            this.tail = null;
          } else {
            if (position == 0) {
              this.head.next.prev = null;
              this.head = this.head.next;
            } else if (position == this.length - 1) {
              current = this.tail;
              //判断是否是最后一个节点
              this.tail.prev.next = null;
              this.tail = this.tail.prev;
            } else {
              var index = 0;

              while (index++ < position) {
                current = current.next;
              }
              current.prev.next = current.next;
              current.next.prev = current.prev;
              // current的这个节点因为没有被引用最后会被销毁
            }
          }
          this.length -= 1;
          return current.data;
        };

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-06-27，如有侵权请联系 cloudcommunity@tencent.com 删除

null