JavaScript数据结构与算法Item4--链表

ゝ一世哀愁。 2022-07-16 01:52 160阅读 0赞

要存储多个元素，数组（或列表）可能是最常用的数据结构,，每种语言都实现了数组。这种数据结构非常方便，提供了一个便利的\[\]语法来访问它的元素。然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素.

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

![JlW5LDW.png][]

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。

现实中也有一些链表的例子。一列火车是由一系列车厢（也称车皮）组成的。每节车厢或车皮都相互连接。你很容易分离一节车皮，改变它的位置，添加或移除它。

![bJllBeQ.png][]

## 1 创建一个链表 ##

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

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

### **向链表尾部追加元素** ###

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

this.append = function(element){ 
        var node = new Node(element), //{1}
        current; //{2}
        if (head === null){ //列表中第一个节点 //{3}
            head = node;
        } else {
            current = head; //{4}
            //循环列表，直到找到最后一项
            while(current.next){
                current = current.next;
            }
            //找到最后一项，将其next赋为node，建立链接
            current.next = node; //{5}
        }
        length++; //更新列表的长度 //{6}
    };

### **从链表中移除元素** ###

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

this.removeAt = function(position){ 
        //检查越界值
        if (position > -1 && position < length){ // {1}
            var current = head, // {2}
            previous, // {3}
            index = 0; // {4}
            //移除第一项
            if (position === 0){ // {5}
                head = current.next;
            } else {
                while (index++ < position){ // {6}
                    previous = current; // {7}
                    current = current.next; // {8}
                }
                //将previous与current的下一项链接起来：跳过current，从而移除它
                previous.next = current.next; // {9}
            }
            length--; // {10}
            return current.element;
        } else {
            return null; // {11}
        }
    };

### **在任意位置插入一个元素** ###

接下来，我们要实现insert方法。使用这个方法可以在任意位置插入一个元素。我们来看一看它的实现：

this.insert = function(position, element){ 
        //检查越界值
        if (position >= 0 && position <= length){ //{1}
            var node = new Node(element),
            current = head,
            previous,
            index = 0;
            if (position === 0){ //在第一个位置添加
                node.next = current; //{2}
                head = node;
            } else {
                while (index++ < position){ //{3}
                    previous = current;
                    current = current.next;
                }
                node.next = current; //{4}
                previous.next = node; //{5}
            }
            length++; //更新列表的长度
            return true;
        } else {
            return false; //{6}
        }
    };

### **toString方法** ###

toString方法会把LinkedList对象转换成一个字符串。下面是toString方法的实现：

this.toString = function(){
        var current = head, //{1}
        string = ''; //{2}
        while (current) { //{3}
            string = current.element; //{4}
            current = current.next; //{5}
        }
        return string; //{6}
    };

### **indexOf方法** ###

indexOf是我们下一个要实现的方法。indexOf方法接收一个元素的值，如果在列表中找到它，就返回元素的位置，否则返回-1。来看看它的实现：

this.indexOf = function(element){ 
        var current = head, //{1}
        index = -1;
        while (current) { //{2}
            if (element === current.element) {
            return index; //{3}
            }
            index++; //{4}
            current = current.next; //{5}
        }
        return -1;
    };

实现了这个方法，我们就可以实现remove等其他的方法：

this.remove = function(element){ 
        var index = this.indexOf(element);
        return this.removeAt(index);
    };

### **isEmpty、size和getHead方法** ###

isEmpty和size方法跟我们在上一章实现的一模一样。但我们还是来看一下：

this.isEmpty = function() { 
        return length === 0;
    };

如果列表中没有元素，isEmpty方法就返回true，否则返回false。

this.size = function() { 
        return length;
    };

size方法返回列表的length。和我们之前几章实现的类有所不同，列表的length是内部控  
制的，因为LinkedList是从头构建的。最后还有getHead方法：

this.getHead = function(){ 
        return head;
    };

总的结构代码：

## 2 双向链表 ##

链表有多种不同的类型，这一节介绍双向链表。双向链表和普通链表的区别在于，在链表中，  
一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，  
另一个链向前一个元素，如下图所示：

![Pwwfs3T.png][]

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

function DoublyLinkedList() { 
        var Node = function(element){ 
            this.element = element;
            this.next = null;
            this.prev = null; //新增的
    
        };
        var length = 0;
        var head = null;
        var tail = null; //新增的
        //这里是方法
    }

### **在任意位置插入一个新元素** ###

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

this.insert = function(position, element){ 
           var current = this.head,
           index = 0,
           prev,
           node = new Node(element);
           if(position> -1 && position < this.length){
             if(position == 0){
               if(!this.head){
       //插入空的链表中的首位
                 this.head = node;
                 this.tail = node;
               }else{
                 this.head = node;
                 node.next = current;
                 current.prev = node;
               }
             }else if(position == this.length){
               current = tail;
               current.next = node;
               node.prev = current;
               this.tail = node;
             }else{
               while(index++ < position){
                 previous = current;
                 current = current.next;
               }
               previous.next = node;
               node.next = current;
               node.prev = previous;
               current.prev = node;
             }
             this.length ++;
             return true;
           }else{
             return false;
           }
         }

### **从任意位置移除元素** ###

我们需要处理三种场景：从头部、从中间和从尾部移除一个元素。  
![e1GVogB.png][]

this.removeAt = function(position){ 
           var current = this.head,
           index = 0,
               prev;
           if(position > -1 && position < this.length){ //检查越界值
             if (position == 0){  //删除第一项，将head指向第一个元素即可；
               this.head = current.next;
               if(this.length == 1){
                 this.tail = null;
               }else{
                 this.head.prev = null;
               }
             }else if(position == this.length -1){
               current = this.tail;
               this.tail = current.prev;
               this.tail.next = null;
    
             }
             else{
               while(index++ < position){ //将previous与current的下一项链接起来：跳过current，从而移除它,此处找到前一项；
                 previous = current;
                 current = current.next;
               }
               previous.next = current.next; //此处跳过current；
               current.next.prev = previous; 
    
             }
             this.length --;
             return current.element;
           }else{
             return null;
           }
         }

## 3 循环链表 ##

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

![WyodomJ.png][]  
双向循环链表有指向head元素的tail.next，和指向tail元素的head.prev。  
![AhA8THL.png][]

双向链表总程序

[JlW5LDW.png]: http://i.imgur.com/JlW5LDW.png
[bJllBeQ.png]: http://i.imgur.com/bJllBeQ.png
[Pwwfs3T.png]: http://i.imgur.com/Pwwfs3T.png
[gLGi5Up.png]: http://i.imgur.com/gLGi5Up.png
[e1GVogB.png]: http://i.imgur.com/e1GVogB.png
[WyodomJ.png]: http://i.imgur.com/WyodomJ.png
[AhA8THL.png]: http://i.imgur.com/AhA8THL.png