当前位置：首页 > JavaScript

链表js实现

2026-03-14 05:01:59JavaScript

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针（或引用）。与数组不同，链表在内存中是非连续存储的，插入和删除操作更高效，但随机访问效率较低。

链表的实现步骤

定义节点类

每个节点包含数据（value）和指向下一个节点的指针（next），初始时next为null。

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

初始化链表

创建头节点（head）并初始化，头节点可以为空或包含数据。

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0; // 可选：记录链表长度
  }
}

插入节点

在链表尾部插入节点
遍历链表找到最后一个节点，将新节点链接到其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.size++;
}

在链表头部插入节点
将新节点的next指向原头节点，并更新头节点为新节点。

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

删除节点

删除指定值的节点
遍历链表找到目标节点的前驱节点，修改其next指针跳过目标节点。

delete(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;
}

打印链表

将链表转换为数组或字符串输出。

链表js实现

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

完整代码示例

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

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 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.size++;
  }

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

  delete(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.delete(1);
list.print(); // 输出: 0 -> 2
console.log(list.contains(2)); // 输出: true