欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript實(shí)現(xiàn)單鏈表過(guò)程解析

 更新時(shí)間：2022年01月24日 15:35:35   作者：bear*6  
這篇文章主要介紹了JavaScript實(shí)現(xiàn)單鏈表過(guò)程，鏈表中的元素在內(nèi)存中不必是連續(xù)的空間。鏈表的每個(gè)元素有一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和指向下一個(gè)元素的引用。下面請(qǐng)和小編一起進(jìn)入文章了解更多的詳細(xì)內(nèi)容吧

前言：

要存儲(chǔ)多個(gè)元素，數(shù)組是最常用的數(shù)據(jù)結(jié)構(gòu)，但是數(shù)組也有很多缺點(diǎn)：

  • 數(shù)組的創(chuàng)建通常要申請(qǐng)一段連續(xù)的內(nèi)存空間，并且大小是固定的，所以當(dāng)當(dāng)前數(shù)組不能滿足容量需求時(shí)，需要進(jìn)行擴(kuò)容，（一般是申請(qǐng)一個(gè)更大的數(shù)組，然后將原數(shù)組中的元素復(fù)制過(guò)去）
  • 在數(shù)組元素開(kāi)頭或者中間位置插入數(shù)據(jù)的成本很高，需要進(jìn)行大量元素的位移。

所以要存儲(chǔ)多個(gè)元素，另一個(gè)選擇就是鏈表，不同于數(shù)組的是，鏈表中的元素在內(nèi)存中不必是連續(xù)的空間。鏈表的每個(gè)元素有一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和指向下一個(gè)元素的引用。
相對(duì)于數(shù)組，鏈表有一些優(yōu)點(diǎn)：

  • 內(nèi)存空間不必是連續(xù)的，可以充分利用計(jì)算機(jī)的內(nèi)存，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。
  • 鏈表不必在創(chuàng)建時(shí)就確定大小，并且大小可以無(wú)限延伸下去。
  • 鏈表在插入和刪除數(shù)據(jù)的時(shí)候，事件復(fù)雜度可以達(dá)到O（1），相對(duì)數(shù)組效率高很多。

相對(duì)于數(shù)組，鏈表有一些缺點(diǎn)：

  • 鏈表訪問(wèn)任何一個(gè)位置的元素的時(shí)候，都需要從頭開(kāi)始訪問(wèn)，無(wú)法通過(guò)下標(biāo)直接訪問(wèn)元素。

一、什么是單鏈表

那么到底什么是單鏈表呢？

它就類似于火車，火車頭規(guī)連接一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)上有乘客，并且這個(gè)節(jié)點(diǎn)會(huì)連接到下一個(gè)節(jié)點(diǎn)，依次類推，如下所示：

我們的鏈表結(jié)構(gòu)就是：

了解了直觀上的鏈表，我們?cè)賮?lái)對(duì)單鏈表進(jìn)行代碼的封裝。

二、單鏈表的封裝

首先，我們封裝一個(gè)NodeList類，用于表示鏈表結(jié)構(gòu)，在這個(gè)類里面在封裝一個(gè)內(nèi)部類Node，用于封裝每一個(gè)節(jié)點(diǎn)上的信息（數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的引用），然后在NodeList類中保存兩個(gè)屬性，一個(gè)是鏈表的長(zhǎng)度，一個(gè)是鏈表中的頭結(jié)點(diǎn)。

如下所示：

 function LinkedList(){
            this.length = 0;
            this.head = null;
            //內(nèi)部的類
            function Node(data){
                this.data = data;
                this.next = null;
            }
        }

三、單鏈表的常用操作

然后在里面添加單鏈表常用的操作。主要有：

  • append（element) :向列表尾部添加一個(gè)項(xiàng)
  • insert(position,element) :向列表的特定位置插入一個(gè)項(xiàng)
  • get(position) :獲取對(duì)應(yīng)位置的元素
  • indexOf(element) :返回元素在列表中的索引，如果列表中沒(méi)有該元素則返回-1
  • update(position，ele) :修改某個(gè)位置的元素
  • removeAt(position) :從列表的指定位置移除一項(xiàng)
  • remove(element) :從列表中移除一項(xiàng)
  • isEmpty() :如果鏈表中不包含任何元素，返回true,如果鏈表長(zhǎng)度大于0返回false
  • size() :返回鏈表包含的元素個(gè)數(shù)，與數(shù)組的length屬性相關(guān)
  • toString() :由于列表項(xiàng)用到了Node類，需要重寫繼承自JavaScript對(duì)象默認(rèn)的toString方法，讓其輸出元素的值

接下來(lái)們就來(lái)一個(gè)一個(gè)實(shí)現(xiàn)。

1、append(element)方法-----向列表尾部添加一個(gè)項(xiàng)

因?yàn)橄蜴湵砦膊刻砑訑?shù)據(jù)可能有兩種情況：

  • 鏈表本身為空，新添加的數(shù)據(jù)是唯一的節(jié)點(diǎn)
  • 鏈表不為空，需要向其他節(jié)點(diǎn)后面追加節(jié)點(diǎn)

所以我們就需要進(jìn)行判斷，如果鏈表為空，直接將頭結(jié)點(diǎn)的指針指向新節(jié)點(diǎn)。
如果鏈表不為空，則新建立一個(gè)臨時(shí)節(jié)點(diǎn)，讓它等于頭結(jié)點(diǎn)，并對(duì)它進(jìn)行判斷，如果它指向的節(jié)點(diǎn)的指針域?yàn)榭?，則為尾節(jié)點(diǎn)，將新加的節(jié)點(diǎn)添加到末尾，即讓尾節(jié)點(diǎn)的指針指向新添加的節(jié)點(diǎn)。如果它指向的節(jié)點(diǎn)的指針域不為空，則讓這個(gè)臨時(shí)節(jié)點(diǎn)的指針域指向下一個(gè)節(jié)點(diǎn)，一直循環(huán)操作到這個(gè)節(jié)點(diǎn)的指針域?yàn)榭眨礊槲补?jié)點(diǎn)）。然后每添加一個(gè)節(jié)點(diǎn)，讓鏈表的長(zhǎng)度+1。

LinkedList.prototype.append = function(data){
                var newNode = new Node(data);
                // 判斷鏈表是否為空
                // 1.為空
                if(this.length === 0){
                    this.head = newNode;
                }else{
                    //不為空
                    var current = this.head;
                    if(current.next){
                        current = current.next;
                    }
                    current.next = newNode;
                }
                this.length += 1;
            }

2、toString方法-----輸出元素的值

這個(gè)比較簡(jiǎn)單，主要是獲取每一個(gè)元素，因?yàn)楂@取鏈表的任何元素都必須從第一個(gè)節(jié)點(diǎn)開(kāi)始，所以我們可以從頭結(jié)點(diǎn)開(kāi)始，循環(huán)遍歷每一個(gè)節(jié)點(diǎn)，并且取出其中的element，拼接成字符串，并將字符串返回。

LinkedList.prototype.toString = function(){
                var current = this.head;
                var ListStr = '';
                while(current){
                    ListStr += current.data + ' ';
                    current = current.next;
                }
                return ListStr;
            }

驗(yàn)證：創(chuàng)建幾個(gè)新的節(jié)點(diǎn)，并打印

 var list = new LinkedList();
        list.append('a');
        list.append('b');
        list.append('c');
        list.append('d');
        list.append('e');
        alert(list);

打印結(jié)果為：

3、insert方法-----向列表的特定位置插入一個(gè)項(xiàng)

實(shí)現(xiàn)在任意位置插入數(shù)據(jù)的方法，首先判斷插入的位置是否越界，然后在不越界的情況下分兩種情況，如果插入到第一個(gè)位置，則表示新添加的節(jié)點(diǎn)是頭，則需要將原來(lái)的頭結(jié)點(diǎn)作為新節(jié)點(diǎn)的next,再讓head指向新節(jié)點(diǎn)。如果插入到其他位置，則需要通過(guò)循環(huán)先找到節(jié)點(diǎn)位置，并在循環(huán)的過(guò)程中保存上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)，找到正確的位置后，將新節(jié)點(diǎn)的Next指向下一個(gè)節(jié)點(diǎn)，將上一個(gè)節(jié)點(diǎn)的next節(jié)點(diǎn)指向新節(jié)點(diǎn)。

代碼如下：

 LinkedList.prototype.insert = function(position,data){
                if(position<0 || position >this.length){
                   return false;
               }
                var newNode = new Node(data);
                var index = 0;
              if(position == 0){
                newNode.next = this.head;
                this.head = newNode;

              }else{
                    while(index++ < position){
                        var current = this.head;
                        var previous = null;
                        previous = current;
                        current = current.next;
                    }
                    newNode.next = current;
                    previous.next = newNode;
                }
                this.length += 1;
                return true;
                }

驗(yàn)證：在第1個(gè)位置插入xl,在第2個(gè)位置插入wh

list.insert(1,'xl')
       list.insert(2,'wh')
        alert(list)

4、get方法-----獲取對(duì)應(yīng)位置的元素

這個(gè)方法相對(duì)簡(jiǎn)單，先對(duì)positon做越界判斷，然后通過(guò)臨時(shí)節(jié)點(diǎn)遍歷鏈表直到目標(biāo)位置，獲取該位置的元素。

LinkedList.prototype.get = function(position,data){

                var current = this.head;
                var index = 0;
                if(position < 0 || position >= this.length){
                    return null;
                }else{
                    while(index<position){
                        current = current.next;
                        index++;
                    }
                    return current.data;
                }
            }

驗(yàn)證：獲取第三個(gè)位置的元素：

alert( list.get(3));

5、indexOf()方法-----返回元素在列表中的索引

首先判斷查找的元素的位置是否存在，如果不存在，返回-1。如果存在的話分兩種情況，如果返回的元素在第一個(gè)位置，則直接返回第一個(gè)位置的索引。如果返回元素在其他位置，則需要通過(guò)循環(huán)先找到節(jié)點(diǎn)位置，這個(gè)過(guò)程中，索引需要跟著遍歷的次數(shù)自加，找到正確元素的位置后，打印索引即為目標(biāo)位置。

LinkedList.prototype.indexOf = function(data){
                var index = 0;
                var current = this.head;
                while(current){
                    if(current.data == data){
                        return index;
                    }
                    else{
                        current = current.next;
                    index++;
                    }
                }
                return -1;
            }
        }

驗(yàn)證：獲取c的索引：

alert(list.indexOf('c'));

6、update方法-----修改某個(gè)位置的元素

這個(gè)方法和get方法很像，向后遍歷，當(dāng)index的值等于position時(shí)，表示找到目標(biāo)位置，將date改為目標(biāo)值：

LinkedList.prototype.update = function(position,ele){
                if(position<0 || position>=this.length){
                    return false;
                }else{
                    var index = 0;
                    var current = this.head;
                    while(index++ <position){
                        current = current.next;
                    }
                    current.data = ele;
                    return true;
                }
            }

驗(yàn)證：修該第0個(gè)位置的元素為：bear

 list.update(0,'bear')
      alert(list)

7、removeAt方法-----從列表的指定位置移除一項(xiàng)

首先判斷刪除項(xiàng)的位置是否越界，然后在不越界的情況下，給定兩個(gè)臨時(shí)節(jié)點(diǎn)previous和current，previous用來(lái)保存前一個(gè)current的值，從頭節(jié)點(diǎn)開(kāi)始遍歷，直到索引位置等于目標(biāo)位置，讓臨時(shí)節(jié)點(diǎn)current遍歷到目標(biāo)位置，讓臨時(shí)節(jié)點(diǎn)的前一個(gè)next指向下一個(gè)next。

LinkedList.prototype.removeAt = function(position,data){
                var current = this.head;
                var previous = null;
                var index = 0;
                if(position<0 || position>=this.length){
                    return false;
                }else{
                    while(index++ <position){
                        previous = currrent;
                        current = current.next;
                    }
                    previous.next = current.next;
                    this.length -= 1;
                    return true;
                }
            }
        }

驗(yàn)證：移除第三個(gè)位置的元素：

list.removeAt(3)
      alert(list)

8、remove方法-----從列表中移除一項(xiàng)

先判斷所要?jiǎng)h除的元素是否在鏈表中，如果不在，返回false，否則，構(gòu)建一個(gè)臨時(shí)節(jié)點(diǎn)，用于遍歷鏈表，如果臨時(shí)節(jié)點(diǎn)的data值和要?jiǎng)h除的元素相等，則停止遍歷，讓臨時(shí)節(jié)點(diǎn)的前一個(gè)next指向下一個(gè)next。這里可以在構(gòu)建一個(gè)臨時(shí)節(jié)點(diǎn)用于存儲(chǔ)前一個(gè)current的值。

LinkedList.prototype.remove = function(ele){
                var current = this.head;
                var previous = null;
                var index = 0;
                while(current.data !== ele){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = current.next;
            }

驗(yàn)證：刪除值為xl的元素：

 list.remove('xl')
      alert(list)

9、isEmpty方法-----判斷鏈表是否為空

根據(jù)length判斷，如果鏈表中不包含任何元素，返回true,如果鏈表長(zhǎng)度大于0返回false

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

驗(yàn)證：

 alert(list.isEmpty())

9、size方法-----返回鏈表包含的元素個(gè)數(shù)

直接返回元素的length就是其個(gè)數(shù)。

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

驗(yàn)證：

   alert(list.size())

到此這篇關(guān)于JavaScript實(shí)現(xiàn)單鏈表過(guò)程解析的文章就介紹到這了,更多相關(guān)JavaScript實(shí)現(xiàn)單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評(píng)論