寫在前面
模塊化編程是大多數(shù)初學(xué)者必經(jīng)之路，然后可能你走向了結(jié)構(gòu)化編程，鏈表是一種典型結(jié)構(gòu)模式，它的出現(xiàn)克服了數(shù)組必須預(yù)先知道大小的缺陷，聽不懂?你只需要記住，鏈表結(jié)構(gòu)非常牛叉就可以了，學(xué)習(xí)這種結(jié)構(gòu)對我們的邏輯思維有很大提升。
什么是鏈表結(jié)構(gòu)呢？
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)。比如A->B->C，這種結(jié)構(gòu)，我們可以理解為A連接著B，B連接C，像這種結(jié)構(gòu)我們就叫做鏈表結(jié)構(gòu)。對了，火車的車廂，其實就是鏈表的結(jié)構(gòu)的最好說明
為什么要有鏈表結(jié)構(gòu)呢？
學(xué)過計算機(jī)的都知道數(shù)組(Array),數(shù)組常用切好用，但也存在問題。首先，數(shù)組必須需要知道空間大小（int[] age = new int[100], 必須聲明長度），其次，對于元素之間插入、刪除操作效率很低（如何在數(shù)組中間插入一個元素？）。
鏈表的出現(xiàn)，完美的解決了這些問題。
如何實現(xiàn)鏈表
首先我們需要聲明一種結(jié)構(gòu)
//鏈表結(jié)構(gòu): 構(gòu)造節(jié)點(diǎn) - 連接節(jié)點(diǎn)//Templateclass Node{ public int num; //指向下一個元素 public Node next;}//鏈表結(jié)構(gòu): 構(gòu)造節(jié)點(diǎn) - 連接節(jié)點(diǎn)//Templateclass Node{ public int num; //指向下一個元素 public Node next;}
我們可以把上面的這種結(jié)構(gòu)看做是一個禮品盒,可以存放整形數(shù)值。
然后我們創(chuàng)建一個MyList先生，這位先生就使用Node去存放整形物品，而且使用了鏈表結(jié)構(gòu)哦！
class MyList{ public Node currentNode; public Node point; public MyList() { currentNode = new Node(); } //存放物品 public void Add(int value) { //第一次 if(point == null) { currentNode.num = value; point = currentNode; } else //2 3 4..... 次 { Node temp = new Node(); temp.num = value; point.next = temp; //更新指針 point = temp; } }}class MyList{ public Node currentNode; public Node point; public MyList() { currentNode = new Node(); } //存放物品 public void Add(int value) { //第一次 if(point == null) { currentNode.num = value; point = currentNode; } else //2 3 4..... 次 { Node temp = new Node(); temp.num = value; point.next = temp; //更新指針 point = temp; } }}
然后，我們可以在客戶端測試一下：
public static void Main (string[] args){ MyList<int> mList = new MyList<int>(); //添加元素 mList.Add(1); mList.Add(11); mList.Add(111); mList.Add(1111); while(mList.currentNode != null) { Console.WriteLine (mList.currentNode.num); mList.currentNode = mList.currentNode.next; }}public static void Main (string[] args){ MyList<int> mList = new MyList<int>(); //添加元素 mList.Add(1); mList.Add(11); mList.Add(111); mList.Add(1111); while(mList.currentNode != null) { Console.WriteLine (mList.currentNode.num); mList.currentNode = mList.currentNode.next; }}
我們自己定義的一個整形集合就這樣ok了。它有兩個優(yōu)點(diǎn)：可以存放任意多個元素！方便元素的插入和刪除。
雙向鏈表的定義和簡單操作：
雙向鏈表其實是單鏈表的改進(jìn)。當(dāng)我們對單鏈表進(jìn)行操作時，有時你要對某個結(jié)點(diǎn)的直接前驅(qū)進(jìn)行操作時，又必須從表頭開始查找。這是由單鏈表結(jié)點(diǎn)的結(jié)構(gòu)所限制的。因為單鏈表每個結(jié)點(diǎn)只有一個存儲直接后繼結(jié)點(diǎn)地址的鏈域，那么能不能定義一個既有存儲直接后繼結(jié)點(diǎn)地址的鏈域，又有存儲直接前驅(qū)結(jié)點(diǎn)地址的鏈域的這樣一個雙鏈域結(jié)點(diǎn)結(jié)構(gòu)呢？這就是雙向鏈表。在雙向鏈表中，結(jié)點(diǎn)除含有數(shù)據(jù)域外，還有兩個鏈域，一個存儲直接后繼結(jié)點(diǎn)地址，一般稱之為右鏈域；一個存儲直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域。
namespace DounlyLinkedlist{ //定義雙向鏈表的結(jié)點(diǎn) public class Node { public Object Element; public Node FLink; public Node BLink; public Node() { Element = null; FLink = null; BLink = null; } public Node(Object element) { Element = element; FLink = null; BLink = null; } } //鏈表操作的類 public class LinkedList { public Node Header; public LinkedList() { Header = new Node("Header"); Header.FLink = null; Header.BLink = null; } //查找結(jié)點(diǎn) private Node Find(Object item) { Node Current = new Node(); Current = Header; while (Current.Element != item) { Current = Current.FLink; } return Current; } //插入結(jié)點(diǎn) public void InsertNode(Object item,Object postionItem) { Node Current = new Node(); Node NewItem = new Node(item); Current = Find(postionItem); if (Current != null) { NewItem.FLink = Current.FLink; NewItem.BLink = Current; Current.FLink = NewItem; } } //刪除結(jié)點(diǎn) public void Remove(Object item) { Node P = Find(item); if (P.FLink != null) { P.BLink.FLink = P.FLink; P.FLink.BLink = P.BLink; P.BLink = null; P.FLink = null; } } //查找雙向鏈表最后一個結(jié)點(diǎn)元素 private Node FindLast() { Node Current = new Node(); Current = Header; while (!(Current.FLink == null)) { Current = Current.FLink; } return Current; } //逆向打印雙向鏈表 public void PrintReverse() { Node Current = new Node(); Current = FindLast(); while (!(Current.BLink == null)) { Console.WriteLine(Current.Element); Current = Current.BLink; } } //打印雙向鏈表 public void Print() { Node Current = new Node(); Current = Header; while (!(Current.FLink == null)) { Console.WriteLine(Current.FLink.Element); Current = Current.FLink; } } }} 鏈表應(yīng)用場景
應(yīng)用場景：集合（動態(tài)數(shù)組）、貪吃蛇、地圖的循環(huán)生成、老虎機(jī)效果等等,鏈表可以幫助我們完成很多事情。
