数据驱动型的设计02 / 四六文摘

本系列从数据结构相关的计算机知识出发，从数据的角度提出一些数据驱动的设计思维模式。

第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

-------------------------------

数据驱动型的设计02

相关推荐