双向链表

双向链表是另一种数据结构，它允许你从每个列表项向前和向后导航。

它可以通过添加第二个指针（即指向前一个元素）来基于单向链表创建。

想象一下双向链表

如果你想更好地想象一个双向链表，打开一个文本编辑器并开始在其中描述你的日子。每当你犯了一个错误，你按下“撤销”按钮，你就会看到更早的版本。你也可以按下“重做”，突然之间，你看到了文档中在你撤销更改之前的内容。当然，你可以多次执行这样的操作，系统会记住许多之前的和接下来的操作。这就是你可以想象双向链表的方式。在列表的每个元素中，你可以轻松地访问下一个元素（相当于“重做”操作）和前一个元素（相当于“后退”操作）。看看在日常生活中为各种数据结构找到应用是多么容易吧！

以下图形展示了双向链表：

正如你所见，第一个框指示列表中的第一个元素。每个项目都有两个属性，分别指向前一个和下一个元素（分别为PREV和NEXT）。如果没有前一个元素，PREV属性等于null。同样，当没有下一个元素时，NEXT属性设置为null。此外，双向链表包含最后一个框，指示最后一个元素。如果你想在你的基于C#的应用程序中使用它，你需要自己实现这样的数据结构吗？幸运的是，不需要！它已经作为LinkedList泛型类在System.Collections.Generic命名空间中可用。创建此类的实例时，你需要指定类型参数，该参数指示列表中每个元素存储的值的类型，例如int或string。每个元素（也称为节点）由LinkedListNode泛型类的实例表示，例如LinkedListNode<int>或LinkedListNode<string>。

对于向双向链表添加新节点的方法，需要一些额外的解释。为此，你可以使用一组方法：

? AddFirst在列表的开头添加一个元素

? AddLast在列表的末尾添加一个元素

? AddBefore在列表中指定节点之前添加一个元素

? AddAfter在列表中指定节点之后添加一个元素

所有这些方法都返回LinkedListNode类的实例。此外，还有一些其他方法：

? Contains检查指定的值是否存在于列表中

? Remove从列表中移除一个节点

? Clear从列表中移除所有元素

在这简短的介绍之后，让我们来看一个例子，它展示了如何在实践中应用作为LinkedList类实现的双向链表。

示例 - 电子书阅读器

以一个简单的应用程序为例，它允许用户通过翻页来阅读一本书。用户在按下N键后应该能够翻到下一页（如果存在的话），在按下P键后应该能够回到上一页（如果存在的话）。当前页面的内容以及页码应该在控制台中显示，如截图所示:

让我们从页面记录的声明开始，如下代码所示：

这个记录代表一个单独的页面，并包含Content属性。然后，你创建了几个Page类的实例，代表书的六页：

当实例被创建后，你可以使用一些与添加相关的函数来构建双向链表，如下列代码所示：

在第一行，创建了一个新的空列表。然后执行给定的操作：

1. 在末尾添加第二页 ([2])。

2. 在末尾添加第四页 ([2, 4])。

3. 在末尾添加第六页 ([2, 4, 6])。

4. 在列表开头添加第一页 ([1, 2, 4, 6])。

5. 在第四页前添加第三页 ([1, 2, 3, 4, 6])。

6. 在第四页后添加第五页 ([1, 2, 3, 4, 5, 6])。

代码的下一部分负责在控制台中呈现页面，以及在按下适当的键后在页面之间导航。代码如下：

在第一行中，变量c的值被设置为双向链表中的第一个节点。通常来说，变量c代表当前在控制台中显示的页面。然后，页面编号的初始值被设置为1（即number变量）。然而，代码中最有趣和复杂部分出现在while循环中。

在循环内部，控制台的当前内容被清除，并且用于显示页面编号的字符串被正确格式化以显示。在它前后添加了"-"字符。此外，使用PadLeft方法插入了前导空格，以准备横向居中的字符串。

然后，页面的内容被分割成不超过90个字符的行，并写入控制台。为了分割字符串，使用了Length属性和范围操作符，例如在content[i..]中。同样，在控制台中展示了额外的信息。如果存在上一页或下一页，则显示"PREV"和"NEXT"标题。

你可以改进这个例子吗？

这个例子在不考虑空格的情况下将文本分成几行。我鼓励你修改代码，使其支持更友好的文本换行。祝你好运！

在代码的下一部分中，程序等待用户按下任何键，并且不将其显示在控制台中（通过将true作为ReadKey方法的参数传递）。当用户按下N键时，使用Next属性将变量c设置为下一个节点。当然，如果下一页不可用，不应执行此操作。P键的处理方式类似，它会导致用户导航到上一页。值得一提的是，页面编号（number变量）在更改c变量的值时也会被修改。

最后，辅助方法GetSpaces的代码如下所示：

这段代码准备并返回一个具有指定数量空格的字符串变量。当然，完成这个任务有几种方法。然而，在这本书中，我想向你展示各种方法，包括那些不那么典型的。目的是向你展示实现目标的多种方式，并尽可能拓宽你的视野。

有了这个，你应该准备好继续你的关于列表的冒险了。在下一节中，你将学习到循环列表及其两个子类型。