链表、队列和堆栈 - 数据结构与算法 第一部分

学习概念以及如何实现链表、队列和堆栈。

欢迎阅读我的第一篇文章，我将在这里讨论数据结构。我非常兴奋能写这个系列！这篇文章被拖延了很久，原因有很多，也许我可以改天再写，但最终我决定完成这个目标。

在这里，我将解释这个主题的重要性，以及为什么你应该理解所有概念。在我看来，了解这些概念及其背后的工作原理至关重要，尽管许多框架已经拥有完整的实现。但相信我，这对你的职业生涯至关重要，也许你将来会用到它来解决一些问题。👨‍💻👩‍💻

这里我们将用 JavaScript 示例进行简短的讨论，我会从头开始，循序渐进，因为我们不必着急！所以，让我们一起探索数据结构和算法这个奇妙的世界吧。😀

💭 “糟糕的程序员担心代码。优秀的程序员担心数据结构及其关系。”—— Linus Torvalds

大纲

• 关于单链表、双链表和循环链表的讨论。
• 什么是队列和堆栈？
• 术语。
• 何时何地使用？
• 代码实现和复杂度分析。

什么是链表？

在开始讨论之前，我们需要清楚地理解链表的含义。链表是一种集合结构，表示一系列节点。但是，等等！✋ 节点是什么意思？🤔 一个包含值和指针的对象，该指针指向链表的序列，用于存储下一个元素的地址，如下图所示：

图 1：链表表示。

实际上，你可以把指针想象成一个指向内存中某个位置的引用，用来查找和获取节点中存储的值。列表中的第一个节点代表头节点，它指向下一个元素；而最后一个节点代表尾节点，因为它指向下一个节点的空指针。

您还可以使用指向前一个对象的指针。这样就创建了一个双向链表类型。

理解链表的另一个重要方面与高效的内存利用率有关。链表无需预先分配内存，因此您可以在链表中添加任意数量的项。但是，如果所需的内存超出了链表的可用容量，则可能会出现一些问题，因为每个节点都拥有一个指针和其他内存空间。

术语

正如您在上图中所看到的，我们定义了两个属性：

• 值：保存数据的元素。
• next：指向下一个节点。

• prev（可选）：可用于指向上一个节点。更多信息请参阅双向链表结构。

让我们开始吧！ 

既然我们已经对概念有了共识，那就让我们更深入地讨论链表的方法，将这些概念转化为代码，并最终实现我们的数据结构。首先，我们将重点介绍链表，因为它是最常见、最简单的数据结构——数据元素的线性集合。
 
让我们开始动手吧！😃

◼️ 单链表

之所以称为单独节点，是因为一个节点仅保存对序列中下一个元素的引用，并且您无法访问前面的元素，因为它不存储任何指针或对前一个节点的引用，如图所示。

图 2：包含一个元素和指向下一个节点的指针的单链表

在描述操作之前，我们需要定义代码中最重要的部分，它将帮助我们构建线性列表结构，即节点类。

class Node {
   constructor(value, next) {
      this.value = value;
      this.next = next;
   }
}

我们的主类只包含对值和下一个节点的引用，很简单吧？那么，让我们继续定义链表类，它有一个 head 属性，指向链表的第一个元素；另一个需要声明的属性是 size，它指明了链表中存在的节点数。

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

好的，继续讨论，我们必须为类添加方法。让我们来看看：

• addAtHead：我们的第一个方法用于在数据结构的开头添加一个新元素。此方法的运行时间是常数（O(1)）。但这意味着什么呢？🧐 这意味着在列表中添加一个值所需的时间相同，是一个常数时间。在这种情况下，只需移动一次即可将新元素添加到列表的第一个位置。因此，我们只需要更新指向我们将要创建的新项目的当前头。具体如下：

addAtHead(value){
   if(linkedList.head){
      var newNode = new Node(value, this.head );
      this.head = newNode;
   }else{
      var newNode = new Node(value, null);
      this.head = newNode;
   }
   this.length++;
}

• removeAtHead：如果我们想从头部移除一个元素，只需用其后的元素替换头部即可。与之前的方法类似，其运行时间为 O(1)。

removeAtHead(value){
    if(this.head){
       var newHead = this.head.next;
       this.head = newHead;
       this.length--;
    }else{
       return false;
    }
}

• 搜索：如果我们要查找某个特定项？不必着急；我们只需遍历列表直到末尾即可找到该元素。但想象一下以下场景：我们有一个包含 1000 个项的列表，我们正在寻找第 999 个项。你能猜到会发生什么吗？如果我们想获取位置 N 处的某个特定值或节点，那么我们必须移动指针遍历整个列表才能找到它。这可能会导致访问时间问题。

    search(value){
        if(this.head){
            var node = this.head;
            var count = 0;
            while(node != null && node.value != value){
                if(count >= this.length && node.value != value){
                    return false;
                }
                node = node.next;
                count++;
            }
            if(node == null){
                return false;
            }else{
                return true;
            }
        }else{
            return false;
        }
    }

我还想讨论其他函数，例如getAtIndex、addAtIndex、removeAt和reverse，但它们的逻辑与之前描述的方法类似，因此我将跳过对它们的解释，以免浪费您的时间。

⚡️但是如果您想知道我是如何实现的，您只需单击此处即可访问 所有代码。__

◼️ 双向链表

正如我之前提到的，双向链表是一种能够指向前一个节点的结构，这是它与单链表最大的区别。现在，我们可以在列表中向后移动。例如，每个节点都有一个指向前一个元素的指针，这样你就可以从尾部开始遍历列表，如下图所示。

正如本叔叔对彼得·帕克所说：“能力越大，责任越大。” 因此，需要更多的空间来存储列表中前一个元素的地址，而不是仅仅存储下一个元素的地址，因此与单个结构相比，需要多占用两倍的内存空间。

除此之外，几乎所有功能和行为都与单链表非常相似。只要对链表有基本的了解，构建和扩展功能使其成为双链表就非常容易了。是不是很简单？😁 你能感觉到我们正在取得进展。💪

图 3：带有指向前一个元素的指针的双向链表

尽管行为相似，但我们需要更新单列表函数，例如addAtHead、removeAtHead、search等，以考虑先前的属性。除了这些函数之外，我们还有新的武器可以使用，如下所示：

• addAtTail：我们在列表底部定义一个新元素，并将最后一个元素指向尾部。你能想象这恒定的运行时间吗？

    addAtTail(value){
        var newNode = new Node(value, null, this.tail);
        if(this.tail){
            this.tail.next = newNode;
            this.tail = newNode;
        }else{
            this.head = newNode;
            this.tail = newNode;
        }
        this.length++;
    }

• removeAtTail：此处将列表中的最后一项设置为空值。因此，最后一个元素将成为最后一个元素的前一个元素。

    removeAtTail(){
        if(this.length === 1){
            this.removeAtHead();
            this.tail = null;
            return;
        } else if (this.length > 1){
            this.tail = this.tail.prev;
            this.tail.next = null;
            this.length--;
            return;
        }
        return false;
    }

◼️ 循环链表

双向链表与双向链表的唯一区别在于，链表的尾部元素与链表的第一个元素相连。这样就形成了一个循环，现在我们可以在整个链表中前后移动。

图 4：包含第一个和最后一个元素之间的链接的循环链表。

现在我们将使用所学的全部知识来实现​​两个新的数据结构。

◼️ 队列

先进先出 (FIFO) 是一种线性数据结构，其中第一个添加到队列的元素将最先被移除。例如，你可以想象一下在商店、银行或超市排队时的这种行为。

🚶♂️🏦🚶♀️🚶♂️🚶♀️🚶♂️

入队 (addFromTail) 函数将新元素添加到列表末尾，出队 (removeFromTail) 函数则将新元素从列表顶部移除。您可以看到其他人或在书中提到队列作为移除或轮询方法，但我更喜欢出队。此结构中另一个常见的操作是 Peek，它会将堆栈顶部的项目作为 Peek 返回。

但是，什么时候应该使用这些结构化数据呢？🤔 当顺序很重要时，建议使用队列，就像请求的排队系统一样。

图 5：队列的表示。

◼️ 堆栈

被称为 LIFO（后进先出）数据结构，您可以直观地了解它的工作原理，就像将一组物品堆叠在一起形成一堆书一样。

正如我之前所说，这种结构与链表有一些相似之处，你可以在栈结构中使用 addFromTail (Push) 和 removeFromTail (Pop) 操作。与队列类似，返回栈顶元素的操作称为 peek。

您可以在文本编辑器、编译器语法检查或图表中的机制中找到此结构。

图 6：堆栈的表示以及 Push 和 Pop 函数。

◼️时间复杂度

您可以在下图中看到时间复杂度，其中 n 是链表的长度。

图 7：时间复杂度。

让我们创建一个示例，在头部添加一些值，然后使用 addAtHead 和 removeAtHead 函数从链表中移除它们。此外，使用 JavaScript 中的 time() 对象可以让我们计时并分析代码的性能，如下图所示：

图 8：在单链表中插入和删除一些值后的输出。

如您所见，我们在列表中添加了一些值，以显示执行速度。通过观察这些值，我们可以发现执行时间变成了一个常数。下图展示了使用 Python 和 Panda DataFrame 库绘制的图表。

图 9：addAtHead 和 removeAtHead 函数之间的消耗时间。

我们完成了🙌

◼️ 就是这样！

总结我们的简短讨论，我们了解到链表是一种最简单、最动态的数据结构，可用于实现其他结构，如队列和堆栈。

你可以使用这些结构来执行大量的插入和删除操作。由于我们只需要更新节点中的下一个指针，因此运行速度很快。但是，如果我们想要获取位置 N 处的某个特定值或节点，并且列表较长，则可能会出现访问时间问题。

另一个重要因素是高效的内存利用率，无需预先分配内存。然而，如果您需要更多空间，则可能会出现与连续内存块相关的问题。

就这样吧，伙计们！

代码：https://github.com/FernandoBLima/data-structures

| 下一个（即将推出）>

这样我们就完成了关于链表、队列和堆栈数据结构的讨论。🙌

希望你对如何操作有了清晰的认识。如果你觉得这篇文章对你有帮助，或者你发现我遗漏了什么，或者你喜欢其中的内容，欢迎随时告诉我并订阅我！ 😁