almost 2 years ago

前篇文章中,我們說明三種資料結構、陣列、堆疊、佇列,在開始今天的文章前,我們先簡單的複習一下這三個東西是啥。

  • 陣列(array) : 最常用使用到的資料結構,它是一種相同形態(!)的資料集合,並且會分配『連續』的記憶體空間給予陣列存放資料。
  • 堆疊(stack) : 後進先出法原理的資料結構,後進去的資料會先取出,就像是你有個箱子,你最先放進去的東西,要先將上面的東西取出後,才能取得。
  • 佇列(queue) : 先進先出法原理的資料結構,先進去的東西先取出,就像是排隊一樣,先排先贏,理論上(和平)。

剛剛在陣列那有說到相同形態,但事實上javascript的陣列,可以存放任何形態的資料,但其它的語言就需要先宣告形態了,某此方面來說它的陣列比較算是list

複習完了上一篇文章後,咱們可以來學習新的資料結構連結串列(linked list)

  • 串列(Linked list)原理
  • 串列與陣列的比較
  • javascript程式實作

串列 (Linked List) 原理

在上一篇中,我們有學習到陣列,它在儲放資料時非常的彈性,但在進行新增或刪除時卻沒著麼方便,主要原因為它的記憶體是連續的。

本篇文章將要說明的連結串列(list),在新增或刪除時就非常的方便,因為它記憶體不是連續的,而是每個結點分配一段記憶體,然後在結點中記錄下個結點的位置。

連結串列有分很多種,我們在這篇文章中將說明比較常用到的『單向連結串列』與『雙向連結串列』。

單向連結串列

單向連結串列,它主要組成的定義如下。

  • 由一組節點(Node)組成的有序串列。
  • 每個節點有『資料欄』與一個『連結欄』組成。
  • 『連結欄』指向其它節點的位置。

根據以上的定義,大至上長的如下圖。

接下來假如我們要新增節點D至A與B之間,過程會和下圖一樣,會將A節點的Link連至D節點,然後它再連到B結點上。而刪除結果過程也差不多,就只是重新指向節點位置。

雙向連結串列 (Double Linked List)

雙向連結串列是另一種常用的串列結構,在單向串列中,它只能順著一個方向尋找資料,而且中間不小心有個節點斷掉,那後面串列的資料就會消失且救不回來,而雙向連結就是可以改善『單向』與『節點斷掉』這兩個缺點。

雙向連結串列,它主要組成的定義如下。

  • 由一組節點(Node)組成的有序串列。
  • 每個節點有『資料欄』與二個『連結欄』組成,一個連結前一個節點,而另一個則連結後一個節點。
  • 『連結欄』指向其它節點的位置。

根據以上的定義,大至上長的如下圖。

然後我們看下圖,來理解如果要插入與刪除節點時,雙向連結串列會如何處理。事際上原理和單向連結串列差不多,都是重新指向位置,只是它要多指向一個。

串列和陣列的比較

由於串列和陣列這兩個使用起來很相似,但原理上,很多地方是不一樣的。以下比較表格來源為此,傳送門

連結串列 (List) 陣列 (Array)
記憶體 不需要連續的空間 需要連續的空間
節點型態 node形態不相同 node形態相同
操作複雜度 插入、刪除都為O(1) 插入刪除都為O(n)
空間配置 不需預留空間 須事先宣告連續空間
資料分割、連結 容易 不容易
存取方式 只能循序存取 可支援隨機與循序存又
存取速度 速度慢 速度快
可靠性
額外指標空間 需要額外的指標空間 不需要

Javascript程式碼實作

我們將實作Single Linked ListDouble Linked List

單向連結串列(Single Linked List)實作

我們這邊主要實作三個方法。

  • add : 可以新增資料至list中。
  • remove : 可以從list內,移除指定位置的節點。
  • view : 可以輸出現在list的內容。

首先我們要先建立list的結構,我們需要兩個物件,一個代表節點,另一個則代表list
Node中我們主要有兩個屬性data為該節點的資料,next為存放它的下個節點。

而在SingleList中,也有兩個屬性head,用來存放第一個節點,其它的節點則存放在它的next中,而另一個_length為代表list的節點數。

/**
 * Node
 * Node class 
 * @param data
 * @returns {undefined}
 */
function Node(data) {
  this.data = data;
  this.next = null;
}

/**
 * SingleList
 * SingleList class 
 * @returns {undefined}
 */
function SingleList() {
    this.head = null;
    this._length = 0;
}

然後我們接下來建立方法add,它可以新增節點至list中。

 * add
 * add data to last .
 * @param data
 * @returns {undefined}
 */
SingleList.prototype.add = function(data){
    var node = new Node(data);
    var currentNode = this.head;    

    if(!currentNode){
        this.head = node;   
        this._length++;
        return node;
    }

    while (currentNode.next){
        currentNode = currentNode.next; 
    }

    currentNode.next = node;
    this._length++;
    return node;    
}

上面的程式碼中,有一段程式碼如下,這段是什麼意思呢 ? 它是指將currentNode,移動至最後一個節點,再將最後一個節點的next,存放我們要新增的節點。這樣我們新增節點的方法就算完成了。

while (currentNode.next){
    currentNode = currentNode.next; 
}

currentNode.next = node;

接下來我們再來完成remove

/**
 * remove
 * it method can remove data from list , depend on postition.
 * @param position
 * @returns {undefined}
 */
SingleList.prototype.remove = function(position){
    var  message = {failure: 'Failure: non-existent node in this list.'};
    var currentNode = this.head,
            deleteNode,
            previous,
            i=1;

    if(position < 1 || position > this._length){
        throw new Error()
    }

    if(position === 1){
        this.head = currentNode.next;   
        deleteNode = currentNode; 
        this._length--;
        return deleteNode;
    }

    while (i++ < position){
        previous = currentNode; 
        currentNode = currentNode.next;
    }
    previous.next = currentNode.next;
    
    return currentNode;
}

這邊我們說明一下remove中的這段程式碼,因為這段比較容易讓人混亂。假設我們list有三筆資料A、B、C,然後我們要刪除B,這時我們來跑while看看。

  • 第一次 : i=2 (是指console.log時的), previous = A , currentNode = B 。
  • 第二次 : 由於 i=2 沒有符合小於position 2 ,所以跳出 while 。

跳出後,我們再將previous也就是A節點,並將它下一個節點設為B的下一個節點也就是C,所以這時B節點就消失囉。

while (i++ < position){
    console.log(i)
    previous = currentNode; 
    currentNode = currentNode.next;
}
previous.next = currentNode.next;

最後我們來做個可以觀看list資料的方法,view,這個方法就比較簡單了。

/**
 * view
 * It can console log list 
 * @returns {undefined}
 */
SingleList.prototype.view = function(){
    var currentNode = this.head;
    while (currentNode != null){
        console.log(currentNode.data);
        currentNode =  currentNode.next;    
    }
}

最後我們來試用看看。

var singleList = new SingleList();
singleList.add("A");
singleList.add("B");
singleList.add("C");

singleList.view();

singleList.remove(2);
singleList.view();

輸出的結果如下。

// 原來的
A B C

// 刪除後

A C

雙向連結串列 (Double Linked List)實作

我們這邊與上面一樣,主要實作三個方法。

  • add : 可以新增資料至list中。
  • remove : 可以從list內,移除指定位置的節點。
  • view : 可以輸出現在list的內容。

首先我們要先建立list的主題,我們需要二個物件,一個代表節點,另一個則代表list
Node中我們主要有三個屬性data為該節點的資料,next為存放它的下個節點而previous為存放前一個節點。

而在DoubleLinkList中,有三個屬性head,用來存放第一個節點,final用來存放list中最後的節點,最後的屬性_length為代表list的節點數,

/**
 * Node
 * Node class
 * @param data
 */
function Node(data) {
  this.data = data;
  this.next = null;
  this.previous = null;
}

/**
 * DoubleLinkList
 * List class
 */
function DoubleLinkList() {
  this.head = null;
  this.final = null;
  this._length = 0;
}

然後我們一樣也先來建立add方法,該方法可以讓我們新增資料到list中。

/**
 * add
 * add data to list
 * @param data
 * @returns {Node}
 */
DoubleLinkList.prototype.add = function(data) {
  var node = new Node(data);
  if (this._length == 0) {
    this.head = node;
    this.final = node;
  } else {
    this.final.next = node;
    node.previous = this.final;
    this.final = node;
  }
  this._length++;
  return node;
}

其中下面這段程式碼,在單向連結時,我們需要先用while來移動到最後的節點,但因為我們雙向連結這邊,多加了一個屬性,final用來記錄最後的節點,因此我們在新增時,只要修改這最後的節點就好囉,不用在使用while進行移動。

這是雙向連結串列的程式碼部份。

   this.final.next = node;
   node.previous = this.final;
   this.final = node;

這是單向連結串列的程式碼部份。

while (i++ < position){
    previous = currentNode; 
    currentNode = currentNode.next;
}
    previous.next = currentNode.next;

完成後,我們再繼續完成remove方法,這個方法真的變比較複雜點兒,我們來慢慢說明。

/**
 * remove
 * remove data by position from list
 * @param position
 */
DoubleLinkList.prototype.remove = function(position) {
  var currentNode = this.head;
  var message = {
      failure: 'Failure: non-existent node in this list.'
    },
    i = 1;
  if (this._length === 0 || this.position < 1 || this.position > this._length) {
    throw new Error(message.failure);
  }

  // 1.刪除的節點為第一個的流程
  if (position === 1) {
    this.head = currentNode.next;

    // 如果不是只有一個節點的list則
    if (this.head) {
      this.head.previous = null;
    } else {
      this.final = null;
    }
        
    // 2.刪除的節點為最後一個的流程
  } else if (position === this._length) {
    this.final = this.final.previous;
    this.final.next = null;
    return;
    
    // 3.其餘的刪除的節點流程
  } else {

    while (i < position) {
      currentNode = currentNode.next;
            i++;
    }
        var previousNode = currentNode.previous;
        var nextNode = currentNode.next;
        previousNode.next = nextNode; 
        nextNode.previous = previousNode;
  }
    this._length--;

}

首先我們要先知道,在上面的remove程式碼中,大至上可以分成三個部份,來處理不同位置的刪除。

1.刪除的節點為第一個的流程 : 這個流程中,我們還需要判斷『這個list是否只有一個節點』,然後在分開來處理。

  // 1.刪除的節點為第一個的流程
  if (position === 1) {
    this.head = currentNode.next;

    // 如果不是只有一個節點的list則
    if (this.head) {
      this.head.previous = null;
    } else {
      this.final = null;
    }
        
    // 2.刪除的節點為最後一個的流程
  }

2.刪除的節點為最後一個的流程 : 這個流程只要將要刪除的節點,它的前一個節點的next設置為null,並修改final為它。

// 2.刪除的節點為最後一個的流程
  } else if (position === this._length) {
    this.final = this.final.previous;
    this.final.next = null;
    return;
    
    // 3.其餘的刪除的節點流程
  }
  1. 其餘的刪除的節點流程 : 這個流程就是先移動到要刪除的節點上,然後再將它的前一個與後一個的節點,連結在一起,這樣它就消失囉。
// 3.其餘的刪除的節點流程
  } else {

    while (i < position) {
      currentNode = currentNode.next;
            i++;
    }
        var previousNode = currentNode.previous;
        var nextNode = currentNode.next;
        previousNode.next = nextNode; 
        nextNode.previous = previousNode;
  }

最後一個view方法,因為與單向連結列表一樣,所以就不多說囉。

/**
 * view
 * View List
 */
DoubleLinkList.prototype.view = function() {
  var currentNode = this.head;
  while (currentNode != null) {
    console.log(currentNode.data);
    currentNode = currentNode.next;
  }
}

然後我們一樣來測試一下。

var list = new DoubleLinkList();
list.add("A");
list.add("B");
list.add("C");

list.view();
list.remove(2);
list.view();

結果如下。

// 原來的
A B C

// 刪除後

A C

最後全部程式碼在此,傳送門

參考資料

← 基礎資料結構(1)---陣列(Array)、堆疊(Stack)、佇列(Queue) VIM的五四三---vim + syntastic + eslint + react的配置 →
 
comments powered by Disqus