JavaScript数据结构之链表

[heyushuo]

链表和数组的区别

• 链表用来存储有序的元素集合,数组是需要一块连续的内存空间来存储,但不同于数组，链表中的元素在内存中并不是连续放置的。
• 链表由一个存储元素本身的节点和一个指向下一个元素的指针构成。当要插入或删除元素时，只需要修改相应元素上的指针就可以了,时间复杂度是 O(1)。但是数组在插入和删除时就要移动大量元素,时间复杂度是 O(N).
• 数组利用下标可以找到元素,查找的时间复杂度是 O(1),链表需要从起点开始迭代列表,查找的时间复杂度是 O(N)。

链表的数据结构如下:

单链表

单链表,由于标识出链表的起始节点却有点麻烦,随意大部分链表最前面有一个特殊的节点,叫做头节点,链表结构改造如下

链表插入或删除一个元素效率非常高,只需要修改相应元素上的指针就可以了.

下图展示了向链表插入一个 cookies 元素和删除一个 Bacon 元素

链表还有其他一些操作，但插入和删除元素最能说明链表为什么如此有用

实现一个单链表

设计一个链表包含两个类

• Node 类用来表示节点
• LinkList 类提供了插入节点/删除节点/显示列表元素的方法,以及一些辅助方法

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

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

LinkList 类提供了插入节点/删除节点/显示列表元素的方法,以及一些辅助方法

function LList() {
  //链表只有一个属性，那就是使用一个 Node 对象来保存该链表的头节点
  this.head = new Node("head");
  this.find = find; //查找方法
  this.insert = insert; //插入方法
  this.remove = remove; //删除方法
  this.display = display; //展示节点
}

链表只有一个属性head，那就是使用一个 Node 对象来保存该链表的头节点,head 节点的 next 属性被初始化为 null，当有新元素插入时，next 会指向新的元素

接下来实现一下链表的其他方法

1. find方法(这里需要注意一点当查询到最后一个的时候next指向null)

function find(item) {
  var currNode = this.head;
  //从起点开始迭代列表直到找到元素
  while (!(currNode.next == null) && currNode.data != item) {
    currNode = currNode.next;
  }
  return currNode;
}

2.insert方法,链表中插入一个节点。向链表中插入新节点时，需要明确指出要在哪个节点前面或后面插入。

function insert(newElement, item) {
  var newNode = new Node(newElement);
  //找到需要插入节点的位置
  var current = this.find(item);
  //把新节点的next指向(`current.next`这个是下一个节点)
  newNode.next = current.next;
  //然后再把current.next指向新的节点
  current.next = newNode;
}

3.remove方法,从链表中删除节点时,需要先找到待删除节点前面的节点.找到节点后,修改它的 next 属性,使其不再指向待删除节点,而是指向待删除节点的下一个节点.

//找到待删除节点前面的节点
function findPrevious(item) {
  var currNode = this.head;
  while (!(currNode.next == null) && currNode.next.data != item) {
    currNode = currNode.next;
  }
  return currNode;
}

function remove(item) {
  //找到待删除节点前面的节点
  var prevNode = findPrevious(item);
  if (!(prevNode.next == null)) {
    //把前一个的节点,指向要删除节点的下一个节点
    prevNode.next = prevNode.next.next;
  }
}

4.display方法,显示链表中的所有元素

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

用 ES6 的 class 整体上实现以下

class Node {
  constructor() {
    this.data = data;
    this.next = null;
  }
}
class LList {
  constructor() {
    this.head = new Node("head");
  }

  find(item) {
    var currNode = this.head;
    //从起点开始迭代列表直到找到元素
    while (!(currNode.next == null) && currNode.data != item) {
      currNode = currNode.next;
    }
    return currNode;
  }

  insert(newElement, item) {
    var newNode = new Node(newElement);
    //找到需要插入节点的位置
    var current = this.find(item);
    //把新节点的next指向(`current.next`这个是下一个节点)
    newNode.next = current.next;
    //然后再把current.next指向新的节点
    current.next = newNode;
  }

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

  remove(item) {
    //找到待删除节点前面的节点
    var prevNode = findPrevious(item);
    if (!(prevNode.next == null)) {
      //把前一个的节点,指向要删除节点的下一个节点
      prevNode.next = prevNode.next.next;
    }
  }

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

测试一下实现的方法

var cities = new LList();
cities.insert("kebi", "head");
cities.insert("yaoming", "kebi");
cities.insert("heyushuo", "yaoming");
cities.display(); //kebi yaoming heyushuo
console.log("-----------");
cities.insert("aaa", "yaoming");
cities.display(); //kebi yaoming aaa heyushuo
cities.remove("aaa");
console.log("-----------");
cities.display(); //kebi yaoming heyushuo

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

此时向链表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在从链表中删除节点时，效率提高了，不需要再查找待删除节点的前驱节点了。

循环链表

循环链表和单向链表相似，节点类型都是一样的。将单链表中尾结点的指针由空指针指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表就简称为循环链表。

双向链表和循环链表就不一一实现了,可以看《JavaScript 数据结构与算法》了解更多

参考

《JavaScript 数据结构与算法》参考