Понимание связанного списка

Question

Этот код используется как example как обычный.

// type parameter T in angle brackets 
public class GenericList<T> 
{ 
    // The nested class is also generic on T 
    private class Node 
    { 
     // T used in non-generic constructor 
     public Node(T t) 
     { 
      next = null; 
      data = t; 
     } 

     private Node next; 
     public Node Next 
     { 
      get { return next; } 
      set { next = value; } 
     } 

     // T as private member data type 
     private T data; 

     // T as return type of property 
     public T Data 
     { 
      get { return data; } 
      set { data = value; } 
     } 
    } 

    private Node head; 

    // constructor 
    public GenericList() 
    { 
     head = null; 
    } 

    // T as method parameter type: 
    public void AddHead(T t) 
    { 
     Node n = new Node(t); 
     n.Next = head; 
     head = n; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     Node current = head; 

     while (current != null) 
     { 
      yield return current.Data; 
      current = current.Next; 
     } 
    } 
} 

У меня возникли проблемы выяснить, несколько строк, а именно это:

Node n = new Node(t); 
n.Next = head; 
head = n; 

Для меня это выглядит, как вы создаете новый экземпляр узла с некоторым аргументом данных затем установить его на следующий узел в связанном списке (я думаю, что имеет смысл быть предыдущим), а затем назначает этот узел в голову, что для меня бессмысленно.

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

Answer 1

Это добавление нового узла в начало списка. Новый узел имеет «следующий» указатель, установленный на старый заголовок, а затем новый узел устанавливается как новый текущий заголовок списка.

Другими словами, если вы начинаете с ...

C -> B -> A 

^ head of list 

затем ветер с ...

D -> C -> B -> A 

^ new head of list, and D.next points to C. 

Answer 2

Ее добавление элемента к перед списка.

псевдо-код:

make new node n out of t. 
n's next node is the current head. 
the new head of the list is n. 

Answer 3

Как и все остальные сказали, это добавление элемента в начало списка. Зачем? Поскольку добавление элемента в начало списка занимает одно и то же время, независимо от того, сколько элементов в списке, следовательно, это O (1) (или постоянное) время.

Если вы добавляли к ХВОСТУ списка, вам нужно будет просмотреть первый элемент, найти следующий элемент, проверить его следующий элемент и повторить до тех пор, пока не попадете в элемент без следующего элемента (т.е. его атрибут next равен нулю). Это O (n) time или linear, где n - количество элементов в списке.

Таким образом, с эффективной точки зрения добавление в начало списка намного лучше.