JavaScript 单链表

单链表是一种常见的数据结构，它由一系列节点组成，每个节点存储一个元素和指向列表中下一个节点的引用。单链表的一个重要特点是只能从头部开始遍历，并且插入和删除操作相对简单。

节点(Node)设计

首先，我们需要定义链表中的基本单元——节点。每个节点需要保存数据和指向下一个节点的引用。

class Node {
    constructor(data, next = null) {
        this.data = data; // 存储数据
        this.next = next; // 指向下一个节点
    }
}

链表类(List)设计

接下来，我们创建一个链表类，该类将包含用于管理链表的基本方法，如插入、删除、查找等。

初始化链表

初始化链表时，我们通常会设置一个空头节点，这有助于简化插入和删除操作。

class LinkedList {
    constructor() {
        this.head = null; // 初始头节点为空
    }
}

插入节点

在链表中插入节点是一个常见操作。我们可以在链表的尾部插入节点，也可以根据索引插入。

在链表尾部插入节点

// www.javascriptcn.com code example
insertAtTail(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;
}

根据索引插入节点

// www.javascriptcn.com code example
insertAtIndex(index, data) {
    if (index < 0) throw new Error('Index must be non-negative');

    const newNode = new Node(data);

    if (index === 0) {
        newNode.next = this.head;
        this.head = newNode;
        return;
    }

    let current = this.head;
    let position = 0;

    while (position < index - 1 && current.next) {
        current = current.next;
        position++;
    }

    if (position === index - 1) {
        newNode.next = current.next;
        current.next = newNode;
    } else {
        throw new Error('Index out of bounds');
    }
}

删除节点

删除节点是另一个重要的操作。我们可以根据值或索引来删除节点。

根据值删除节点

// www.javascriptcn.com code example
deleteByValue(value) {
    if (!this.head) return;

    if (this.head.data === value) {
        this.head = this.head.next;
        return;
    }

    let current = this.head;
    while (current.next && current.next.data !== value) {
        current = current.next;
    }

    if (current.next) {
        current.next = current.next.next;
    }
}

根据索引删除节点

// www.javascriptcn.com code example
deleteAtIndex(index) {
    if (index < 0) throw new Error('Index must be non-negative');

    if (!this.head) throw new Error('List is empty');

    if (index === 0) {
        this.head = this.head.next;
        return;
    }

    let current = this.head;
    let position = 0;

    while (position < index - 1 && current.next) {
        current = current.next;
        position++;
    }

    if (position === index - 1 && current.next) {
        current.next = current.next.next;
    } else {
        throw new Error('Index out of bounds');
    }
}

查找节点

查找节点可以根据值或索引进行。

根据值查找节点

// www.javascriptcn.com code example
findNodeByValue(value) {
    let current = this.head;
    while (current) {
        if (current.data === value) {
            return current;
        }
        current = current.next;
    }
    return null;
}

根据索引查找节点

// www.javascriptcn.com code example
findNodeAtIndex(index) {
    if (index < 0) throw new Error('Index must be non-negative');

    let current = this.head;
    let position = 0;

    while (current && position < index) {
        current = current.next;
        position++;
    }

    return current || null;
}

总结

通过上述代码，我们已经实现了一个基本的单链表类，包括节点的创建、链表的插入、删除、查找等操作。这些基础功能为更复杂的链表操作提供了良好的起点。在实际应用中，根据需求可以进一步扩展链表的功能，例如反转链表、合并链表等。

以上就是关于JavaScript单链表的详细介绍，希望对大家有所帮助。