0010 ￥ 自建链表方法之#removeAt

不二如是

                               
登录/注册后可看大图

---

在上一讲我们完成了append方法，这次来实现“删除”。

在开始前，先让我们来看看链表中是如何删除一个元素的，有两个场景：

1、移除链表中的第一个元素。
2、移除非第一个以外的任意一个元素。

移除元素首先要得到元素的位置，那么就需要验证这个位置是否为链表中的有效位置。

所谓的有效位置，就是从位置0开始到最后一项（size-1）都是有效值，否则返回null（没有从链表中移除元素）。

1. //检查是否为有效位置（越界）
   
2.             if (position > -1 && position < length){
   
3.                 } else {
   
4.                 }
   

复制代码

先来模拟第一种场景，要从链表中移除第一个元素（position == 0）：

要移除第一个元素，要做的就是让head指向链表中原来的第二个元素。

我们此时用current变量创建一个对链表中第一个元素的引用，然后把head指向current.next，就会移除链表中的第一个元素。

现在，进入情景二，移除非第一个元素。

为此，需要依靠一个变量来迭代链表，直到目标位置。

此时我们使用一个用于内部控制和递增的index变量。

current变量总是为对所有循环链表的当前元素的引用，还需要一个对当前元素的前一个元素的引用的变量，命名为previous。

因此要从链表中移除当前元素，要做的就是将previous.next和current.next连接起来。

这样当前元素就会被丢弃在计算机内存中，等着被垃圾回收机制清除。

还是画一张图，首先考虑移除最后一个元素：

对于最后一个元素，current变量将是对链表中最后一个元素的引用（要移除的元素）。

current.next将是null（最后一个元素），previous.next指向了current。

那么要移除current，要做的就是把previous.next的值改变为current.next。

对于链表中的中间项，也可以应用上述逻辑：

current变量是对移除元素的引用，previous变量是对要移除元素的前一个元素的引用。

那么要移除current元素，需要做的就是将previous.next与current.next连接起来。

上述过程的代码实现：

1.   从链表中特定位置移除一项
   
2.         this.removeAt = function (position) {
   
3.             //检查是否为有效位置（越界）
   
4.             if (position > -1 && position < length) {
   
5. //                初始化变量
   
6.                 let current = head,
   
7.                     previous,
   
8.                     index = 0;
   
9. //                移除第一个元素
   
10.                 if (position === 0) {
    
11.                     head = current.next;
    
12.                 } else {
    
13. //                移除非第一个
    
14.                     while (index++ < position) {
    
15.                         previous = current;
    
16.                         current = current.next;
    
17.                     }
    
18. //                将previous与current的下一项连接起来，跳过current，从而移除它
    
19.                     previous.next = current.next;
    
20.                 }
    
21. //                更新链表长度
    
22.                 length--;
    
23.                 return current.element;
    
24.             } else {
    
25.                 return null;
    
26.             }
    
27.         };

复制代码

---

如果有收获，别忘了评分 ：

                               
登录/注册后可看大图

这位鱼油，如果喜欢本系列学习笔记，请订阅 专辑&#9758;（传送门）（不喜欢更要订阅 ）

                               
登录/注册后可看大图

一切都成往事丶

想学。