【原】数据驱动型的设计02

Mixlab交叉学科 2020-11-07

展开全文

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

第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 这是最简单的链表结构：