JavaScript数据结构之链表的实现

什么是链表

链表是一种线性数据结构，其中的元素在内存中不连续地存储，每个元素通常由一个存储元素本身的节点和一个指向下一个元素的引用组成。相比较于数组，链表具有如下优缺点：

• 优点：动态地添加或删除元素时，无需移动其它元素。(数组则需要移动其它元素)
• 缺点：不能随机地访问某个元素，必须从头开始顺序遍历。(而数组可以通过索引直接访问任何元素)

链表的基本操作

链表的基本操作包括插入、删除、查找等。下面是对应操作的 JavaScript 实现。

创建链表节点

为了实现链表，首先需要创建一个节点类。

class Node {
  constructor(element) {
    this.element = element; // 当前节点元素
    this.next = null; // 下一个节点连接
  }
}

在链表末尾添加元素

在链表末尾添加元素时，需要先找到最后一个节点，然后将该节点的 next 指向新节点。

class LinkedList {
  constructor() {
    this.length = 0; // 链表长度
    this.head = null; // 头节点
  }
  append(element) {
    let node = new Node(element);
    let current;
    if (this.head == null) { // 链表为空
      this.head = node;
    } else { // 链表不为空，找到最后一个节点，并将其 next 指向新节点
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }
}

下面是一个在链表末尾添加元素的示例：

let list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
console.log(list); // 链表长度为 3，头节点为 1，尾节点为 3。

在链表指定位置插入元素

在链表中插入元素时，需要找到被插入位置的前一个节点，然后将该节点的 next 指向新节点，新节点的 next 指向原来的节点。

class LinkedList {
  //...
  insert(position,element){
    if(position>=0&&position<=this.length){
      let node=new Node(element);
      let 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;
    }
    return false;
  }
}

下面是一个在链表指定位置插入元素的示例：

let list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.insert(1,4);
console.log(list); // 链表长度为 4，头节点为 1，尾节点为 3，第二个节点为 4。

删除链表中指定位置的元素

在删除链表中的元素时，需要找到该节点的前一个节点，然后将前一个节点的 next 指向该节点的下一个节点。

class LinkedList {
  //...
  removeAt(position){
    if(position>=0&&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;
    }
    return null;
  }
}

下面是一个在链表中删除指定位置元素的示例：

let list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.removeAt(1);
console.log(list); // 链表长度为 2，头节点为 1，尾节点为 3。

总结

以上就是链表的实现及基本操作的介绍，相信通过以上的示例教程，你已经对链表有了更深层次的理解。需要注意的是，链表虽然能够提高插入和删除元素的效率，但由于无法随机访问任何元素，因此在某些需要快速访问元素的场合并不适用。