Node.js环境下JavaScript实现单链表与双链表结构

下面我详细讲解一下在Node.js环境下如何实现单链表与双链表结构。

什么是链表

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。一般分为单向链表和双向链表两种，下面我们将分别介绍如何在Node.js环境下实现这两种链表结构。

单向链表

单向链表的每个节点只有一个指针，指向下一个节点。它的优点是插入和删除节点的时间复杂度为O(1)，缺点是访问节点的时间复杂度为O(n)。

实现思路

我们首先需要创建一个链表类，包括链表的头部节点和节点数量。在该类中还需要实现链表的增、删、改、查等基本操作，具体思路如下：

1. 创建Node类，表示链表中的节点，包括节点的数据和指向下一个节点的指针。
2. 创建LinkedList类，表示链表，包括链表的头部节点和节点数量。
3. 在LinkedList类中，实现链表的增、删、改、查等基本操作。

具体代码如下：

// Node类表示链表中的节点
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

// LinkedList类表示链表
class LinkedList {
  constructor() {
    this.head = null; // 头部节点
    this.length = 0; // 节点数量
  }

  // 链表添加节点
  append(element) {
    let node = new Node(element),
        current;

    if (this.head === null){ // 如果链表为空
        this.head = node;
    } else {
        current = this.head;

        while(current.next){
            current = current.next;
        }

        current.next = node;
    }
    this.length++; // 更新节点数量
  }

  // 链表删除节点
  removeAt(position) {
    if (position > -1 && position < this.length) {
      let current = this.head, // 当前节点
          previous, // 上一个节点
          index = 0; // 记录节点位置

      if (position === 0) { // 如果删除的是头部节点
        this.head = current.next;
      } else {
        while (index++ < position) { // 遍历链表，查找要删除的节点
          previous = current;
          current = current.next;
        }

        previous.next = current.next; //将上一个节点的指针指向删除节点的下一个节点
      }

      this.length--; // 更新节点数量

      return current.element;
    } else {
      return null;
    }
  }

  // 链表查找节点
  findIndex(element) {
    let current = this.head,
        index = -1;

    while (current) {
      if (element === current.element) {
        return index;
      }

      index++;
      current = current.next;
    }

    return -1;
  }

  // 链表插入节点
  insert(position, element) {
    if (position >= 0 && position <= this.length) {
      let node = new Node(element),
          current = this.head,
          previous,
          index = 0;

      if (position === 0) {
        node.next = current;
        this.head = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }

        previous.next = node;
        node.next = current;

      }

      this.length++;

      return true;
    } else {
      return false;
    }
  }
}

示例说明

我们可以通过以下代码，使用LinkedList类创建链表，并进行增、删、改、查等操作。

const list = new LinkedList();

list.append('a'); // 添加节点
list.append('b');
list.append('c');

console.log(list.length); // 打印节点数量

console.log(list.findIndex('a')); // 查找节点的位置

list.insert(2, 'd'); // 在指定位置插入节点

list.removeAt(1); // 删除制定位置的节点

双向链表

双向链表的每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。它的优点是访问和删除节点的时间复杂度为O(1)，缺点是插入节点的时间复杂度为O(n)。

实现思路

我们同样需要创建一个链表类，包括链表的头部节点、尾部节点和节点数量。在该类中还需要实现链表的增、删、改、查等基本操作，具体思路如下：

1. 创建Node类，表示链表中的节点，包括节点的数据和指向前一个节点和后一个节点的指针。
2. 创建DoublyLinkedList类，表示双向链表，包括链表的头部节点、尾部节点和节点数量。
3. 在DoublyLinkedList类中，实现链表的增、删、改、查等基本操作。

具体代码如下：

// Node类表示链表中的节点
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }
}

// DoublyLinkedList类表示双向链表
class DoublyLinkedList {
  constructor() {
    this.head = null; // 头部节点
    this.tail = null; // 尾部节点
    this.length = 0; // 节点数量
  }

  // 链表添加节点
  append(element) {
    let node = new Node(element);

    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }

    this.length++; // 更新节点数量
  }

  // 链表删除节点
  removeAt(position) {
    if (position > -1 && position < this.length) {
      let current = this.head,
          previous,
          index = 0;

      if (position === 0) {
        this.head = current.next;

        if (this.length === 1) {
          this.tail = null;
        } else {
          this.head.prev = null;
        }

      } else if (position === this.length - 1) {
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = null;

      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }

        previous.next = current.next;
        current.next.prev = previous;
      }

      this.length--;

      return current.element;
    } else {
      return null;
    }
  }

  indexOf(element) {
    let current = this.head,
        index = 0;

    while(current) {
      if (element === current.element) {
        return index;
      }

      index++;
      current = current.next;
    }

    return -1;
  }

  // 链表插入节点
  insert(position, element) {
    if (position >= 0 && position <= this.length) {
      let node = new Node(element),
          current = this.head,
          previous,
          index = 0;

      if (position === 0) {
        if (!this.head) {
          this.head = node;
          this.tail = node;
        } else {
          node.next = current;
          current.prev = node;
          this.head = node;
        }
      } else if (position === this.length) {
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }

        previous.next = node;
        node.prev = previous;
        node.next = current;
        current.prev = node;
      }

      this.length++;

      return true;
    } else {
      return false;
    }
  }
}

示例说明

我们可以通过以下代码，使用DoublyLinkedList类创建双向链表，并进行增、删、改、查等操作。

const list = new DoublyLinkedList();

list.append('a'); // 添加节点
list.append('b');
list.append('c');

console.log(list.length); // 打印节点数量

console.log(list.indexOf('a')); // 查找节点的位置

list.insert(2, 'd'); // 在指定位置插入节点

list.removeAt(1); // 删除指定位置的节点