C#中向现有的LinkedList<T>添加新项的最佳方法是什么？

Question

我正在尝试在现有的链表中添加新电影名称，但出现了错误。

cannot convert from 'string' to 'System.Collections.Generic.LinkedListNode<string>'

这是我正在处理的代码:

 LinkedList<string>  movies = new LinkedList<string>();
       movies.AddLast("Fire & Dew");
       movies.AddLast("Hang Break");
       movies.AddLast("Naughty Monkey");
       movies.AddLast("Sabotage");  

     //Add movie name Good & Bad After Hang Break
     movies.AddAfter("Hang Break", "Good & Bad");

        foreach (string movie in movies)
       {
           Console.WriteLine(movie);
       }    

有什么解决方案和代码提示吗？

- user8038996

---

双向链表中的每个元素都需要引用其前一个和后一个元素。您需要创建一个单独的类型来封装该元素。该类型是LinkedListNode<T>。 - user5245248

你使用链表而不是其他集合类型有什么特别的原因吗？ - DigiFriend

规则 #1：永远不要使用 LinkedList。规则 #2：正确使用，AddAfter() 需要一个节点，而不是一个字符串。如果用字符串来实现，会比现在更糟糕，因为你需要再次遍历集合来找到节点。请使用 List<> 替代。 - Hans Passant

链表提供了一种备选集合，可以在需要频繁添加或删除集合项的情况下获得更好的性能。 - user5245248

这是一个非常常见的误解。找到链表中插入点的成本比在列表中插入元素更高。LinkedList 对现代处理器非常不友好，它具有非常差的缓存局部性。只有在不丢失节点引用的情况下才能保持领先，这实际上是 OP 忘记做的事情。 - Hans Passant

Answer 1

好的，AddAfter 的 类型签名 是：

public LinkedListNode<T> AddAfter(<b>LinkedListNode<T> node</b>, T value)

因此，第一个参数node应该是一个LinkedListNode<T>。您可以获取该节点，因为它是从AddLast方法返回的：

movies.AddLast("Fire & Dew");
<b>var hang_break = </b>movies.AddLast("Hang Break");
movies.AddLast("Naughty Monkey");
movies.AddLast("Sabotage");  

//Add movie name Good & Bad After Hang Break
movies.AddAfter(<b>hang_break</b>, "Good & Bad");

在我们使用 csharp 交互式命令行评估这段代码后，我们会得到:

csharp> movies
{ "Fire & Dew", "Hang Break", "Good & Bad", "Naughty Monkey", "Sabotage" }

这是必要的原因是因为这样的链表允许在O(1)时间内插入给定节点旁边，因为它修改了下一个和前一个节点的引用。这可以做到，因为它只需要改变给定节点和给定节点旁边的节点。但是，如果您需要先搜索节点，则算法的复杂度为O(n)，因此链表的性能优势将会丧失。

- Willem Van Onsem