瞭解鏈接列表

下面的代碼被用作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;

對我來說，它看起來像你正在創建節點的新實例，一些數據參數，然後將其設置爲下一鏈表中的節點（我認爲它是更有意義的是先前），然後將該節點分配給頭，這對我來說是沒有意義的。

我已經在調試中加入了一堆代碼，但仍然無法弄清楚究竟發生了什麼。有人可以走我嗎？

來源

2010-06-27 Shane

它將新節點添加到列表頭部。新節點將其「下一個」指針設置爲舊的頭，然後將新節點設置爲列表的新當前頭。

換句話說，如果你開始...

C -> B -> A 

^ head of list

那麼你風與...

D -> C -> B -> A 

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

來源

2010-06-27 22:54:47 Amber

它添加元素到列表中的前。

僞代碼：

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

來源

2010-06-27 22:55:02

正如其他人所說，這是添加元素到列表的前面。爲什麼？因爲在列表的前面添加一個元素會花費相同的時間，而不管列表中有多少項目，因此它是O（1）（或常量）時間。

如果您要添加到列表的尾部，您必須查看第一個項目，找到下一個項目，檢查其下一個項目，然後重複，直到找到沒有下一個項目的項目（即其next屬性爲空）。這是O（n）時間或線性，其中n是列表中的項目數。

因此，從高效的角度來看，添加到列表的頭部會好很多。

來源

2010-06-27 23:00:01

瞭解鏈接列表

回答

相關問題