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

真诚赞赏,手留余香
赞赏
随机推荐
MySQL 处理高并发,防止库存超卖(乐观锁和悲观锁)
Vuex
vue-router 切换页面时设置过渡动画
Windows Firewall and secure FTP (FTPS) traffic
PHP开发api接口安全验证
文件的上传与无刷新上传
微信支付错误两个问题的解决:curl出错,错误码:60
CSS中比一像素还要细的边框
Wordpress 增加文章阅读次数或点赞次数(非插件实现)
JS时间戳转换