對于閱讀本文的那些從未創(chuàng)建過線性鏈表的人。你可以將線性鏈表想像成有一條鏈子栓在一起的盒子(稱作一個結點)，每個盒子里包含著一些數(shù)據(jù) 和 鏈接到這個鏈子上的下一個盒子的引用(當然，除了最后一個盒子，這個盒子對于下一個盒子的引用被設置成NULL)。

為了創(chuàng)建我們的簡單線性鏈表，我們需要下面三個類：

1、Node 類，包含數(shù)據(jù)以及下一個Node的引用。

2、LinkedList 類，包含鏈表中的第一個Node，以及關于鏈表的任何附加信息。

3、測試程序，用于測試 LinkedList 類。

為了查看鏈接表如何運作，我們添加Objects的兩種類型到鏈表中：整型 和 Employee類型。你可以將Employee類型想象成一個包含關于公司中某一個員工所有信息的類。出于演示的目的，Employee類非常的簡單。

public class Employee{  
　　private string name;  
　　public Employee (string name){  
　　　　this.name = name;  
　　}  
 
　　public override string ToString(){  
　　　return this.name;  
　　}  
} 

這個類僅包含一個表示員工名字的字符串類型，一個設置員工名字的構造函數(shù)，一個返回Employee名字的ToString()方法。

鏈接表本身是由很多的Node構成，這些Note，如上面所說，必須包含數(shù)據(jù)(整型 和 Employee)和鏈表中下一個Node的引用。

public class Node{  
    Object data;  
    Node next;  
 
    public Node(Object data){  
       this.data = data;  
       this.next = null;  
    }  
 
    public Object Data{   
       get { return this.data; }  
       set { data = value; }  
    }  
 
    public Node Next{  
        get { return this.next; }  
       set { this.next = value; }  
    }  
} 

注意構造函數(shù)將私有的數(shù)據(jù)成員設置成傳遞進來的對象，并且將 next 字段設置成null。

這個類還包括一個方法，Append，這個方法接受一個Node類型的參數(shù)，我們將把傳遞進來的Node添加到列表中的最后位置。這過程是這樣的：首先檢測當前Node的next字段，看它是不是null。如果是，那么當前Node就是最后一個Node，我們將當前Node的next屬性指向傳遞進來的新結點，這樣，我們就把新Node插入到了鏈表的尾部。

如果當前Node的next字段不是null，說明當前node不是鏈表中的最后一個node。因為next字段的類型也是node，所以我們調用next字段的Append方法(注：遞歸調用)，再一次傳遞Node參數(shù)，這樣繼續(xù)下去，直到找到最后一個Node為止。

public void Append(Node newNode){  
    if ( this.next == null ){  
       this.next = newNode;  
    }else{  
       next.Append(newNode);  
    }  
} 

Node 類中的 ToString() 方法也被覆蓋了，用于輸出 data 中的值，并且調用下一個 Node 的 ToString()方法(譯注：再一次遞歸調用)。

public override string ToString(){  
    string output = data.ToString();  
 
    if ( next != null ){  
       output += ", " + next.ToString();  
    }  
 
    return output;  
} 

這樣，當你調用第一個Node的ToString()方法時，將打印出所有鏈表上Node的值。

LinkedList 類本身只包含對一個Node的引用，這個Node稱作 HeadNode，是鏈表中的第一個Node，初始化為null。

public class LinkedList{  
    Node headNode = null;  
} 

LinkedList 類不需要構造函數(shù)(使用編譯器創(chuàng)建的默認構造函數(shù))，但是我們需要創(chuàng)建一個公共方法，Add()，這個方法把 data存儲到線性鏈表中。這個方法首先檢查headNode是不是null，如果是，它將使用data創(chuàng)建結點，并將這個結點作為headNode，如果不是null，它將創(chuàng)建一個新的包含data的結點，并調用headNode的Append方法，如下面的代碼所示：

public void Add(Object data){  
    if ( headNode == null ){  
       headNode = new Node(data);  
    }else{  
       headNode.Append(new Node(data));  
    }  
} 

為了提供一點集合的感覺，我們?yōu)榫€性鏈表創(chuàng)建一個索引器。

public object this[ int index ]{  
    get{  
       int ctr = 0;  
       Node node = headNode;  
       while ( node != null  && ctr <  = index ){  
           if ( ctr == index ){  
              return node.Data;  
           }else{  
              node = node.Next;  
           }  
           ctr++;  
        }  
    return null;  
    }  
} 

最后，ToString()方法再一次被覆蓋，用以調用headNode的ToString()方法。

public override string ToString(){  
    if ( this.headNode != null ){  
       return this.headNode.ToString();  
    }else{  
       return string.Empty;  
    }  
} 

這樣，一個線性鏈表就創(chuàng)建好了。

【編輯推薦】

1. C# winForm自定義鼠標樣式的兩種方法
2. C#自定義消息框的設置圖解
3. 掌握C#自定義泛型類：從初始化說起
4. C#存儲過程的循序漸進
5. 存儲過程的優(yōu)勢及其調用方法介紹