实现单链表

假设理解 Big O 表示法。 JavaScript 中有示例。资料参考 Gayle Laakmann McDowell 的《Cracking the Coding Interview》

理解单链表

链表是一种表示节点序列的数据结构。在单链表中，每个节点都指向下一个节点。

在内存中，这些节点不需要连续排序（彼此相邻），因为我们不依赖索引。当我们迭代链表时，我们会遍历节点的每个引用，直到遇到null指针。

节点的结构

在单链表中，每个节点通常包含两个字段：

• data：节点
中包含的值或信息
• next：列表中下一个节点的引用（指针）

头尾指针

head 是对列表中第一个节点的 引用。它很重要，因为它允许访问链表的开头。它有时充当哨兵节点（放置在实际头节点之前），以便更轻松地进行操作，例如在头部插入。尾部是对列表中最后一个节点的引用。它的下一个指针为空，表示列表的末尾。

插入/删除的内存效率

与数组相比，链表在插入/删除方面具有更高的内存效率，因为这些操作不需要“移动”元素。从链表中的任意位置添加或删除元素的操作需要 $O(1)$O(1) 时间。然而，这需要 $O(n)$O(n) 最坏情况下遍历链表然后添加/删除元素的时间（不适用于添加/删除第一个元素）。

值得指出的是，由于每个节点中都存储了指针和数据，因此链表会产生额外的内存开销。

时间复杂度分析

插入：

• 在开始或结束处（带有头/尾指针）→ $O(1)$O(1)
• 在特定位置（由于遍历）→ $O(n)$O(n)

删除：

• 开始→ $O(1)$O(1)
• 最后→ $O(n)$O(n)
• 在特定位置→ $O(n)$O(n)

遍历/搜索： $O(n)$O(n)

JavaScript 实现

经典面向对象编程

class ListNode {
    constructor(val, nextNode = null) {
        this.val = val;
        this.next = nextNode;
    }
}

class LinkedList {
    constructor() {
        // sentinel node for easy operations on head
        this.head = new ListNode(-1);
        this.tail = this.head;
    }

    // get the value at the specified index.
    get(index) {
        let curr = this.head.next;
        let i = 0;
        while (curr !== null) {
            if (i === index) return curr.val;
            curr = curr.next;
            i++;
        }
        return -1;
    }

    // insert a new value at the head of the list.
    insertHead(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head.next;
        this.head.next = newNode;
        if (newNode.next === null) {
            this.tail = newNode;
        }
    }

    // insert a new value at the tail of the list.
    insertTail(val) {
        const newNode = new ListNode(val);
        this.tail.next = newNode;
        this.tail = newNode;
    }

    // remove the node at the specified index.
    remove(index) {
        let curr = this.head;
        let i = 0;
        while (i < index && curr.next !== null) {
            i++;
            curr = curr.next;
        }

        if (curr !== null && curr.next !== null) {
            if (curr.next === this.tail) this.tail = curr;
            curr.next = curr.next.next;
            return true;
        }
        return false;
    }

    // get all values in the list as an array.
    getValues() {
        const values = [];
        let curr = this.head.next;
        while (curr !== null) {
            values.push(curr.val);
            curr = curr.next;
        }
        return values;
    }

    // get the length of the list.
    length() {
        let length = 0;
        let curr = this.head.next;
        while (curr !== null) {
            length++;
            curr = curr.next;
        }
        return length;
    }
}

函数式面向对象编程

function ListNode(val, nextNode = null) {
    this.val = val;
    this.next = nextNode;
}

function LinkedList() {
    this.head = new ListNode(-1); // Sentinel node
    this.tail = this.head;
}

// get the value at the specified index
LinkedList.prototype.get = function(index) {
    let curr = this.head.next;
    let i = 0;
    while (curr !== null) {
        if (i === index) return curr.val;
        curr = curr.next;
        i++;
    }
    return -1;
};

// insert a new value at the head of the list
LinkedList.prototype.insertHead = function(val) {
    const newNode = new ListNode(val);
    newNode.next = this.head.next;
    this.head.next = newNode;
    if (newNode.next === null) {
        this.tail = newNode;
    }
};

// insert a new value at the tail of the list
LinkedList.prototype.insertTail = function(val) {
    const newNode = new ListNode(val);
    this.tail.next = newNode;
    this.tail = newNode;
};

// remove the node at the specified index
LinkedList.prototype.remove = function(index) {
    let curr = this.head;
    let i = 0;
    while (i < index && curr.next !== null) {
        i++;
        curr = curr.next;
    }

    if (curr !== null && curr.next !== null) {
        if (curr.next === this.tail) this.tail = curr;
        curr.next = curr.next.next;
        return true;
    }
    return false;
};

// get all values in the list as an array
LinkedList.prototype.getValues = function() {
    const values = [];
    let curr = this.head.next;
    while (curr !== null) {
        values.push(curr.val);
        curr = curr.next;
    }
    return values;
};

// get the length of the list
LinkedList.prototype.length = function() {
    let length = 0;
    let curr = this.head.next;
    while (curr !== null) {
        length++;
        curr = curr.next;
    }
    return length;
};

以上是实现单链表的详细内容。更多信息请关注PHP中文网其他相关文章！