JavaScript数据结构之单链表和循环链表

单链表和循环链表是数据结构中非常基础的两种链式结构，它们可以用JavaScript来实现。本文将详细讲解单链表和循环链表的实现过程和常见操作，且包含两条示例说明。

单链表

单链表是一种链式结构，每个节点包含数据和指向下一个节点的指针。单链表最后一个节点的指针指向NULL，表示链表的结尾。

实现单链表

在JavaScript中，我们可以使用对象来实现单链表。每个节点可以用一个对象来表示，该对象中包含数据和指向下一个节点的指针。

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

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

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

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

上面的代码中，我们定义了两个构造函数：Node和LinkedList。Node对象表示链表中的节点，LinkedList对象表示整个链表。

在LinkedList的构造函数中，我们首先定义了一个头节点head，它的element值为字符串"head"，next为null，表示它是链表的开头。然后我们定义了一些常用的方法，例如find、insert、remove和display。这些方法可以用来在链表中查找、插入、删除和显示节点。其中，find方法和remove方法使用了while循环，该循环会一直遍历链表，直到遍历到指定的节点。

单链表示例

下面是一个将单链表用于队列的示例。在JavaScript中，单链表可以用来实现队列，只需要在链表尾部添加元素（入队），在链表头部删除元素（出队）即可。

function Queue() {
  this.dataStore = new LinkedList();
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.back = back;
  this.toString = toString;
  this.empty = empty;
}

function enqueue(element) {
  this.dataStore.insert(element, "head");
}

function dequeue() {
  this.dataStore.remove(this.front());
}

function front() {
  var firstNode = this.dataStore.head.next;
  if (firstNode == null) {
    return null;
  }
  return firstNode.element;
}

function back() {
  var lastNode = this.dataStore.head;
  while (lastNode.next != null) {
    lastNode = lastNode.next;
  }
  if (lastNode == this.dataStore.head) {
    return null;
  }
  return lastNode.element;
}

function toString() {
  var result = "";
  var currNode = this.dataStore.head;
  while (currNode.next != null) {
    result += currNode.next.element + "\n";
    currNode = currNode.next;
  }
  return result;
}

function empty() {
  return this.dataStore.head.next == null;
}

在上面的代码中，我们定义了Queue对象来表示队列。我们将Queue对象的dataStore属性设置为一个LinkedList对象，这样就可以使用LinkedList的方法对队列进行操作。其中，enqueue方法用于在链表尾部添加元素，而dequeue方法用于在链表头部删除元素。front和back方法用于获取队列的首部和尾部元素。

循环链表

循环链表是一种链式结构，它的最后一个节点的指针指向链表的第一个节点，形成一个循环。

实现循环链表

在JavaScript中，我们可以使用两种方式来实现循环链表：

• 基于LinkedList对象，在LinkedList的构造函数中将最后一个节点的next指向head。
• 将最后一个节点的next指针设置为head。

本文中我们选用第一种方式，下面是实现代码：

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

// 和单链表相同的代码
function find(item) {...}

function insert(newElement, item) {...}

function remove(item) {...}

function display() {...}

上面的代码和单链表的实现非常相似，唯一的不同是在CircularLinkedList的构造函数中，我们将最后一个节点的next属性设置为head，表示这是一个循环链表。

循环链表示例

下面是一个使用循环链表来实现约瑟夫环的示例：

function Josephus(n, m) {
  var L = new CircularLinkedList();
  var currNode = L.head;
  for (var i = 1; i <= n; i++) {
    currNode.next = new Node(i);
    currNode = currNode.next;
  }
  currNode.next = L.head.next; // 将最后一个节点的next指向第一个节点，形成循环链表
  currNode = L.head.next;

  while (currNode.next != currNode) {
    // 数m个数，然后删除当前元素
    for (var i = 1; i < m; i++) {
      currNode = currNode.next;
    }
    L.remove(currNode.element);
    currNode = currNode.next;
  }
  return currNode.element; // 最后一个元素即为胜利者
}

在上面的代码中，我们定义了Josephus函数来实现约瑟夫环。我们首先创建一个循环链表L，然后依次插入1~n个元素。最后将最后一个元素的next指向第一个元素，形成循环链表。

接着，我们使用一个while循环，数m个数，然后删除当前元素，直到链表中只剩下一个元素。最后返回最后一个元素的值，即为胜利者的编号。

总结

单链表和循环链表是JavaScript中常用的链式结构，能够实现队列、约瑟夫环等应用。在实现链表时，我们需要注意链表头和尾的处理，这是链表操作的重要部分。