数据驱动型的设计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
