Как мне получить n-й элемент в LinkedList<T>?

Question

Как я могу получить n-й элемент экземпляра LinkedList? Есть ли встроенный способ или мне может потребоваться представить собственную реализацию? Например метод расширения?

Спасибо

Answer 1

ElementAt метод расширения сделает это:

// This is 0-based of course
var value = linkedList.ElementAt(n);

Не забывайте, что это операция O(n), потому что LinkedList<T> не предоставляет более эффективного способа доступа к элементу по индексу. Если вам нужно делать это регулярно, это предполагает, что вам не следует использовать связанный список для начала.

Answer 2

Вы можете использовать перечисляемый метод расширения ElementAt(). Причина, по которой LinkedList изначально не поддерживает произвольный доступ, заключается в том, что это довольно неэффективная операция для структуры данных. Если вы собираетесь делать это часто, вам следует подумать об использовании более подходящей структуры данных.

Answer 3

Мне нужно было получить второй элемент моего списка (чтобы обновить значение 1-го элемента на основе 2-го)

Предполагая, что вы предпринимаете необходимые шаги, чтобы убедиться, что у вас есть два элемента, вы можете просто сделать это:

list.First.Next.Value

Answer 4

Вы можете сделать это с помощью LINQ, как в list.ElementAt(n) или же list.Skip(n - 1).First(), но если вы делаете индексированный доступ в связанный список, вы, вероятно, делаете что-то не так (связанные списки не поддерживают эту операцию эффективно). Возможно, другая структура данных будет более подходящей?

Answer 5

Существует ПУТЬ более производительное решение - по крайней мере, в 3 раза быстрее в худшем случае. Доказательство:

//Test Name:    TestLinkedListElementAtStart
//Test Outcome: Passed
//Result StandardOutput:    
//0
//Total milliseconds: 48,24
//Total milliseconds: 4,7386
[TestMethod]
public void TestLinkedListElementAtStart()
{
    var l = new LinkedList<int>();
    for (int i = 0; i < 1000; i++) { l.AddLast(i); }
    Console.WriteLine(l.OptimizedElementAt(0));
    Performance.ConsoleWriteExecutionTime(() => l.ElementAt(0), 1000000);
    Performance.ConsoleWriteExecutionTime(() => l.OptimizedElementAt(0), 1000000);
}

//Test Name:    TestLinkedListElementAtMiddle
//Test Outcome: Passed
//Result StandardOutput:    
//500
//Total milliseconds: 2990,9241
//Total milliseconds: 730,9262
[TestMethod]
public void TestLinkedListElementAtMiddle()
{
    var l = new LinkedList<int>();
    for (int i = 0; i < 1000; i++) { l.AddLast(i); }
    Console.WriteLine(l.OptimizedElementAt(l.Count / 2));
    Performance.ConsoleWriteExecutionTime(() => l.ElementAt(l.Count / 2), 1000000);
    Performance.ConsoleWriteExecutionTime(() => l.OptimizedElementAt(l.Count / 2), 1000000);
}

//Test Name:    TestLinkedListElementAtEnd
//Test Outcome: Passed
//Result StandardOutput:    
//999
//Total milliseconds: 5942,9193
//Total milliseconds: 4,6877
[TestMethod]
public void TestLinkedListElementAtEnd()
{
    var l = new LinkedList<int>();
    for (int i = 0; i < 1000; i++) { l.AddLast(i); }
    Console.WriteLine(l.OptimizedElementAt(l.Count - 1));
    Performance.ConsoleWriteExecutionTime(() => l.ElementAt(l.Count - 1), 1000000);
    Performance.ConsoleWriteExecutionTime(() => l.OptimizedElementAt(l.Count - 1), 1000000);
}

Код является частной собственностью, поэтому я не могу поделиться, но просто зная, что это возможно, вы можете сделать математику.. буквально. Я также могу подумать о еще более быстром решении, если список используется в основном для чтения.