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

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

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

2、LinkedList 類，包含鏈表中的第一個(gè)Node，以及關(guān)于鏈表的任何附加信息。

3、測(cè)試程序，用于測(cè)試 LinkedList 類。

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

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

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

鏈接表本身是由很多的Node構(gòu)成，這些Note，如上面所說(shuō)，必須包含數(shù)據(jù)(整型 和 Employee)和鏈表中下一個(gè)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; }  
    }  
} 

注意構(gòu)造函數(shù)將私有的數(shù)據(jù)成員設(shè)置成傳遞進(jìn)來(lái)的對(duì)象，并且將 next 字段設(shè)置成null。

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

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

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

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

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

這樣，當(dāng)你調(diào)用第一個(gè)Node的ToString()方法時(shí)，將打印出所有鏈表上Node的值。

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

public class LinkedList{  
    Node headNode = null;  
} 

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

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

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

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()方法再一次被覆蓋，用以調(diào)用headNode的ToString()方法。

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

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

【編輯推薦】

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