数据结构于JS也可以成为CP（五）链表

萌兔IT

发布于 2019-07-26 14:59:32

6210

发布于 2019-07-26 14:59:32

文章被收录于专栏：萌兔it

Hello大家好～兔妞今天给大家带来的是链表哦！为什么有链表呢，因为数组并不总是组织数据的最佳数据结构。由于在JavaScript中数组是一个对象，所以js的数组相比其他语言的数组效率较低。那么我们就可以考虑使用链表啦。

那么什么是链表呢？链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。

链表的实现

链表要怎么实现呢？我们先分析一下链表的结构。如下图，元素为链表中的每一个节点，为什么链表的效率高呢，因为链表有链接，这样才能在遍历链表的时候跟着链接从头元素到尾元素，而尾元素指向null节点。

当我们对链表进行操作时，如插入元素，我们需要将前面的节点指向新加入的节点，新加入的节点再指向原来的前节点所指向的节点。

当删除元素的时候，我们只要将待删除元素前节点元素指向待删元素的后元素，再将待删元素指向null就OK啦。

那我们就看看具体怎么实现吧～首先需要定义一个Node类和LList类，然后需要遍历列表并找到指定数据，然后我们需要显示列表中元素。还有就是链表的优势所在：插入数据和删除数据。

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

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;
}
function display() {
  var currNode = this.head;
  while (!(currNode.next == null)) {
     print(currNode.next.element);
     currNode = currNode.next;
  }
}
function findPrevious(item) {
  var currNode = this.head;
  while (!(currNode.next == null) &&
          (currNode.next.element != item)) {
    currNode = currNode.next;
  }
    return currNode;
}
function remove(item) {
  var prevNode = this.findPrevious(item);
  if (!(prevNode.next == null)) {
      prevNode.next = prevNode.next.next;
  }
}

其他更多类型的链表

1）双向链表：单向链表存在着一个问题，如果想从后遍历就会出现问题。我们要怎么解决呢，那么就是给Node增加一个属性，该属性存储指向前驱节点的链接。

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

2）循环链表：这个呢，也可以称为环形链表，它的特点就是当创建链表的时候（也就是链表为空时），头节点的next属性指向它本身，并传导至链表中的每个节点。所以我们需要将LList对象加入一个方法。

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-06-30，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法