编写一个函数，实现一个简单的链表 (Linked List)

推荐答案

// www.javascriptcn.com code example
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

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

  // 添加节点到链表末尾
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // 在链表头部添加节点
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
  }

  // 删除指定数据的节点
  delete(data) {
    if (!this.head) {
      return;
    }
    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }

  // 查找节点
  find(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) {
        return current;
      }
      current = current.next;
    }
    return null;
  }

  // 打印链表
  print() {
    let current = this.head;
    let result = [];
    while (current) {
      result.push(current.data);
      current = current.next;
    }
    console.log(result.join(' -> '));
  }
}

// 示例用法
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.print(); // 输出: 0 -> 1 -> 2 -> 3
list.delete(2);
list.print(); // 输出: 0 -> 1 -> 3
console.log(list.find(1)); // 输出: Node { data: 1, next: Node { data: 3, next: null } }

本题详细解读

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的特点是插入和删除操作效率高，但访问元素的效率较低。

代码结构

1. Node类：表示链表中的一个节点，包含data和next两个属性。data存储节点的数据，next指向下一个节点。
2. LinkedList类：表示链表本身，包含head属性，指向链表的第一个节点。
   • append(data)：在链表末尾添加一个新节点。
   • prepend(data)：在链表头部添加一个新节点。
   • delete(data)：删除链表中第一个匹配指定数据的节点。
   • find(data)：查找链表中第一个匹配指定数据的节点并返回。
   • print()：打印链表中的所有节点数据。

关键点解析

• append方法：从链表头部开始遍历，直到找到最后一个节点，然后将新节点添加到末尾。
• prepend方法：直接将新节点的next指向当前的头节点，然后更新头节点为新节点。
• delete方法：遍历链表，找到匹配的节点后，将其前一个节点的next指向匹配节点的下一个节点，从而跳过匹配节点。
• find方法：遍历链表，返回第一个匹配的节点。
• print方法：遍历链表，将所有节点的数据拼接成字符串并打印。

时间复杂度

• append：O(n)，需要遍历到链表末尾。
• prepend：O(1)，直接在头部插入。
• delete：O(n)，需要遍历链表找到匹配节点。
• find：O(n)，需要遍历链表找到匹配节点。
• print：O(n)，需要遍历整个链表。

适用场景

链表适用于频繁插入和删除操作的场景，如实现队列、栈等数据结构。