C#模拟链表数据结构的实例解析
写在前面
模块化编程是大多数初学者必经之路，然后可能你走向了结构化编程，链表是一种典型结构模式，它的出现克服了数组必须预先知道大小的缺陷，听不懂?你只需要记住，链表结构非常牛叉就可以了，学习这种结构对我们的逻辑思维有很大提升。
什么是链表结构呢？
链表是一种物理存储单元上非连续、非顺序的存储结构。比如A->B->C，这种结构，我们可以理解为A连接着B，B连接C，像这种结构我们就叫做链表结构。对了，火车的车厢，其实就是链表的结构的最好说明
为什么要有链表结构呢？
学过计算机的都知道数组(Array),数组常用切好用，但也存在问题。首先，数组必须需要知道空间大小（int[]age=newint[100],必须声明长度），其次，对于元素之间插入、删除操作效率很低（如何在数组中间插入一个元素？）。
链表的出现，完美的解决了这些问题。
如何实现链表
首先我们需要声明一种结构
//链表结构:构造节点-连接节点
//Template
classNode
{
publicintnum;
//指向下一个元素
publicNodenext;
}
//链表结构:构造节点-连接节点
//Template
classNode
{
publicintnum;
//指向下一个元素
publicNodenext;
}
我们可以把上面的这种结构看做是一个礼品盒,可以存放整形数值。
然后我们创建一个MyList先生，这位先生就使用Node去存放整形物品，而且使用了链表结构哦！
classMyList
{
publicNodecurrentNode;
publicNodepoint;
publicMyList()
{
currentNode=newNode();
}
//存放物品
publicvoidAdd(intvalue)
{
//第一次
if(point==null)
{
currentNode.num=value;
point=currentNode;
}
else//234.....次
{
Nodetemp=newNode();
temp.num=value;
point.next=temp;
//更新指针
point=temp;
}
}
}
classMyList
{
publicNodecurrentNode;
publicNodepoint;
publicMyList()
{
currentNode=newNode();
}
//存放物品
publicvoidAdd(intvalue)
{
//第一次
if(point==null)
{
currentNode.num=value;
point=currentNode;
}
else//234.....次
{
Nodetemp=newNode();
temp.num=value;
point.next=temp;
//更新指针
point=temp;
}
}
}
然后，我们可以在客户端测试一下：
publicstaticvoidMain(string[]args)
{
MyList<int>mList=newMyList<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;
}
}
publicstaticvoidMain(string[]args)
{
MyList<int>mList=newMyList<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了。它有两个优点：可以存放任意多个元素！方便元素的插入和删除。
双向链表的定义和简单操作：
双向链表其实是单链表的改进。当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。
namespaceDounlyLinkedlist
{
//定义双向链表的结点
publicclassNode
{
publicObjectElement;
publicNodeFLink;
publicNodeBLink;
publicNode()
{
Element=null;
FLink=null;
BLink=null;
}
publicNode(Objectelement)
{
Element=element;
FLink=null;
BLink=null;
}
}
//链表操作的类
publicclassLinkedList
{
publicNodeHeader;
publicLinkedList()
{
Header=newNode("Header");
Header.FLink=null;
Header.BLink=null;
}
//查找结点
privateNodeFind(Objectitem)
{
NodeCurrent=newNode();
Current=Header;
while(Current.Element!=item)
{
Current=Current.FLink;
}
returnCurrent;
}
//插入结点
publicvoidInsertNode(Objectitem,ObjectpostionItem)
{
NodeCurrent=newNode();
NodeNewItem=newNode(item);
Current=Find(postionItem);
if(Current!=null)
{
NewItem.FLink=Current.FLink;
NewItem.BLink=Current;
Current.FLink=NewItem;
}
}
//删除结点
publicvoidRemove(Objectitem)
{
NodeP=Find(item);
if(P.FLink!=null)
{
P.BLink.FLink=P.FLink;
P.FLink.BLink=P.BLink;
P.BLink=null;
P.FLink=null;
}
}
//查找双向链表最后一个结点元素
privateNodeFindLast()
{
NodeCurrent=newNode();
Current=Header;
while(!(Current.FLink==null))
{
Current=Current.FLink;
}
returnCurrent;
}
//逆向打印双向链表
publicvoidPrintReverse()
{
NodeCurrent=newNode();
Current=FindLast();
while(!(Current.BLink==null))
{
Console.WriteLine(Current.Element);
Current=Current.BLink;
}
}
//打印双向链表
publicvoidPrint()
{
NodeCurrent=newNode();
Current=Header;
while(!(Current.FLink==null))
{
Console.WriteLine(Current.FLink.Element);
Current=Current.FLink;
}
}
}
}
链表应用场景
应用场景：集合（动态数组）、贪吃蛇、地图的循环生成、老虎机效果等等,链表可以帮助我们完成很多事情。