前端學數據結構之鏈表

来源:https://www.cnblogs.com/xiaohuochai/archive/2018/01/02/8175716.html
-Advertisement-
Play Games

[1]數據結構 [2]創建鏈表 [3]雙向鏈表 [4]迴圈鏈表 ...


前面的話

　　本文將介紹如何實現和使用鏈表這種動態的數據結構

 

數據結構

　　要存儲多個元素，數組（或列表）可能是最常用的數據結構。每種語言都實現了數組。這種數據結構非常方便，提供了一個便利的[]語法來訪問它的元素。然而，這種數據結構有一個缺點：（在大多數語言中）數組的大小是固定的，從數組的起點或中間插入或移除項的成本很高，因為需要移動元素

　　鏈表存儲有序的元素集合，但不同於數組，鏈表中的元素在記憶體中並不是連續放置的。每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用（也稱指針或鏈接）組成。下圖展示了一個鏈表的結構：

linkedList1

　　相對於傳統的數組，鏈表的一個好處在於，添加或移除元素的時候不需要移動其他元素。然而，鏈表需要使用指針，因此實現鏈表時需要額外註意。數組的另一個細節是可以直接訪問任何位置的任何元素，而要想訪問鏈表中間的一個元素，需要從起點（表頭）開始迭代列表直到找到所需的元素

　　現實中也有一些鏈表的例子。第一個例子就是康加舞隊。每個人是一個元素，手就是鏈向下一個人的指針。可以向隊列中增加人——只需要找到想加入的點，斷開連接，插入一個人，再重新連接起來

　　另一個例子是尋寶游戲。你有一條線索，這條線索是指向尋找下一條線索的地點的指針。你順著這條鏈接去下一個地點，得到另一條指向再下一處的線索。得到列表中間的線索的唯一辦法，就是從起點（第一條線索）順著列表尋找

　　還有一個可能是用來說明鏈表的最流行的例子，那就是火車。一列火車是由一系列車廂（也稱車皮）組成的。每節車廂或車皮都相互連接。你很容易分離一節車皮，改變它的位置，添加或移除它。下圖演示了一列火車。每節車皮都是列表的元素，車皮間的連接就是指針：

linkedList2

 

創建鏈表

　　理解了鏈表是什麼之後，現在就要開始實現我們的數據結構了。以下是我們的LinkedList 類的骨架：

function LinkedList() {
  var Node = function(element){ // {1} 
    this.element = element; 
    this.next = null;
  };
  var length = 0; // {2} 
  var head = null; // {3}
  this.append = function(element){}; 
  this.insert = function(position, element){}; 
  this.removeAt = function(position){}; 
  this.remove = function(element){}; 
  this.indexOf = function(element){}; 
  this.isEmpty = function() {};
  this.size = function() {}; 
  this.toString = function(){}; 
  this.print = function(){};
}

　　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方法，讓其只輸出元素的值。

【append】

　　向LinkedList對象尾部添加一個元素時，可能有兩種場景：列表為空，添加的是第一個元素，或者列表不為空，向其追加元素

　　下麵是我們實現的append方法：

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}
};

　　首先需要做的是把element作為值傳入，創建Node項（行{1}）

　　先來實現第一個場景：向為空的列表添加一個元素。當我們創建一個LinkedList對象時，head會指向null：

linkedList3

　　如果head元素為null（列表為空——行{3}），就意味著在向列表添加第一個元素。因此要做的就是讓head元素指向node元素。下一個node元素將會自動成為null

　　第二個場景是向一個不為空的列表尾部添加元素

　　要向列表的尾部添加一個元素，首先需要找到最後一個元素。記住，我們只有第一個元素的引用（行{4}），因此需要迴圈訪問列表，直到找到最後一項。為此，我們需要一個指向列表中current項的變數（行{2}）。迴圈訪問列表時，當current.next元素為null時，我們就知道已經到達列表尾部了。然後要做的就是讓當前（也就是最後一個）元素的next指針指向想要添加到列表的節點（行{5}）。下圖展示了這個行為：

linkedList4

　　當一個Node元素被創建時，它的next指針總是null。這沒問題，因為我們知道它會是列表的最後一項。當然，別忘了遞增列表的長度，這樣就能控制它，輕鬆地得到列表的長度（行{6}）。 我們可以通過以下代碼來使用和測試目前創建的數據結構

var list = new LinkedList(); 
list.append(15); 
list.append(10);

【remove】

　　現在，讓我們看看如何從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}
  }
};

　　該方法要得到需要移除的元素的位置，就需要驗證這個位置是有效的（行{1}）。從0（包括0）到列表的長度（size – 1，因為索引是從零開始的）都是有效的位置。如果不是有效的位置，就返回null（意即沒有從列表中移除元素）

　　下麵來為第一種場景編寫代碼：我們要從列表中移除第一個元素（position === 0——行{5}）。下圖展示了這個過程：

linkedList5

　　因此，如果想移除第一個元素，要做的就是讓head指向列表的第二個元素。我們將用current變數創建一個對列表中第一個元素的引用（行{2}）。這樣 current 變數就是對列表中第一個元素的引用。如果把 head 賦為current.next，就會移除第一個元素。

　　現在，假設我們要移除列表的最後一項或者中間某一項。為此，需要依靠一個細節來迭代列表，直到到達目標位置（行{6}——我們會使用一個用於內部控制和遞增的index變數）：current 變數總是為對所迴圈列表的當前元素的引用（行{8}）。我們還需要一個對當前元素的前一個元 素的引用（行{7}）；它被命名為previous（行{3}）。

　　因此，要從列表中移除當前元素，要做的就是將previous.next和current.next鏈接起 來（行{9}）。這樣，當前元素就會被丟棄在電腦記憶體中，等著被垃圾回收器清除

　　下麵試著通過一些圖表來更好地理解。首先考慮移除最後一個元素：

linkedList6

　　對於最後一個元素，當我們在行{6}跳出迴圈時，current變數將是對列表中最後一個元素的引用（要移除的元素）。current.next的值將是null（因為它是最後一個元素）。由於還保留了對previous元素的引用（當前元素的前一個元素），previous.next就指向了current。那麼要移除current，要做的就是把previous.next的值改變為current.next

　　現在來看看，對於列表中間的元素是否可以應用相同的邏輯：

linkedList7

　　current變數是對要移除元素的引用。previous變數是對要移除元素的前一個元素的引用。 那麼要移除current元素，需要做的就是將previous.next與current.next鏈接起來。因此，我們的邏輯對這兩種情況都管用

【insert】

　　接下來，我們要實現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}
  }
};

　　由於處理的是位置，就需要檢查越界值（行{1}，跟remove方法類似）。如果越界了， 就返回false值，表示沒有添加項到列表中（行{6}）

　　現在要處理不同的場景。第一種場景，需要在列表的起點添加一個元素，也就是第一個位置。下圖展示了這種場景

linkedList8

　　current變數是對列表中第一個元素的引用。我們需要做的是把node.next的值設為current（列表中第一個元素）。現在head和node.next都指向了current。接下來要做的就是把head的引用改為node（行{2}），這樣列表中就有了一個新元素

　　現在來處理第二種場景：在列表中間或尾部添加一個元素。首先，我們需要迴圈訪問列表， 找到目標位置（行{3}）。當跳出迴圈時，current變數將是對想要插入新元素的位置之後一個元素的引用，而previous將是對想要插入新元素的位置之前一個元素的引用。在這種情況下，我們要在previous和current之間添加新項。因此，首先需要把新項（node）和當前項鏈接起來（行{4}），然後需要改變previous和current之間的鏈接。我們還需要讓previous.next指向node（行{5}）

　　我們通過一張圖表來看看代碼所做的事：

linkedList9

　　如果我們試圖向最後一個位置添加一個新元素，previous將是對列表最後一項的引用，而current將是null。在這種情況下，node.next將指向current，而previous.next將指向 node，這樣列表中就有了一個新的項

　　現在來看看如何向列表中間添加一個新元素

linkedList10

　　在這種情況下，我們試圖將新的項（node）插入到previous和current元素之間。首先， 我們需要把node.next的值指向current。然後把previous.next的值設為node。這樣列表中就有了一個新的項

【toString】

　　toString方法會把LinkedList對象轉換成一個字元串。下麵是toString方法的實現：

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

　　首先，要迴圈訪問列表中的所有元素，就需要有一個起點，也就是head。我們會把current 變數當作索引（行{1}），控制迴圈訪問列表。我們還需要初始化用於拼接元素值的變數（行{2}）。

　　接下來就是迴圈訪問列表中的每個元素（行{3}）。我們要用current來檢查元素是否存在（如果列表為空，或是到達列表中最後一個元素的下一位（null），while迴圈中的代碼就不會執行）。然後我們就得到了元素的內容，將其拼接到字元串中（行{4}）。最後，繼續迭代下一個元 素（行{5}）。最後，返回列表內容的字元串（行{6}）

【indexOf】

　　indexOf是我們下一個要實現的方法。indexOf方法接收一個元素的值，如果在列表中找到它，就返回元素的位置，否則返回-1。下麵來看看它的實現：

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

　　我們需要一個變數來幫助迴圈訪問列表，這個變數是current，它的初始值是head（列表的第一個元素——我們還需要一個index變數來計算位置數（行{1}））。然後迴圈訪問元素（行{2}），檢查當前元素是否是我們要找的。如果是，就返回它的位置（行{3}）；如果不是，就繼續計數（行{4}），檢查列表中下一個節點（行{5}）

　　如果列表為空，或是到達列表的尾部（current = current.next將是null），迴圈就不會執行。如果沒有找到值，就返回-1

【remove】

　　實現了indexOf方法，我們就可以實現remove等其他的方法：

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

　　我們已經有一個移除給定位置的一個元素的removeAt方法了。現在有了indexOf方法，如果傳入元素的值，就能找到它的位置，然後調用removeAt方法並傳入找到的位置。這樣非常簡單，如果需要更改removeAt方法的代碼，這樣也更容易——兩個方法都會被更改（這就是重用代碼的妙處）。這樣，我們就不需要維護兩個從列表中移除一項的方法，只需要一個！同時， removeAt方法將會檢查邊界約束

【isEmpty】

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

【size】

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

【getHead】

　　head變數是LinkedList類的私有變數（這意味著它不能在LinkedList實例外部被訪問和更改，只有通過LinkedList實例才可以）。但是，如果我們需要在類的實現外部迴圈訪問列表，就需要提供一種獲取類的第一個元素的方法

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

【完整代碼】

　　鏈表的完整代碼如下

function LinkedList() {

    let Node = function(element){

        this.element = element;
        this.next = null;
    };

    let length = 0;
    let head = null;

    this.append = function(element){

        let node = new Node(element),
            current;

        if (head === null){ //first node on list
            head = node;
        } else {

            current = head;

            //loop the list until find last item
            while(current.next){
                current = current.next;
            }

            //get last item and assign next to added item to make the link
            current.next = node;
        }

        length++; //update size of list
    };

    this.insert = function(position, element){

        //check for out-of-bounds values
        if (position >= 0 && position <= length){

            let node = new Node(element),
                current = head,
                previous,
                index = 0;

            if (position === 0){ //add on first position

                node.next = current;
                head = node;

            } else {
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }

            length++; //update size of list

            return true;

        } else {
            return false;
        }
    };

    this.removeAt = function(position){

        //check for out-of-bounds values
        if (position > -1 && position < length){

            let current = head,
                previous,
                index = 0;

            //removing first item
            if (position === 0){
                head = current.next;
            } else {

                while (index++ < position){

                    previous = current;
                    current = current.next;
                }

                //link previous with current's next - skip it to remove
                previous.next = current.next;
            }

            length--;

            return current.element;

        } else {
            return null;
        }
    };

    this.remove = function(element){

        let index = this.indexOf(element);
        return this.removeAt(index);
    };

    this.indexOf = function(element){

        let current = head,
            index = 0;

        while (current) {
            if (element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }

        return -1;
    };

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

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

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

    this.toString = function(){

        let current = head,
            string = '';

        while (current) {
            string += current.element + (current.next ? ', ' : '');
            current = current.next;
        }
        return string;

    };

    this.print = function(){
        console.log(this.toString());
    };
}

【ES6】

　　ES6版本的代碼如下

let LinkedList2 = (function () {

    class Node {
        constructor(element){
            this.element = element;
            this.next = null;
        }
    }

    const length = new WeakMap();
    const head = new WeakMap();

    class LinkedList2 {

        constructor () {
            length.set(this, 0);
            head.set(this, null);
        }

        append(element) {

            let node = new Node(element),
                current;

            if (this.getHead() === null) { //first node on list
                head.set(this, node);
            } else {

                current = this.getHead();

                //loop the list until find last item
                while (current.next) {
                    current = current.next;
                }

                //get last item and assign next to added item to make the link
                current.next = node;
            }

            //update size of list
            let l = this.size();
            l++;
            length.set(this, l);
        }

        insert(position, element) {

            //check for out-of-bounds values
            if (position >= 0 && position <= this.size()) {

                let node = new Node(element),
                    current = this.getHead(),
                    previous,
                    index = 0;

                if (position === 0) { //add on first position

                    node.next = current;
                    head.set(this, node);

                } else {
                    while (index++ < position) {
                        previous = current;
                        current = current.next;
                    }
                    node.next = current;
                    previous.next = node;
                }

                //update size of list
                let l = this.size();
                l++;
                length.set(this, l);

                return true;

            } else {
                return false;
            }
        }

        removeAt(position) {

            //check for out-of-bounds values
            if (position > -1 && position < this.size()) {

                let current = this.getHead(),
                    previous,
                    index = 0;

                //removing first item
                if (position === 0) {
                    head.set(this, current.next);
                } else {

                    while (index++ < position) {

                        previous = current;
                        current = current.next;
                    }

                    //link previous with current's next - skip it to remove
                    previous.next = current.next;
                }

                let l = this.size();
                l--;
                length.set(this, l);

                return current.element;

            } else {
                return null;
            }
        }

        remove(element) {

            let index = this.indexOf(element);
            return this.removeAt(index);
        }

        indexOf(element) {

            let current = this.getHead(),
                index = 0;

            while (current) {
                if (element === current.element) {
                    return index;
                }
                index++;
                current = current.next;
            }

            return -1;
        }

        isEmpty() {
            return this.size() === 0;
        }

        size() {
            return length.get(this);
        }

        getHead() {
            return head.get(this);
        }

        toString() {

            let current = this.getHead(),
                string = '';

            while (current) {
                string += current.element + (current.next ? ', ' : '');
                current = current.next;
            }
            return string;

        }

        print() {
            console.log(this.toString());
        }
    }

    return LinkedList2;
})();

 

雙向鏈表

　　鏈表有多種不同的類型，下麵將介紹雙向鏈表。雙向鏈表和普通鏈表的區別在於，在鏈表中，一個節點只有鏈向下一個節點的鏈接，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素， 另一個鏈向前一個元素，如下圖所示：

linkedList11

　　先從實現DoublyLinkedList類所需的變動開始：

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

　　在代碼中可以看到，LinkedList類和DoublyLinkedList類之間的區別標為新增的。在Node類里有prev屬性（一個新指針），在DoublyLinkedList類里也有用來保存對列表最後一項的引用的tail屬性

　　雙向鏈表提供了兩種迭代列表的方法：從頭到尾，或者反過來。我們也可以訪問一個特定節點的下一個或前一個元素。在單向鏈表中，如果迭代列表時錯過了要找的元素，就需要回到列表起點，重新開始迭代。這是雙向鏈表的一個優點

【insert】

　　向雙向鏈表中插入一個新項跟（單向）鏈表非常類似。區別在於，鏈表只要控制一個next指針，而雙向鏈表則要同時控制next和prev（previous，前一個）這兩個指針

　　這是向任意位置插入一個新元素的演算法

this.insert = function(position, element){
 //檢查越界值
 if (position >= 0 && position <= length){
  let node = new Node(element),
      current = head,
      previous,
      index = 0;
  if (position === 0){ //在第一個位置添加
    if (!head){ //新增的 {1}
      head = node;
      tail = node;
    } else {
      node.next = current;
      current.prev = node; //新增的 {2}
      head = node;
    }
  } else if (position === length) { //最後一項 //新增的
    current = tail; // {3}
    current.next = node;
    node.prev = current;
    tail = node;
  } else {
    while (index++ < position){ //{4}
      previous = current;
      current = current.next;
    }
    node.next = current; //{5}
    previous.next = node;
    current.prev = node; //新增的
    node.prev = previous; //新增的
  }
  length++; //更新列表的長度
  return true;
 } else {
  return false;
 }
};

　　我們來分析第一種場景：在列表的第一個位置（列表的起點）插入一個新元素。如果列表為空（行{1}），只需要把head和tail都指向這個新節點。如果不為空，current變數將是對列表中第一個元素的引用。就像我們在鏈表中所做的，把node.next設為current，而head將指向node（它將成為列表中的第一個元素）。不同之處在於，我們還需要為指向上一個元素的指針設一個值。current.prev指針將由指向null變為指向新元素（node——行{2}）。node.prev指針已經是null，因此不需要再更新任何東西

　　下圖演示了這個過程：

linkedList12

　　現在來分析一下，假如我們要在列表最後添加一個新元素。這是一個特殊情況，因為我們還控制著指向最後一個元素的指針（tail）。current變數將引用最後一個元素（行{3}）。然後開始建立第一個鏈接：node.prev將引用current。current.next指針（指向null）將指向node（由於構造函數，node.next已經指向了null）。然後只剩一件事了，就是更新tail，它將由指向current變為指向node。下圖展示了這些行為

linkedList13

　　然後還有第三種場景：在列表中間插入一個新元素。就像我們在之前的方法中所做的迭代列表，直到到達要找的位置（行{4}）。我們將在current和previous元素之間插入新元素。首先，node.next將指向current（行{5}），而previous.next將指向node，這樣就不會丟失節點之間的鏈接。然後需要處理所有的鏈接：current.prev將指向node，而node.prev將指向 previous。下圖展示了這一過程：

linkedList14

【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;
 }
};

　　我們需要處理三種場景：從頭部、從中間和從尾部移除一個元素。 下麵來看看如何移除第一個元素。current變數是對列表中第一個元素的引用，也就是我們想移除的元素。需要做的就是改變 head 的引用，將其從current 改為下一個元素（current.next——行{1}）。但我們還需要更新current.next指向上一個元素的指針（因為第一個元素的prev指針是null）。因此，把head.prev的引用改為null（行{3}——因為head也指向列表中新的第一個元素，或者也可以用current.next.prev）。由於還需要控制tail的引用，我們可以檢查要移除的元素是否是第一個元素，如果是，只需要把tail也設為null

　　下圖勾畫了從雙向鏈表移除第一個元素的過程：

linkedList15

　　下一種場景是從最後一個位置移除元素。既然已經有了對最後一個元素的引用（tail），我們就不需要為找到它而迭代列表。這樣我們也就可以把tail的引用賦給current變數（行{4}）。接下來，需要把tail的引用更新為列表中倒數第二個元素（current.prev，或者tail.prev 也可以）。既然tail指向了倒數第二個元素，我們就只需要把next指針更新為null（tail.next=null）。下圖演示了這一行為：

linkedList16

　　第三種也是最後一種場景：從列表中間移除一個元素。首先需要迭代列表，直到到達要找的位置（行{5}）。current變數所引用的就是要移除的元素。那麼要移除它，我們可以通過更新previous.next和current.next.prev的引用，在列表中跳過它。因此，previous.next將指向current.next，而current.next.prev將指向previous，如下圖所示：

linkedList17

【完整代碼】

　　雙向鏈表的完整代碼如下所示

function DoublyLinkedList() {

    let Node = function(element){

        this.element = element;
        this.next = null;
        this.prev = null; //NEW
    };

    let length = 0;
    let head = null;
    let tail = null; //NEW

    this.append = function(element){

        let node = new Node(element),
            current;

        if (head === null){ //first node on list
            head = node;
            tail = node; //NEW
        } else {

            //attach to the tail node //NEW
            tail.next = node;
            node.prev = tail;
            tail = node;
        }

        length++; //update size of list
    };

    this.insert = function(position, element){

        //check for out-of-bounds values
        if (position >= 0 && position <= length){

            let node = new Node(element),
                current = head,
                previous,
                index = 0;

            if (position === 0){ //add on first position

                if (!head){       //NEW
                    head = node;
                    tail = node;
                } else {
                    node.next = current;
                    current.prev = node; //NEW {1}
                    head =
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • vue 回到頂部的小問題
    今天在用vue項目中，實現回到頂部功能的時候，我寫了一個backTop組件，接下來需要通過監聽window.scroll事件來控制這個組件顯示隱藏 因為可能會有其他的組件會用到這樣的邏輯，所以將此功能做成一個自定義指令： 根據滾動的距離控制一個數據為true還是為false（v scroll sho ...
  • 全屏網格摺疊動畫插件
    前言 Duang，Duang，Duang，博主又來分享插件了，這次是一個炫酷的網格摺疊動畫效果，其原理模擬紙板摺疊過程的動畫，頁面使用了大量CSS3屬性，具體效果請看演示頁面（建議使用新版谷歌、火狐瀏覽器觀看，對於ie9以下不支持CSS3屬性的瀏覽器不相容）。 博主個人建議：這個效果可以用於網站引導 ...
  • 基於HTML5陀螺儀實現ofo首頁眼睛移動效果
    最近用ofo小黃車App的時候，發現以前下方掃一掃變成了一個眼睛動的小黃人，覺得蠻有意思的，這裡用HTML5仿一下效果。 ofo眼睛效果 效果分析 從效果中不難看出，是使用陀螺儀事件實現的。 這裡先來看一下HTML5中陀螺儀事件的一些概念。 陀螺儀事件為deviceorientation，這裡主要獲 ...
  • 實現div毛玻璃背景
    毛玻璃效果 ios里毛玻璃效果的使用非常多，本文介紹一個實現div毛玻璃背景的方法 CSS3 Filter CSS3的Filter主要用在圖像的特效處理上，預設值為none，還有以下備選項：   1.grayscale灰度   2.sepia褐色   ...
  • Web前端開發學習誤區，你掉進去了沒？
    從接觸網站開發以來到現在，已經有五個年頭了吧，今天偶然整理電腦資料看到當時為參加系裡面一個比賽而做的第一個網站時，勾起了在這網站開發道路上的一串串回憶，成功與喜悅、煩惱與糾結都歷歷在目，感慨頗多。 先從大家學習上的一個誤區開始談起。 Web前端的學習誤區 網頁製作是電腦專業同學在大學期間都會接觸到 ...
  • HTML常用的標簽中，行內元素和塊級元素
    塊元素(block element) HTML標簽分類明細 * address - 地址 * blockquote - 塊引用 * center - 舉中對齊塊 * dir - 目錄列表 * div - 常用塊級容易，也是css layout的主要標簽 * dl - 定義列表 * fieldset ...
  • Web前端開發的四個階段（小白必看）
    第一階段：HTML的學習 超文本標記語言（HyperText Mark-up Language 簡稱HTML）是一個網頁的骨架，無論是靜態網頁還是動態網頁，最終返回到瀏覽器端的都是HTML代碼，瀏覽器將HTML代碼解釋渲染後呈現給用戶。因此，我們必須掌握HTML的基本結構和常用標記及屬性。 HTML ...
  • 從零開始學習前端開發 — 4、容器溢出
    一、容器溢出 語法：overflow:visible|hidden|scroll|auto|inherit; visible:預設值，溢出內容不會被裁剪，正常顯示 hidden: 溢出內容隱藏不可見 scroll: 當容器溢出時，溢出的內容以滾動條的形式查看（當容器沒有溢出時，也會顯示一個預設的滾動 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類