JavaScript数据结构之链表各种操作详解

链表是一种常见的数据结构，常用于实现栈和队列等数据结构。链表与数组不同，链表是一种动态数据结构，可以方便地插入和删除数据。下面将详细讲解JavaScript中链表的各种操作。

链表的基本结构

链表由一个个节点组成，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。

下面是一个节点的定义：

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

其中，data表示节点的数据，next指向下一个节点的地址。如果next为null则表示链表的末尾。

整个链表可以用一个头节点来表示。头节点不包含数据，只包含指针，指向第一个节点。

下面是一个头节点的定义：

class LinkedList {
  constructor() {
    this.head = null;
  }
}

链表的各种操作

在链表末尾添加节点

在链表末尾添加节点是一种常见的操作。实现方法如下：

LinkedList.prototype.append = function(data) {
  let node = new Node(data);
  if (this.head === null) {
    this.head = node;
  } else {
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    current.next = node;
  }
};

上述代码中，如果链表为空，则直接将新节点设置为头节点。否则，遍历链表，找到链表末尾，将新节点添加到末尾。

在链表头部添加节点

在链表头部添加节点也常常用到。可以通过如下方式实现：

LinkedList.prototype.prepend = function(data) {
  let node = new Node(data);
  node.next = this.head;
  this.head = node;
};

在添加一个节点时，先将新节点的next指向当前头节点，然后将新节点设置为头节点。

在指定位置插入节点

如果要在链表的指定位置插入数据，可以通过如下方式实现：

LinkedList.prototype.insert = function(data, position) {
  let node = new Node(data);
  if (position === 0) {
    this.prepend(data);
  } else {
    let current = this.head;
    let index = 0;
    while (index < position - 1) {
      current = current.next;
      index++;
    }
    node.next = current.next;
    current.next = node;
  }
};

如果需要在头部插入，可以调用prepend方法。否则，需要遍历链表，找到插入位置，然后将新节点插入到链表中。

遍历链表

遍历链表可以通过如下方式实现：

LinkedList.prototype.traverse = function() {
  let current = this.head;
  while (current !== null) {
    console.log(current.data);
    current = current.next;
  }
};

这个方法通过循环，从头节点开始遍历整个链表，并输出每个节点的数据。

查找节点

如果需要查找链表中的某个节点，可以通过如下方式实现：

LinkedList.prototype.indexOf = function(data) {
  let current = this.head;
  let index = 0;
  while (current !== null) {
    if (current.data === data) {
      return index;
    }
    current = current.next;
    index++;
  }
  return -1;
};

这个方法遍历整个链表，查找某个节点的数据是否等于指定的数据。如果找到则返回节点的索引，否则返回-1。

删除节点

删除节点也是链表中的一种常见操作，可以通过如下方式实现：

LinkedList.prototype.delete = function(data) {
  if (this.head === null) {
    return;
  }
  if (this.head.data === data) {
    this.head = this.head.next;
    return;
  }
  let current = this.head;
  while (current.next !== null) {
    if (current.next.data === data) {
      current.next = current.next.next;
      return;
    }
    current = current.next;
  }
};

如果需要删除头节点，直接将头节点指向下一个节点即可。否则需要遍历链表，找到要删除的节点，然后删除它。

示例说明

示例1：用链表实现栈

链表可以方便地实现栈和队列等数据结构。下面示范通过链表实现栈的方式：

class Stack {
  constructor() {
    this.list = new LinkedList();
  }

  push(data) {
    this.list.prepend(data);
  }

  pop() {
    let head = this.list.head;
    if (head === null) {
      return null;
    }
    this.list.head = head.next;
    return head.data;
  }

  isEmpty() {
    return this.list.head === null;
  }

  size() {
    let current = this.list.head;
    let count = 0;
    while (current !== null) {
      count++;
      current = current.next;
    }
    return count;
  }
}

可以看到，这个栈类内部使用链表来存储数据。push方法将新的元素添加到链表头部，pop方法将链表的头节点弹出，并返回节点的数据。isEmpty方法用来判断栈是否为空，size方法返回栈的元素个数。

示例2：通过链表实现一元多项式

链表还可以用来实现一元多项式。一元多项式可以表示为：

a0 + a1x + a2x² + ... + anxⁿ

这个式子中，a0 ~ an表示系数，x表示未知数，n表示项数。

下面是一个用链表实现一元多项式的示例：

class Node {
  constructor(coef, exp) {
    this.coef = coef;
    this.exp = exp;
    this.next = null;
  }
}

class Polynomial {
  constructor() {
    this.head = null;
  }

  append(coef, exp) {
    let node = new Node(coef, exp);
    if (this.head === null) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
  }

  add(p) {
    let result = new Polynomial();
    let p1 = this.head;
    let p2 = p.head;
    while (p1 !== null && p2 !== null) {
      if (p1.exp === p2.exp) {
        result.append(p1.coef + p2.coef, p1.exp);
        p1 = p1.next;
        p2 = p2.next;
      } else if (p1.exp > p2.exp) {
        result.append(p1.coef, p1.exp);
        p1 = p1.next;
      } else {
        result.append(p2.coef, p2.exp);
        p2 = p2.next;
      }
    }
    while (p1 !== null) {
      result.append(p1.coef, p1.exp);
      p1 = p1.next;
    }
    while (p2 !== null) {
      result.append(p2.coef, p2.exp);
      p2 = p2.next;
    }
    return result;
  }

  toString() {
    let current = this.head;
    let str = '';
    while (current !== null) {
      if (current.coef !== 0) {
        str += current.coef;
        if (current.exp !== 0) {
          str += 'x^' + current.exp;
        }
        if (current.next !== null && current.next.coef > 0) {
          str += '+';
        }
      }
      current = current.next;
    }
    return str;
  }
}

这个代码中，每个节点包含系数coef和指数exp，通过链表可以存储多个节点。append方法用来向多项式添加新的项，add方法用来将两个多项式相加，toString方法将多项式转化为字符串输出。

以上就是链表的各种操作详解，通过这些方法，可以方便地实现更多的数据结构和算法。