數據驅動型的設計02
- 2019 年 10 月 8 日
- 筆記
本系列從數據結構相關的計算機知識出發，從數據的角度提出一些數據驅動的設計思維模式。
第01期總體介紹數據結構與設計的關係，用數據結構的方式來思考設計，並通過幾個案例介紹一些大的思路。
第02期介紹數據結構中的鏈表結構，並探討設計中可能的鏈表數據。
1 何為鏈表？
1.1 概念
一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接實現的。圖示：
來個形象點的圖：
1.2 鏈表有特點呢？
查找某個元素：需要從鏈表中第一個元素開始，一直找到目標元素的位置。
插入／刪除某個元素：只要修改元素中的指針。
2 用代碼實現一個鏈表結構
採用Javascript來實現一個鏈表結構，加深對鏈表的理解，Chrome瀏覽器打開console面板，先實現一個鏈表的節點。
2.1 節點
此節點保存了數據本身（value的值）及下一個節點的位置（下一個節點），輸入：
class LinkedListNode { constructor(value,next) { this.value = value; this.next = next; } }
這裡我們需要了解下ES6的class特性，下文的例子定義了一個「類」——Point,可以看到裏面有一個constructor方法,這就是構造方法,主要寫一些Point對象的屬性，例如x和y的坐標值；而傳統的方法是通過構造函數,定義並生成新對象,然後通過 prototype 屬性向對象添加屬性和方法。
class Point { constructor(){ this.x=0; this.y=0; // ... } toString(){ // ... } toValue(){ // ... } }; // 等同於 function Point(){ this.x=0; this.y=0; //... }; Point.prototype = { toString(){}, toValue(){} };
2.2 鏈表的基本結構
主要是有兩個屬性，head記錄的是最開始的節點，tail記錄的是結尾的節點。其中由於每個節點都有一個next屬性指向下一個節點，所以head記錄了整條鏈表的節點。
class LinkedList{ constructor(){ this.head = null; this.tail = null; }}
初始化一個鏈表結構:
var ls=new LinkedList();
2.3 添加方法
下面為鏈表結構的數據添加：增刪改查的方法。
添加節點的方法：
append – 在結尾插入節點
prepend – 在開始插入節點
查詢節點的方法：
find
刪除節點的方法：
delete
2.3.1 prepend方法
添加prepend方法，圖示結合代碼：
LinkedList.prototype.prepend=function(value) { const newNode = new LinkedListNode(value,this.head); // 往head添加節點 this.head = newNode; // 如果tail為空，往tail添加此節點 if (!this.tail) { this.tail = newNode; } return this; }
實驗下prepend方法：
ls.prepend(0);console.log(JSON.stringify(ls,null,2));
打印出來：
{ "head": { "value": 0, "next": null }, "tail": { "value": 0, "next": null } }
繼續添加：
ls.prepend(1); console.log(JSON.stringify(ls,null,2));
結果：
"{ "head": { "value": 1, "next": { "value": 0, "next": null } }, "tail": { "value": 0, "next": null } }"
經過多次實驗，會發現，head是個一層層嵌套的結構，通過head可以找到任何一個節點（按順序），而tail永遠是存儲的最後一個節點。
2.3.2 append方法
為鏈表結構添加append方法：
LinkedList.prototype.append=function(value) { const newNode = new LinkedListNode(value); // 如果head為空，則head設為newNode if (!this.head) { this.head = newNode; this.tail = newNode; return this; } // 把新的newNode設為tail this.tail.next = newNode; this.tail = newNode; return this; }
實驗下append方法：
ls.append(10); console.log(JSON.stringify(ls,null,2));
2.3.3 compare方法
為了實現刪除delete，我們得先實現比對兩個數值是否相等的功能，相等的話返回0：
LinkedList.prototype.compare=function(a,b){ if (a === b) { return 0; } return a < b ? -1 : 1;};
2.3.4 delete方法
根據value值來刪除節點，凡是等於目標value的節點都被刪除：
LinkedList.prototype.delete=function(value) { let deletedNode = null; // head節點是否需要被刪除 while (this.head && this.compare(this.head.value, value)===0) { deletedNode = this.head; this.head = this.head.next; } let currentNode = this.head; if (currentNode !== null) { // 遍歷每一個節點 while (currentNode.next) { if (this.compare(currentNode.next.value, value)===0) { deletedNode = currentNode.next; currentNode.next = currentNode.next.next; } else { currentNode = currentNode.next; } } } // 判斷tail節點是否需要刪除 if (this.compare(this.tail.value, value)===0) { this.tail = currentNode; } return deletedNode; };
2.3.5 find方法
實現一個簡單的查找方法，找到一個值等於value的節點，並返回，代碼如下：
LinkedList.prototype.find=function(value) { let currentNode = this.head; while (currentNode) { if (value && this.compare(currentNode.value, value)===0) { return currentNode; } currentNode = currentNode.next; } return null; }
2.3.6 toArray方法
鏈表結構的數據轉化為數組數據：
LinkedList.prototype.toArray=function() { const nodes = []; let currentNode = this.head; while (currentNode) { nodes.push(currentNode); currentNode = currentNode.next; } return nodes; }
至此，我們對鏈表結構的數據應該已經理解得比較深刻了。接下來，我們探討下在設計中，有哪些是可以被鏈表結構的數據所表示的？
讚賞的方式可以是點廣告～
3 設計中的鏈表結構
思考下設計里，哪些元素／手法是可以被鏈表結構的數據表示的？我們先了解下鏈表結構的幾種基本類型。
3.1 鏈表結構的幾種基本類型
Singly linked list 這是最簡單的鏈表結構：
Double Linked List 雙向鏈表的結構：
Circular linked list循環鏈表的結構：
3.2 設計中的鏈表結構
鏈表本身的特點是一個節點連接着下一個節點，非常適合描述流程性，有前後關係的數據。
1）用戶體驗的流線
室內設計中，不同空間游線之間的關係；
展覽館的游線設計；
UX設計中頁面的跳轉流線；
2）設計思路的解構
景觀設計中，一層層的關係，地面鋪裝，樹池花台，喬木灌木，亭廊構架；
平面設計中，背景，主體內容，配色，布局，構圖等；
更多跟設計的結合，歡迎留言補充。
參考資料：
https://en.wikipedia.org/wiki/Linked_list
