JavaScript 链表

为什么需要链表

数组不总是组织数据的最佳数据结构,在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移,以反映数组刚刚进行了 添加或删除操作。然而,JavaScript 的数组并不存在上述问题,因为使用 split() 方法不需要再访问数组中的其他元素了。

JavaScript 中数组的主要问题是,它们被实现成了对象,与其他语言(比如 C++ 和 Java) 的数组相比,效率很低,如果你发现数组在实际使用时很慢,就可以考虑使用链表来替代它。除了对数据的随机访问,链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问,数组仍然是更好的选择。

插入元素

 

删除元素

 


一个基于对象的链表

function Node(element) {
   this.element = element;
   this.next = null;
}

function LList() {
   this.head = new Node("head");
   this.find = find;
   this.insert = insert;
   this.display = display;
   this.findPrevious = findPrevious;
   this.remove = remove;
}

function remove(item) {
   var prevNode = this.findPrevious(item);
   if (!(prevNode.next == null)) {
       prevNode.next = prevNode.next.next;
   }
}

function findPrevious(item) {
   var currNode = this.head;
   while (!(currNode.next == null) && 
           (currNode.next.element != item)) {
      currNode = currNode.next;
   }
   return currNode;
}

function display() {
   var currNode = this.head;
   while (!(currNode.next == null)) {
      console.log(currNode.next.element);
      currNode = currNode.next;
   }
}

function find(item) {
   var currNode = this.head;
   while (currNode.element != item) {
      currNode = currNode.next;
   }
   return currNode;
}

function insert(newElement, item) {
   var newNode = new Node(newElement);
   var current = this.find(item);
   newNode.next = current.next;
   current.next = newNode;
}
   

var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");
cities.display();
console.log();
cities.remove("Carlisle");
cities.display();

 

其他的还有:双向链表和循环链表

 

 

《数据结构与算法JavaScript描述》第六章

修改时间 2019-06-19

真诚赞赏,手留余香
赞赏
随机推荐
物理对齐和视觉对齐
Apache、PHP 配置 open_basedir,以及性能问题
包含汉字元素的PHP数组转成json字符串
Fatal error:Call-time pass-by-reference has been removed
Apache限制虚拟主机网速「mod_bw」
thinkphp5 r4分页类传入参数
CentOS7 安装 LAMP 和 Mod Security 手记
一个LOGO的设计过程
Content Security Policy 与跨域脚本攻击 XSS
JavaScript 链表