《数据结构与算法JavaScript描述》学习笔记（一）—--—链表

《数据结构与算法JavaScript描述》学习笔记（一）—--—链表 2017-07-03

暑假看了下 《数据结构与算法JavaScript描述》 ，这里写一下学习链表的笔记。

为什么使用链表

JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言相比（比如 C++ 跟 Java）的数组相比，效率更低。如果你发现数组的实际使用时很慢，就可以考虑使用链表了。

什么是链表

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

如图所示，单链表最开始包含一个 头结点 （Header）作为链表的接入点，链表的表尾是一个 NULL 。

单链表的实现

在JavaScript中链表包含两个类。Node类用来表示节点，LinkList类提供了插入节点、删除节点、显示列表元素的方法，
以及一些其他辅助方法。

Node类

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

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

LinkedList类

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

这里只有一个属性head，其指向头结点。
Head节点的next属性被初始化为null,当有新元素插入时，next会指向新的元素，所以这里没有必要修改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;
}

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;
  }
}

源码地址

双向链表

双向链表与单链表相比每个节点多了一个对象引用指向其的前驱。
如图所示
project

源码地址

循环链表

循环链表和单链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头结点的next属性指向它本身。
project

1	head.next = head;

源码地址