js 实现链表

实现链表的基本结构

链表由节点（Node）组成，每个节点包含数据（value）和指向下一个节点的指针（next）。以下是基础链表的实现：

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

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

添加节点到链表末尾

使用 append 方法在链表末尾添加新节点。若链表为空，新节点成为头节点；否则遍历到链表末尾插入。

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++;
}

在指定位置插入节点

通过 insertAt 方法在特定索引处插入节点。需处理索引越界及头节点插入的特殊情况。

insertAt(value, index) {
  if (index < 0 || index > this.size) return false;
  const newNode = new Node(value);
  if (index === 0) {
    newNode.next = this.head;
    this.head = newNode;
  } else {
    let current = this.head;
    let prev = null;
    let i = 0;
    while (i < index) {
      prev = current;
      current = current.next;
      i++;
    }
    newNode.next = current;
    prev.next = newNode;
  }
  this.size++;
  return true;
}

删除指定位置的节点

removeFrom 方法根据索引删除节点。需处理头节点删除和中间节点删除的逻辑。

removeFrom(index) {
  if (index < 0 || index >= this.size) return null;
  let removedNode;
  if (index === 0) {
    removedNode = this.head;
    this.head = this.head.next;
  } else {
    let current = this.head;
    let prev = null;
    let i = 0;
    while (i < index) {
      prev = current;
      current = current.next;
      i++;
    }
    removedNode = current;
    prev.next = current.next;
  }
  this.size--;
  return removedNode.value;
}

查找节点值的位置

indexOf 方法返回给定值的首次出现索引，若未找到则返回 -1。

indexOf(value) {
  let current = this.head;
  let index = 0;
  while (current) {
    if (current.value === value) return index;
    current = current.next;
    index++;
  }
  return -1;
}

判断链表是否为空

通过 isEmpty 方法检查链表是否为空（即头节点是否为 null）。

isEmpty() {
  return this.size === 0;
}

获取链表长度

getSize 方法直接返回链表的 size 属性。

getSize() {
  return this.size;
}

打印链表内容

print 方法将链表所有节点的值拼接为字符串输出。

print() {
  let current = this.head;
  let str = "";
  while (current) {
    str += current.value + " -> ";
    current = current.next;
  }
  str += "null";
  console.log(str);
}

完整代码示例

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

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

  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++;
  }

  insertAt(value, index) {
    if (index < 0 || index > this.size) return false;
    const newNode = new Node(value);
    if (index === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let current = this.head;
      let prev = null;
      let i = 0;
      while (i < index) {
        prev = current;
        current = current.next;
        i++;
      }
      newNode.next = current;
      prev.next = newNode;
    }
    this.size++;
    return true;
  }

  removeFrom(index) {
    if (index < 0 || index >= this.size) return null;
    let removedNode;
    if (index === 0) {
      removedNode = this.head;
      this.head = this.head.next;
    } else {
      let current = this.head;
      let prev = null;
      let i = 0;
      while (i < index) {
        prev = current;
        current = current.next;
        i++;
      }
      removedNode = current;
      prev.next = current.next;
    }
    this.size--;
    return removedNode.value;
  }

  indexOf(value) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.value === value) return index;
      current = current.next;
      index++;
    }
    return -1;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  print() {
    let current = this.head;
    let str = "";
    while (current) {
      str += current.value + " -> ";
      current = current.next;
    }
    str += "null";
    console.log(str);
  }
}

// 使用示例
const list = new LinkedList();
list.append(10);
list.append(20);
list.insertAt(15, 1);
list.print(); // 输出: 10 -> 15 -> 20 -> null
console.log(list.removeFrom(1)); // 输出: 15
console.log(list.indexOf(20)); // 输出: 1