Sequential Search

[barretlee]

顺序查找（Sequential Search），需要通过链表构建一张深度为 N 的无序符号表。你可以简单地理解它为一个数组，只不过它的每个单元都是一个键值对，并且它的数据结构比数组更加松散，便于我们做插入/删除等操作。

无序符号表的实现，十分简单，可以看这里：

chapters/chapter-3-searching/3.1-elementary-symbol-tables/sequentialSearchST.js

function sequentialSearchST() {

  function Node(key, val, next) {
    this.key = key;
    this.val = val;
    this.next = next;
  }

  var first = null;

  return {
    links: null,
    insertWhere: function(node, where) {
      var n = new Node(node.key, node.val);
      var l = this.links;
      if(where) {
        while(l) {
          if (l.key == where.key || l.val == where.val) {
            var ll = l.next;
            l.next = n;
            n.next = ll;
            break;
          }
          l = l.next;
        }
      } else {
        n.next = l;
        this.links = n;
      }
      return null;
    },
    findWhere: function(where) {
      var l = this.links;
      var depth = 0;
      while(l) {
        if(l.key == where.key || l.val == where.val) {
          var output = { depth: depth };
          for(var key  in l) if(key !== 'next') output[key] = l[key];
          return output;
        }
        depth++;
        l = l.next;
      }
      return -1;
    }
  }
}

一个长度为 N 的无序链表，每次查询和删除操作，最多需要 N 次，也就是说，我们构建一个长度为 N 的不重复无序链表，最多需要 ~N² / 2 次比较。