JS数据结构之双向循环链表

数据结构

发布日期: 2021-08-30

文章字数: 801

这篇文章是JavaScript实现链表数据结构的第四篇文章，本文的主要内容是——双向循环链表。之前我们已经实现过单向链表、单向循环链表以及双向链表数据结构。

双向循环链表结构

双向循环链表的结构和双向链表的接口相同，区别在于双向循环链表的最后一个节点的next指针会指向链表的头节点，而链表头节点的prev指针则指向最后一个节点。所以在实现的时候可以直接继承双向链表。双向循环链表结构如下图所示：
双向循环链表数据结构

增(add)、删(remove)、改(update)、查(getNode)

查(getNode)

对于这个方法，双向循环链表和双向链表的唯一区别在于：双向循环链表首位相连，不存在查询索引超出范围的问题。因此 getNode 这个方法不需要判断查询索引是否超出范围。代码如下：

_getNode(index) {
  let offset = 0;
  let curNode = this.head;
  while (offset++ < index && curNode.element) {
    curNode = curNode.next;
  }
  return curNode;
}

增(add)

这个方法分为两种情况讨论：

在链表头部插入节点；此时是在旧节点之前插入节点，除了建立新头节点与旧头节点之间的指针关系之外，还要将旧头结点与末尾节点之间的指向关系更新到新头节点上；具体操作如下图所示：
其他情况；

add(index, element) {
  if (arguments.length === 1) {
    element = index;
    index = this.size ? this.size - 1 : 0;
  }
  if (index === 0) {
    const oldHead = this.head;
    if (this.head) {
      this.head = new Node(element, oldHead.prev, oldHead);
      oldHead.prev.next = this.head;
      oldHead.prev = this.head;
    } else {
      this.head = new Node(element, null, null);
      this.head.next = this.head;
      this.head.prev = this.head;
    }
  } else {
    const currNode = this._getNode(index);
    const newNode = new Node(element, currNode, currNode.next);
    currNode.next.prev = newNode;
    currNode.next = newNode;
  }
  this.size++;
}

删(remove)

因为双向循环链表有首位相连的特点，因此删除任何一个节点都是一样的，所以删除操作只有一种情况。具体操作如下图所示，将待删除节点的前一个节点的next指针指向待删除节点next的节点，将待删除节点的next节点的prev指针指向待删除节点的prev节点。

remove(index) {
  if (this.size === 0) throw new Error("无法从空链表删除元素");
  if (this.size === 1) {
    this.head = null;
  } else {
    const removeNode = this._getNode(index);
    const prevNode = removeNode.prev;
    prevNode.next = removeNode.next;
    removeNode.next.prev = prevNode;
    if (index === 0) this.head = this.head.next;
  }
  this.size--;
}

完整代码

class CircleDoublyLinkedList extends DoublyLinkedList {
  constructor() {
    super();
  }

  _getNode(index) {
    let offset = 0;
    let curNode = this.head;
    while (offset++ < index && curNode.element) {
      curNode = curNode.next;
    }
    return curNode;
  }

  add(index, element) {
    if (arguments.length === 1) {
      element = index;
      index = this.size ? this.size - 1 : 0;
    }
    if (index === 0) {
      const oldHead = this.head;
      if (this.head) {
        this.head = new Node(element, oldHead.prev, oldHead);
        oldHead.prev.next = this.head;
        oldHead.prev = this.head;
      } else {
        this.head = new Node(element, null, null);
        this.head.next = this.head;
        this.head.prev = this.head;
      }
    } else {
      const currNode = this._getNode(index);
      const newNode = new Node(element, currNode, currNode.next);
      currNode.next.prev = newNode;
      currNode.next = newNode;
    }
    this.size++;
  }

  remove(index) {
    if (this.size === 0) throw new Error("无法从空链表删除元素");
    if (this.size === 1) {
      this.head = null;
    } else {
      const removeNode = this._getNode(index);
      const prevNode = removeNode.prev;
      prevNode.next = removeNode.next;
      removeNode.next.prev = prevNode;
      if (index === 0) this.head = this.head.next;
    }
    this.size--;
  }
}