了解链接列表

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）时间或线性，其中n是列表中的项目数。

因此，从高效的角度来看，添加到列表的头部会好很多。