数据结构与算法学习之循环链表

循环链表

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个节点的 next 指针指向头节点，整个链表形成一个环。如下图：

循环链表与链表 (普通链表) 的唯一区别在于，链表的最后一个节点的 next 指针指向的是 undefined，而循环链表的最后一个节点的 next 指针指向的是头节点。

实现循环链表

定义节点类

class Node {
    constructor(element) {
      this.element = element;
    this.next = undefined;
  }
}

定义循环链表类

function defaultEquals(a, b) {
  return a === b;
}
class CircularLinkedList {
    constructor(equalsFn = defaultEquals) {
      this.count = 0;
    this.head = undefined;
    this.equalsFn = qeualsFn;
  }
}

接下来，我们为循环链表定义一些方法：
append(element) 向循环链表尾部添加一个新元素
insert(element, index) 向循环链表的特定位置插入一个新元素
getElementAt(index) 返回循环链表中特定位置的元素，若元素不存在，返回 undefined
remove(element) 从循环链表中移除一个元素
removeAt(index) 从循环链表的特定位置移除一个元素
removeHead() 移除首节点
removeTail() 移除尾结点
indexOf(element) 返回指定元素在循环链表中的索引，若没有该元素则返回 -1
head() 查看首节点
tail() 查看尾结点
size() 返回循环链表包含的元素个数，即返回链表的长度
isEmpty() 判断循环链表是否为空
clear() 清空循环链表
toString() 返回表示整个循环链表的字符串

下面，我们逐一实现这些方法：

append 向循环链表尾部添加一个新元素

向循环链表尾部添加一个新元素时，有两种情景：

• 循环链表为空，添加的是第一个yuans
• 循环链表不为空，向其追加元素

  append(element) {
    const node = new Node(element);
  let current = null;
  // 循环链表为空，添加的是第一个节点
  if (this.head == null) {
    // 让 head 指向新添加的节点
      this.head = node;
  } else {
    // 循环链表不为空，在循环链表尾部添加新节点
      current = this.getElementAt(this.size() - 1);
    // 将当前的尾节点的 next 指针指向node，node变成新的尾节点
    current.next = node;
  }
  // 将尾节点的 next 指针指向头节点，形成一个环
  node.next = this.head;
  this.count++;
  }

我们来分析一下这两种情景：

第一种情景：向空的循环链表添加一个元素。当我们创建一个循环链表实例时，head 默认指向 undefined，也就意味着此时的循环链表是一个空链表，我们是在空的循环链表添加第一个元素，因此我们要做的就是让 head 指向这个新添加的节点 node，同时要把新节点的 next 指针指向 head，也就是指向自己。

if (this.head == null) {
  // 让 head 指向新添加的节点
  this.head = node;
}
// 将尾节点的 next 指针指向头节点，形成一个环
node.next = this.head;

第二种情景：循环链表不为空，向其追加元素。向一个不为空的循环链表添加一个新元素，首先需要找到最后一个元素。我们使用 getElementAt 方法获取循环链表的最后一个元素，然后将它的 next 指针指向新添加的节点，同时将新节点的 next 指针指向头节点。

else {
  // 循环链表不为空，在循环链表尾部添加新节点
  current = this.getElementAt(this.size() - 1);
  // 将当前的尾节点的 next 指针指向node，node变成新的尾节点
  current.next = node;
}
// 将尾节点的 next 指针指向头节点，形成一个环
node.next = this.head;

insert 向循环链表的特定位置插入一个新元素

向循环链表中插入一个新元素，我们需要考虑三种情景：

• 插入的位置不合法，元素插入失败
• 在循环链表的第一个位置（头部）插入新元素

• 在循环链表的中间或尾部插入新元素

  insert(element, index) {
  // 插入的位置合法，将元素插入到循环链表中
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
    // current 变量是对头节点的引用
    let current = this.head;
    if (index === 0) {
        // 在循环链表的第一个位置插入新元素
      if (this.head == null) {
        // 在空循环链表的第一个位置插入新元素
        // 将 head 指向新添加的节点
          this.head = node;
        // 将新添加节点的 next 指针指向 head，即指向自己
        node.next = this.head;
      } else {
        // 在非空循环链表的第一个位置插入新元素
        // 将新添加节点 node 的 next 指针指向现在的 head 引用的头节点（current 变量）
          node.next = current;
        // 获取循环链表中最后一个节点
        current = this.getElementAt(this.size());
        // 将 head 指向新添加的 node 节点，即新的头节点
        this.head = node;
        // 此时的 current 变量是循环链表最后一个节点的引用
        // 将最后一个节点的 next 指针指向 head，即指向头节点
        current.next = this.head;
      }
    } else {
        // 在循环链表的中间或尾部插入新元素
      // 新节点插入位置的前一个节点
      const previous = this.getElementAt(index - 1);
      // 将新插入元素的 next 指针指向插入位置的下一个节点
      node.next = previous.next;
      // 将新节点插入位置的前一个节点的 next 指针指向新插入的节点
      previous.next = node;
    }
    // 更新循环链表的长度
    this.count++;
    // 返回 true ，表示元素插入成功
    return true;
  }
  // 插入的位置不合法，返回false，表示元素没有添加到循环链表中
  return false;
  }

  下面，我们来分析一下这三种情景：

第一种情景：插入的位置不合法。由于我们是根据位置（索引）插入元素，因此在插入前需要先检查越界值，如果越界了，就返回false，表示元素没有插入到循环链表中。

第二种情景：在循环链表的第一个位置（头部）插入新元素。
第一种情况，在空链表的第一个位置插入新元素，将 head 赋值为新添加的元素，并将新添加元素的 next 指针指向 head。在这种情况下，新添加的元素即是头节点也是尾节点，因此它的 next 指针指向自己。
第二种情况，在一个非空循环链表的第一个位置插入一个新元素。我们首先将新插入节点的 next 指针指向当前的头节点（head），新插入节点变成了新的头节点，然后将循环链表的最后一个节点的 next 指针指向新的头节点，即指向新插入的节点。

第三种情景：在循环链表的中间或尾部插入新元素。我们首先找到插入位置的前一个节点 previous，然后将 previous 的 next 指针指向新插入的节点，再将新插入节点的next指针指向插入位置的后一个节点，这样，新节点就插入成功了。

getElementAt 返回循环链表中特定位置的元素

getElementAt 方法返回循环链表中特定位置的元素，若元素不存在，返回 undefined

getElementAt(index) {
  // 传入的位置合法，迭代循环链表查找目标位置的元素
    if (index >= 0 && index <= this.count) {
    // 从循环链表的第一个位置开始迭代循环链表
      let node = this.head;
    for (let i = 0; i < index && node != null; i++) {
      // 迭代整个循环链表直到目标index，结束迭代时，此时的 node 节点是目标index的前一个节点
      // 因此使用 node.next 获取目标index的节点
        node = node.next;
    }
    return node;
  }
  // 传入的位置不合法，在循环链表中找不到该位置的节点，返回 undefined
  return undefined;
}

代码分析：
我们首先会对传入的 index 参数做合法性检查，如果传入的位置时不合法的参数，我们会返回 undefined，因为这个位置在循环链表中不存在。
然后从循环链表的第一个节点开始，迭代整个循环链表直到目标index，当结束迭代时，node 就是我们要查找的目标节点。

remove 从循环链表中移除一个元素

remove(element) {
    const index = this.indexOf(element);
  return this.removeAt(index);
}

removeAt 从循环链表的特定位置移除一个元素

从循环链表的特定位置移除一个元素时， 我们需要考虑三种情景：

• 移除的位置不合法，移除移除失败
• 移除循环链表的第一个元素

• 移除循环链表的最后一个或中间的元素

  removeAt(index) {
  // 
    if (index >= 0 && index < this.count) {
    // current 变量是对循环链表第一个元素（即首节点）的引用
      let current = this.head;
    // 移除的是循环链表中的第一个元素
    if (index === 0) {
      // 从只有一个元素的循环链表中删除一个元素
        if (this.size() === 1) {
        // 将 head 赋值为 undefined 即可
          this.head = undefined;
      } else {
        // 从非空循环链表移除第一个元素
        // 保存当前 head 元素的引用
          const removed = this.head;
        // 循环链表中最后一个元素
        current = this.getElementAt(this.size() - 1);
        // 将 head 指向第二个元素
        this.head = this.head.next;
        // 将最后一个元素是 next 指针指向新的 head
        current.next = this.head;
        // 更新 current 变量为要移除的第一个元素
        current = removed;
      }
    } else {
      // 移除位置的前一个节点
        const previous = this.getElementAt(index - 1);
      // 要移除的元素
      current = previous.next;
      // 将移除位置的前一个节点的 next 指针指向移除位置的下一个节点
      previous.next = current.next;
    }
    // 更新循环链表的长度
    this.count--;
    // 返回移除节点的数据域
    return current.element;
  }
  // 传入的 index 不是有效位置，返回 undefined，表示没有从循环链表中移除元素
  return undefined;
  }

  下面，我们来分析一下这三种情景：

第一种情景：移除的位置不合法。removeAt 方法是根据位置（index）来移除循环链表中的元素，我们首先需要对 index 进行有效性检查。从 0 (包括 0) 到循环链表的长度（count - 1）都是有效的位置。如果 index 不是有效的位置，返回 undefined，表示没有从循环链表中移除元素。

第二种情景：移除循环链表的第一个元素。
第一种情况，从只有一个元素的循环链表中移除一个元素，我们只需要将 head 赋值为 undefined 即可。
第二种情况，从一个非空的循环链表中移除第一个元素。在这种情况下，head 的指向会发生改变，我们需要修改最后一个节点的 next 指针的指向。因此，我们首先保存现在的 head 元素的引用，它将会从循环链表中移除。然后获取循环链表中最后一个节点，将 head 指向循环链表中的第二个元素，也就是新的 head，然后将最后一个节点的 next 指针指向新的head。这样，就将原来的 第一个元素移除了。

第三种情景：移除循环链表的最后一个或中间的元素。我们首先获取到移除位置的前一个节点 previous，通过 previous.next 获得要移除的元素，然后将 previous 的 next 指针指向移除位置的后一个节点，即可将我们想要移除的元素从循环链表中移除了。

removeHead 移除首节点

removeHead() {
    if (this.isEmpty()) {
      return undefined;
  }
  let current = this.head;
  // 从只有一个元素的循环链表中删除一个元素
  if (this.size() === 1) {
    // 将 head 赋值为 undefined 即可
    this.head = undefined;
  } else {
    // 从非空循环链表移除第一个元素
    // 保存当前 head 元素的引用
    const removed = this.head;
    // 循环链表中最后一个元素
    current = this.getElementAt(this.size() - 1);
    // 将 head 指向第二个元素
    this.head = this.head.next;
    // 将最后一个元素是 next 指针指向新的 head
    current.next = this.head;
    // 更新 current 变量为要移除的第一个元素
    current = removed;
  }
  this.count--;
  return current.element;
}

removeTail 移除尾节点

removeTail() {
    if (this.isEmpty()) {
      return undefined;
  }
   // 尾节点的前一个节点
  const previous = this.getElementAt(this.size() - 1);
  // 要移除的尾节点
  const current = previous.next;
  // 将尾节点的前一个节点的 next 指针指向 head （current.next 指向的是 head）
  previous.next = current.next;
  this.count--;
  return current.element
}

移除尾节点，首先需要找到尾节点的前一个节点 previous，然后通过 previous.next 获取到尾节点，并将尾节点缓存下来，接着将 previous 的 next 指针指向 head (尾节点的next指针指向的是 head)，这样，尾节点就从循环链表中移除了。

indexOf 返回指定元素在循环链表中的索引

indexOf(element) {
  // 对循环链表第一个元素（即首节点）的引用
    let current = this.head;
  // 迭代循环链表，从 head（索引 0）开始，直到循环链表长度（count 变量）为止
  for (let i = 0; i < this.size() && current != null; i++) {
    // 比较当前节点的元素与目标元素是否相等，若相等，当前节点就是我们要找的节点，返回当前节点的位置
      if (this.equalsFn(element, current.element)) {
        return i;
    }
    // 不是我们要找的节点，继续迭代下一个元素
    current = current.next;
  }
  // 循环链表为空或者迭代到循环链表尾部，没有找到目标元素，返回 -1
  return -1;
}

代码分析：
从循环链表中查找某个节点的位置，就需要对循环链表进行迭代。我们从 head（索引 0）开始，一直到循环链表长度（count 变量）为止，也就是迭代到循环链表的尾部。

在每次迭代时，我们都会验证 current 节点的元素和目标元素是否相等，如果相等，当前位置的元素就是我们要找的元素，返回该元素的位置。如果不是我们要找的元素，则继续迭代下一个节点。

如果循环链表为空，或者我们迭代到了循环链表的尾部，都没有找到我们想要的元素，则返回 -1。

head 查看首节点

head() {
    return this.head;
}

tail 查看尾结点

tail() {
    return this.getElementAt(this.size());
}

size 返回循环链表包含的元素个数

size 方法返回循环链表的节点个数，即返回循环链表的长度。CircularLinkedList 是我们自己构建的类，链表的长度是我们使用 count 变量来控制的，因此返回循环链表的长度，就是返回 count 变量。

size() {
    return this.count;
}

isEmpty 判断循环链表是否为空

isEmpty 方法判断循环链表是否为空。如果循环链表中没有元素，isEmpty 方法就返回 true，否则返回 false。

isEmpty() {
    return this.size() === 0;
}

clear 清空循环链表

clear() {
    this.head = null;
  this.count = 0;
}

toString 返回表示整个循环链表的字符串

toString 方法将 CircularLinkedList 对象转换成一个字符串，然后返回循环链表内容的字符串。

toString() {
    if (this.head == null) {
      return '';
  }
  let objString = `${this.head.element}`;
  let current = this.head.next;
  for (let i = 1;  i < this.size() && current != null; i++) {
      objString = `${objString}, ${current.element}`;
    current = current.next;
  }
  return objString;
}

代码分析：
首先，如果循环链表为空，我们就返回一个空字符串；

如果循环链表不为空，我们首先用循环链表第一个元素的值来初始化方法返回的字符串objString。然后迭代循环链表的所有其它元素，将元素值添加到字符串 objString 上；

当迭代完循环链表后，返回循环链表内容的字符串。

完整代码

// 元素是否相等比较函数
function defaultEquals(a, b) {
    return a === b;
}
// 节点类
class Node {
    constructor(element) {
    this.element = element;
    this.next = null;
  }
}
class CircularLinkedList {
    constructor(equalsFn = defaultEquals) {
      this.count = 0;
    this.head = undefined;
    this.equalsFn = quealsFn;
  }
  // 向循环链表尾部添加一个新元素
  append(element) {
      const node = new Node(element);
    let current = null;
    if (this.head == null) {
        this.head = node;
    } else {
        current = this.getElementAt(this.size() - 1);
      current.next = node;
    }
    node.next = this.head;
    this.count++;
  }
  // 向循环链表的特定位置插入一个新元素
  insert(element, index) {
      if (index >= 0 && index <= this.count) {
        const node = new Node(element);
      let current = this.head;
      if (index === 0) {
          if (this.head == null) {
            this.head = node;
          node.next = this.head;
        } else {
            node.next = current;
          current = this.getElementAt(this.size());
          this.head = node;
          current.next = this.head;
        }
      } else {
          const previous = this.getElementAt(this.size() - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }
  // 返回循环链表中特定位置的元素
  getElementAt(index) {
      if (index >= 0 && index <= this.count) {
        let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
          node = node.next;
      }
      return node;
    }
    return undefined;
  }
  // 从循环链表中移除一个元素
  remove(element) {
      const index = this.indexOf(element);
    return this.removeAt(index);
  }
  // 从循环链表的特定位置移除一个元素
  removeAt(index) {
      if (index >= 0 && index < this.count) {
        let current = this.head;
      if (index === 0) {
          if (this.size() === 1) {
            this.head = undefined;
        } else {
            const removed = this.head;
          current = this.getElementAt(this.size() - 1);
          this.head = this.head.next;
          current.next = this.head;
          current = removed;
        }
      } else {
          const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
  // 移除首节点
  removeHead() {
      if (this.isEmpty()) {
        return undefined;
    }
    let current = this.head;
    if (this.size() === 1) {
        this.head = undefined;
    } else {
        const removed = this.head;
      current = this.getElementAt(this.size() -1);
      this.head = this.head.next;
      current.next = this.head;
      current = removed;
    }
    this.count--;
    return current.element;
  }
  // 移除尾节点
  removeTail() {
      if (this.isEmpty()) {
        return undefined;
    }
    const previous = this.getElementAt(this.size() -1);
    const current = previous.next;
    previous.next = current.next;
    this.count--;
    return current.element;
  }
  // 返回指定元素在循环链表中的索引
  indexOf() {
      let current = this.head;
    for (let i = 0; i < this.size() && current != null; i++) {
        if (this.equalsFn(element, current.element)) {
          return i;
      }
      current = current.next;
    }
    return -1;
  }
  // 查看首节点
  head() {
      return this.head;
  }
  // 查看尾节点
  tail() {
      return this.getElementAt(this.size())
  }
  // 返回循环链表包含的元素个数
  size() {
      return this.count;
  }
  // 判读循环链表是否为空
  isEmpty() {
      return this.size() === 0;
  }
  // 清空循环链表
  clear() {
      this.head = null;
    this.count = 0;
  }
  // 返回整个循环链表的字符串
  toString() {
      if (this.head == null) {
        return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size && current != null; i++) {
        objString = `${objString}, ${current.element}`;
      current = current.next;
    }
    return objString;
  }
}