單向鏈表

單向鏈表是一種簡單的線型存儲結(jié)構(gòu)，其特點是只能從一個前驅(qū)節(jié)點找到一個后繼節(jié)點，沒有后繼節(jié)點的節(jié)點稱為頭節(jié)點，沒有后繼的節(jié)點稱為尾節(jié)點。示例如下圖：

從上圖來看鏈表是存在邏輯關(guān)系，但在物理內(nèi)存中它們的存儲是沒有前后關(guān)系，而是分布在不同的位置。如果前節(jié)點需要找到后繼節(jié)點，那么前節(jié)點就需要從本節(jié)點中找到后斷節(jié)點的地址，也就是說每個鏈表節(jié)點必須存儲下個節(jié)點的引用。鏈表在插入的時候可以達(dá)到O⑴的復(fù)雜度，比另一種線性表：順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表相應(yīng)的時間復(fù)雜度分別是O(logn)和O⑴。使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機(jī)內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。

創(chuàng)建單向鏈表的算法代碼如下：

1. 鏈表節(jié)點類：

2. 鏈表頭節(jié)點引用、當(dāng)前節(jié)點引用：

3. 鏈表創(chuàng)建法算：

4. 打印鏈表:

完整源代碼如下：

using System; using System.Text;
 
namespace LB
{
    class Program
    {
        static void Main(string[] args){
            Node head = null;
            Node now = null;
            do{
                Node temp = new Node();
                Console.Write("請輸入數(shù)據(jù):");
                temp.data = Console.ReadLine();
                if (head != null){
                    now.next = temp;
                    now = now.next;
                }
                else
                {
                    head = temp;
                    now = head;
                }
                Console.Write("輸入n退出循環(huán):");
            } while (Console.ReadLine() != "n");
 
            Node tmp = head;
            while (tmp != null)
            {
                Console.WriteLine(tmp.data);
                tmp = tmp.next;
            }
        }
    }
    class Node
    {
       public object data;
       public Node next;
    }

}

【北大青鳥深圳嘉華】