JavaScript数据结构与算法（7）链表

怼烎@ 2022-01-29 03:27 203阅读 0赞

参考文章:[https://www.cnblogs.com/xiaohuochai/p/8175716.html\#anchor4][https_www.cnblogs.com_xiaohuochai_p_8175716.html_anchor4]

**1.链表**

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展示了一个链表的结构：

![在这里插入图片描述][20190521094410552.png]

**2.创建链表**

理解了链表是什么之后，现在就要开始实现我们的数据结构了。以下是我们的LinkedList 类的骨架：

LinkedList数据结构还需要一个Node辅助类（行\{1\}）。**Node类表示要加入列表的项。它包含一个element属性，即要添加到列表的值，以及一个next属性，即指向列表中下一个节点项的指针。**

LinkedList类也有存储列表项的数量的length属性（内部/私有变量）（行\{2\}）。**另一个重要的点是，我们还需要存储第一个节点的引用。为此，可以把这个引用存储在一个称为head的变量中（行\{3\}）。**

LinkedList类的方法：  
append(element)：向列表尾部添加一个新的项。  
insert(position, element)：向列表的特定位置插入一个新的项。  
remove(element)：从列表中移除一项。  
indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。  
removeAt(position)：从列表的特定位置移除一项。  
isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。  
size()：返回链表包含的元素个数。与数组的length属性类似。  
toString() ：由 于列表项使 用了 Node 类 ，就 需要重写 继承自 JavaScript对 象默认 的  
toString方法，让其只输出元素的值。

1.append方法

向LinkedList对象尾部添加一个元素时，可能有两种场景：列表为空，添加的是第一个元素，或者列表不为空，向其追加元素

先来实现第一个场景：向为空的列表添加一个元素。当我们创建一个LinkedList对象时，head会指向null：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]

第二个场景是向一个不为空的列表尾部添加元素

要向列表的尾部添加一个元素，首先需要找到最后一个元素。记住，我们只有第一个元素的引用（行\{4\}），因此需要循环访问列表，直到找到最后一项。为此，我们需要一个指向列表中current项的变量（行\{2\}）。循环访问列表时，当current.next元素为null时，我们就知道已经到达列表尾部了。然后要做的就是让当前（也就是最后一个）元素的next指针指向想要添加到列表的节点（行\{5\}）。下图展示了这个行为：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]

2.remove方法

现在，让我们看看如何从LinkedList对象中移除元素。移除元素也有两种场景：第一种是移除第一个元素，第二种是移除第一个以外的任一元素。我们要实现两种remove方法：第一种是从特定位置移除一个元素，第二种是根据元素的值移除元素（稍后会展示第二种remove方法）

//现在，让我们看看如何从LinkedList对象中移除元素。移除元素也有两种场景：第一种是移除第一个元素，第二种是移除第一个以外的任一元素。
    this.removeAt = function(position){
    
    	//验证位置是有效的
    	if(position>-1 && position<length){
    
    		//我们将用current变量创建一个对列表中第一个元素的引用
    		//head是第一个节点的引用（说明哪一个是头）。current是代表当前节点（遍历或者移动时当时的那个节点current）
    		var current = head;
    		var previous;
    		//需要依靠一个细节来迭代列表，直到到达目标位置
    		var index = 0;
    
    		//移除第一项，因此，如果想移除第一个元素，要做的就是让head指向列表的第二个元素。
    		//我们将用current变量创建一个对列表中第一个元素的引用
    		//如果把 head 赋为current.next，就会移除第一个元素。
    		if(position === 0){
    			head = current.next;
    		}else{
    			while(index++ < position){
    				 previous = current;
    				 //找到删除元素位置的position，此时
    				 current=current.next;
    
    			}
    			将previous与current的下一项链接起来：跳过current，从而移除它
    			previous.next = current.next;
    		}
    		length--;
    		return current.element;
    	}else{
    		return null
    	}
    
    }

3.insert方法

//接下来，我们要实现insert方法。使用这个方法可以在任意位置插入一个元素。
    this.insert = function(position,element){
    
    	//检查越界值
    	if(position>=0  && position<=length){
    
    		var node = new Node(element);
    		var current = head;
    		var previous;
    		var index;
    
    		if(position === 0){
    			node.next = current;
    			head = node;
    		}else{
    			while(index++ < position){
    				previous = current;
    				current = current.next;
    			}
    			node.next = current;
    			previous.next = node;
    		}
    
    		length++;
    
    		return true;
    
    	}else{
    		return false;
    	}
    
    }

**3.双向链表**

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素， 另一个链向前一个元素，如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]

先从实现DoublyLinkedList类所需的变动开始：

function DoubleLinkedList(){
    
    	let Node = function(element){
    		this.element = element;
    		this.next = null;
    		this.prev;
    	}
    
    	let length = 0;
    	let head = null;
    	let tail = null;
    }

双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点.

1.insert

向双向链表中插入一个新项跟（单向）链表非常类似。区别在于，链表只要控制一个next指针，而双向链表则要同时控制next和prev（previous，前一个）这两个指针

这是向任意位置插入一个新元素的算法

2.removeAt

从双向链表中移除元素跟链表非常类似。唯一的区别就是还需要设置前一个位置的指针。下面来看一下它的实现：

this.removeAt = function(position){
     //检查越界值
     if (position > -1 && position < length){
      let current = head,
          previous,
          index = 0;
      //移除第一项
      if (position === 0){
        head = current.next; // {1}
        //如果只有一项，更新tail //新增的
        if (length === 1){ // {2}
         tail = null;
        } else {
         head.prev = null; // {3}
        }
      } else if (position === length-1){ //最后一项 //新增的
        current = tail; // {4}
        tail = current.prev;
        tail.next = null;
      } else {
        while (index++ < position){ // {5}
          previous = current;
          current = current.next;
        }
        //将previous与current的下一项链接起来——跳过current
        previous.next = current.next; // {6}
        current.next.prev = previous; //新增的
      }
      length--;
      return current.element;
     } else {
      return null;
     }
    };

**4.循环链表**

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用null，而是指向第一个元素（head），如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]

双向循环链表有指向head元素的tail.next，和指向tail元素的head.prev

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 4]

[https_www.cnblogs.com_xiaohuochai_p_8175716.html_anchor4]: https://www.cnblogs.com/xiaohuochai/p/8175716.html#anchor4
[20190521094410552.png]: /images/20220129/5c33a7a9788047599f42c3b76dbd7670.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220129/295b0407eefd4efcb08deee7b09b382e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220129/3f1b66abba04434ba661b49a47f9f2d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]: /images/20220129/e94bff47ff3147fda5d7fc56ee9fcb7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]: /images/20220129/2fbbe1cdd414458684a3c6cdbc7421ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 4]: /images/20220129/e9a5b2bc060d40b1b3547d8675d14248.png