JS中数据结构之链表

时间: 2019-01-17阅读: 800标签: 数据结构

数组不总是组织数据的最佳数据结构,在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移。

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。许多链表的实现都在链表最前面有一个特殊节 点,叫做头节点。如下图:


基于对象的链表的实现

Node 类用来表示节点,包含两个属性:element 用来保存节点上的数据,next 用来保存指向下一个节点的链接。

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

LList 类提供了对链表进行操作的方法。该类的功能包括插入删除节点、在列表中查找给定的值。

function LList() {
  this.head = new Node("head");  //使用一个 Node 对象来保存该链表的头节点。
  this.find = find;
  this.insert = insert;
  this.remove = remove;
  this.display = display;
}

find() 方法遍历链表,查找给定数据。如果找到数据,该方法就返回保存该数据的节点。如果查找成功,该方法返回包含该数据的节点;否则,返回 null。

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

insert() 方法在一个已知节点后面插入元素

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

display() 方法用来显示链表中的元素

function display() {
  var currNode = this.head;
  while (!(currNode.next == null)) {
    print(currNode.next.element);
    currNode = currNode.next;
  }
}
站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/1834

关闭

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!