Python » 脚本编程 » [原创]javascript封装的链表类

xieaotian 发表于 2008-8-18 10:56

[原创]javascript封装的链表类

这是用javascript封装的一套双向链表的类，包括添加，删除，查找等基本功能
使用实例见panelwork windows(Javascript经典专区封装的模拟windows窗口管理程序)

以下为引用的内容：
/*--------------------------------------------------------------------
$ this is a part of Javascript Foundation Classes Framework that is  
$ used for javascript panel work programing. all is free, but reserved
$ by author.
$ date: 21:56 2007-11-27
$ author: Lovely Life
$ All rights reservered; [email]life.qm@gmail.com[/email]
-----------------------------------------------------------------------*/

// this only constructor for creating other class
var __CLASS = {
create: function() {
  return function() {
   this._initialize.apply(this, arguments);
  };
}
};
var __NODE = __CLASS.create(); // 列表节点结构
var __LIST = __CLASS.create(); // 链表

__NODE.prototype = {
_pre : null,
_next : null,
_key : null,
_initialize : function(key) {
  if( key != "" )
   this._key = key;
}
};

var __LIST__NODEHASEXIST = true;
var __LIST__NODENOTEXIST = false;


__LIST.prototype = {
_head : null,
_tail : null,

// 初始化链表
_initialize : function(Type){
  if(typeof Type == undefined)
   return;
  this._head = new Type(0);  // 链表的头部
  this._tail = new Type(null);  // 链表尾部
  this._head._next = this._tail;
  this._tail._pre = this._head;
},

// 链表第一个节点
_begin : function(){
  return this._head._next;
},

//链表最后一个节点
_end : function(){
  return this._tail;
},

//链表长度
_len : function(){
  return this._head._key;
},

// 追加节点
_append : function(node){
  if( this._find(node._key) != null ){
   return __LIST__NODEHASEXIST;
  }
  this._tail._pre._next = node;
  node._pre = this._tail._pre;
  node._next = this._tail;
  this._tail._pre = node;
  this._head._key++;
},

// 移除节点
_remove : function(node){
  if( this._find(node._key) == null ){
   return __LIST__NODENOTEXIST;
  }
  node._pre._next = node._next;
  node._next._pre = node._pre;
  this._head._key--;
  return node._key;
},

// 移除所有节点
_removeAll : function(){
  for(var node = this._begin(); node != this._end(); node = node._next){
   this._remove(node);
  }
},

// 查找指定关键字key的节点
_find : function(key){
  for(var node = this._begin(); node != this._end(); node = node._next){
   if( node._key == key )
    return node;
  }
  return null;
},

//将节点转化成字符串以便调试跟踪
_toString : function(){
  var i = 0;
  var str = "";
  for(var node = this._begin(); node != this._end(); node = node._next){
   str += "Node["+i+"]: " + node._key + "\n";
   i++;
  }
  return str;
}


在panelwork windows 中，通常都是用Array来保存管理窗口。 如果某个窗口被创建后又被删除，不一定是最后一个，这个时候会留下个存储单元，除非你对这些释放的单元进行管理，否则只有浪费。因为考虑到资源的重新利用，所以采用链表的方式存储这些数据。当删除某个节点的时候并不会造成资源的浪费，而且更精确的管理这些数据。可以看看数据结构这本书，现在到处都有的

查看完整版本: [原创]javascript封装的链表类