js实现单向链表

单向链表的基本概念

单向链表是一种线性数据结构，由多个节点组成，每个节点包含两部分：

• 数据域（value）：存储实际数据。
• 指针域（next）：指向下一个节点的引用（最后一个节点指向 null）。

实现单向链表的步骤

定义节点类

使用 class 或构造函数定义链表节点，包含 value 和 next 属性：

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

初始化链表

创建链表类，初始化头节点和链表长度：

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

实现常用方法

1. 添加节点（尾部）
遍历链表至末尾，将新节点连接到最后一个节点的 next：

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

2. 插入节点（指定位置）
在指定索引处插入节点，更新相邻节点的指针：

insert(index, value) {
  if (index < 0 || index > this.length) return false;
  const newNode = new ListNode(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;
    }
    newNode.next = current;
    prev.next = newNode;
  }
  this.length++;
  return true;
}

3. 删除节点
根据索引删除节点，调整前后节点的指针：

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

4. 查找节点
根据值返回节点索引，未找到返回 -1：

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

5. 获取链表长度
直接返回 length 属性：

size() {
  return this.length;
}

完整代码示例

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

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

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

  insert(index, value) {
    if (index < 0 || index > this.length) return false;
    const newNode = new ListNode(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;
      }
      newNode.next = current;
      prev.next = newNode;
    }
    this.length++;
    return true;
  }

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

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

  size() {
    return this.length;
  }
}

使用示例

const list = new LinkedList();
list.append(10);
list.append(20);
list.insert(1, 15);
console.log(list.indexOf(15)); // 输出: 1
list.removeAt(1);
console.log(list.size());      // 输出: 2

通过以上实现，可以完成单向链表的基本操作，包括增删查改和长度获取。