问题标签 [singly-linked-list]

我最近刚刚启动了一个项目，其中包含一些已经编写的代码。我决定研究他的实现，发现他实现了一个带有单链表的优先级队列。

我对 SLL 的理解是，由于您可能必须遍历整个列表，因此实现它的效率很低，这就是首选堆的原因。但是，也许我错过了它背后的某种推理，并且想知道是否有人曾经为优先队列选择 SLL 而不是堆？

我正在编写一个程序来模拟内存碎片。输入文件告诉什么时间段需要输入。

一个示例文件是：

whereC是内存大小，P是顺序中的段（大小，开始时间和寿命），并且R（应该）打印出一份报告，显示内存中的哪些段，任何孔以及在哪里。

这个赋值的规则之一是创建事件的链表，其中段的插入和删除被创建为事件，我需要遍历事件列表。更新：我有一些不同的东西，但我确定它不会将我的事件插入到事件列表中。我不明白为什么。有谁知道我的逻辑在哪里？

首先解释一下我正在尝试做的事情：

我的计划是编写一个使用 boost::asio 库实现的套接字流的程序，该库将数据馈送到使用 boost:spirit::qi 实现的解析器。解析器将获取数据包并填充数据包对象，然后将该对象附加到数据包对象链表的末尾。数据包处理器将读取列表中的第一个对象并进行处理，然后移动到下一个项目并删除第一个。

我决定使用链表，因为如果我使用 std::queue，每次流添加一个数据包或处理器删除一个数据包时，我都必须锁定整个容器，这会使两个线程或多或少串行运行，这我想避免。另外，队列类倾向于复制整个对象，而链表思想的好处是创建一次对象，然后只指向它。为了避免将整个业务序列化，我打算在每个节点中放置 boost:mutex 互斥锁并从那里锁定它们。这个想法是让套接字流创建列表并立即锁定第一个节点，从解析器填充节点，创建下一个节点并锁定它，然后解锁第一个节点并移动到下一个节点进行工作。这边有' s 永远不会有一个未锁定的节点悬垂在数据包处理器可能跳转到并在套接字流鼻子下删除的末尾。数据包处理器将检查第一个节点并尝试锁定它，如果它锁定它，那么它将进行处理然后解锁它，获取下一个节点然后删除第一个节点。这种方式序列化仅限于包处理器赶上套接字流类的那些时间。

所以现在我的问题是，在我开始实际实施之前，这听起来是个好主意吗？我已经在一个简单的测试中尝试过它，它似乎工作正常，只要我实现异常处理并注意释放我分配的任何内存，我想不出任何严重的问题，但如果有人能想到我忽略了这个想法的任何问题，我将不胜感激。另外，我将不胜感激任何其他人可能会提出的任何其他建议作为替代方案，或者可能会使这个想法更好地发挥作用。

提前致谢！

除非我遗漏了什么，否则SGIslist和 C++11在我看来都是一样的；std::forward_list两者都实现了单链表。

我认为这是有区别的，因为 C++ 标准委员会在将容器添加到 C++0x 标准库时没有采用名称 slist 而是选择了一个新名称 forward_list。

我在 C++ 中启动数据结构，在阅读时，我想到了以下片段，

谁能详细说明为什么作者选择一个结构而不是一个类来实现singly linked list？谢谢。

给定一个单链表，如何从指定节点（例如节点 4）确定头节点。节点总数：10。谢谢。逻辑会做，代码表示赞赏。

我们知道给定一个头节点，可以轻松执行前向遍历并确定下一个节点。

对于这种情况，使用双链表会更简单，但我想知道是否可以使用单链表来追踪头节点。谢谢。

我以为我在上一个关于链接列表的问题中对此有所了解，但我大错特错了，我就像我最初发布时一样迷茫。

我意识到我在技术上问了两个问题，但希望至少得到一个应该使另一个容易（假设它们只是彼此相反）。

我已经给我上了 3 节课，它们是：

SLinkedList.java

还有 Node.java

最后是 GameEntry.java

编辑点 我创建了一个名为Scores.java的驱动程序，到目前为止我所拥有的只是**我已经添加了我认为我需要的课程，但我可能错了：

我有一个名为 ScoresTest.java 的测试驱动程序，我已经填写了很多：

包项目_1；

导入第 3 章.linkedList.SLinkedList；

这已经完全完成了，我很确定我没有什么要补充的了。

我不是在找人来为我回答这个问题，但我不知道从哪里开始，也不知道如何以任何方式制作添加或删除功能。这是一门中级课程，这本书对解释链表没有任何作用（如果您不相信我，请自行查找，文本称为 Java 中的数据结构和算法，第 5 版）。它展示了如何很容易地使用数组来做到这一点......这对于链表来说非常有效，但显然老师不希望我们这样做，所以很遗憾我现在完全不知道如何做到这一点。

我试过在这里和谷歌上查看其他人的答案，到目前为止，没有任何点击或任何意义，我无法理解它是如何工作的，老师的解释和例子只是在上面画框董事会，我从未见过为链接列表编码的排序，添加或删除功能......不知道我没有被教导或找不到什么。

非常感谢任何帮助，并提前感谢您！

编辑

我查看了 import java.util.*; 以及其中用于链接列表的命令，它们看起来非常简单。要删除，我只需使用 list.sublist(i, i).clear(); 并且我希望删除的值被删除，超级简单，它似乎只是试图利用 slinkedlist.java 和 node.java，我似乎无法以任何方式遵循它们的形状或形式。我相信老师确实写了它们，我试过寻求他的帮助，课后呆了 2 个小时试图从他那里得到任何理解，正如你所见，它根本没有多大帮助。再次感谢您的帮助！

编辑

如果这看起来含糊不清，我也很抱歉，但我没有一个具体的点，我的困惑似乎是相关的，如果我们谈论的是 java.util.linkedList;，我理解链表，但至于使用什么在这种情况下给了我，我根本无法遵循逻辑，让我很迷茫，不知道从哪里开始。

我正在为一个提供 SinglyLinkedList 类的学校做作业，我们应该创建一个程序来调用这个类来添加、删除、查找和显示列表中的项目。我已经很好地实现了添加、删除和显示方法，但我不知道如何调用 find 方法。任何帮助都会很棒。

这是我需要实现的 SingleLinked 类的方法：

}

这就是我所拥有的......我还包括了其他方法的实现：

我确信我会踢自己，因为它比我做的简单，但我真的只是卡住了。

是否有可能找到一个元素（例如，一个整数）的最后一次出现并删除这个节点，只需要一次（前向）遍历列表？

似乎添加了第一个 mapList 节点，然后添加了它之后的节点，但是之后添加的每个节点每次都被放置在第三个位置，即使看起来我的 *next 设置正确（我还是新的at 指针和 C) 当我想访问更多节点时，这导致了我的分段错误。我已经让patronNode添加了工作，这要复杂得多，我似乎无法正确处理这个问题，而那些输出只是对我吐口水=（

这是两个结构..

这是添加功能

这是我的输出的样子：

使用 KEY = Orson Scott Card 输入添加节点

ENTERING ADDMAPNODE WITH KEY = Frank Herbert - 在 Orson Scott Card 之后添加密钥 - 添加 Frank Herbert

ENTERING ADDMAPNODE WITH KEY = Isaac Asimov - 当前密钥是 Orson Scott Card - 在 Frank Herbert 之后添加一个密钥 - 添加了 Isaac Asimov

ENTERING ADDMAPNODE WITH KEY = Douglas Adams - 当前密钥是 Orson Scott Card - 在 Frank Herbert 之后添加一个密钥 - 添加 Douglas Adams

ENTERING ADDMAPNODE WITH KEY = George Orwell - 当前密钥是 Orson Scott Card - 在 Frank Herbert 之后添加一个密钥 - 添加 George Orwell

ENTERING ADDMAPNODE WITH KEY = Robert A. Heinlein - 当前密钥是 Orson Scott Card - 在 Frank Herbert 之后添加一个密钥 - 添加了 Robert A. Heinlein

ENTERING ADDMAPNODE WITH KEY = Ray Bradbury - 当前密钥是 Orson Scott Card - 在 Frank Herbert 之后添加密钥 - 添加 Ray Bradbury

等....在 Frank Herbert 之后添加了每个键，因为代码认为 Herbert's->next 为 NULL，即使我只是将它设置为 = 到一个新节点... CONFIZZZLED