js实现链表思路

实现链表的基本结构

链表由节点（Node）组成，每个节点包含两个部分：

• value：存储数据
• next：指向下一个节点的引用（默认为 null）

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

初始化链表

链表类（LinkedList）需维护一个头节点（head）和链表长度（size）：

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

插入节点

尾部插入
遍历链表找到最后一个节点，将新节点链接到其 next：

append(value) {
  const newNode = new Node(value);
  if (!this.head) {
    this.head = newNode;
  } else {
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
  this.size++;
}

头部插入
新节点的 next 指向原头节点，并更新链表的 head：

prepend(value) {
  const newNode = new Node(value);
  newNode.next = this.head;
  this.head = newNode;
  this.size++;
}

删除节点

按值删除
遍历链表找到目标节点的前驱节点，修改其 next 以跳过目标节点：

remove(value) {
  if (!this.head) return;
  if (this.head.value === value) {
    this.head = this.head.next;
    this.size--;
    return;
  }
  let current = this.head;
  while (current.next) {
    if (current.next.value === value) {
      current.next = current.next.next;
      this.size--;
      return;
    }
    current = current.next;
  }
}

查找节点

遍历链表，匹配目标值：

contains(value) {
  let current = this.head;
  while (current) {
    if (current.value === value) {
      return true;
    }
    current = current.next;
  }
  return false;
}

遍历链表

输出所有节点的值：

print() {
  let current = this.head;
  const values = [];
  while (current) {
    values.push(current.value);
    current = current.next;
  }
  console.log(values.join(" -> "));
}

示例用法

const list = new LinkedList();
list.append(1);
list.append(2);
list.prepend(0);
list.print(); // 输出: 0 -> 1 -> 2
list.remove(1);
list.print(); // 输出: 0 -> 2
console.log(list.contains(2)); // 输出: true