C#实现单链表(线性表)完整实例
本文实例讲述了C#实现单链表(线性表)的方法。分享给大家供大家参考，具体如下：
顺序表由连续内存构成，链表则不同。顺序表的优势在于查找，链表的优势在于插入元素等操作。顺序表的例子：https://www.nhooo.com/article/87605.htm
要注意的是，单链表的Add（）方法最好不要频繁调用，尤其是链表长度较长的时候，因为每次Add，都会从头节点到尾节点进行遍历，这个缺点的优化方法是将节点添加到头部，但顺序是颠倒的。
所以，在下面的例子中，执行Purge（清洗重复元素）的时候，没有使用Add（）方法去添加元素，而是定义一个节点，让它始终指向目标单链表的最后一个节点，这样就不用每次都从头到尾遍历。
此外，链表还可以做成循环链表，即最后一个结点的next属性等于head，主要操作与单链表相似，判断最后一个结点，不是等于null，而是等于head
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceLinearList
{
//定义线性表的行为，可供顺序表类和单链表类继承
publicinterfaceIListDS<T>
{
intGetLength();
voidInsert(Titem,inti);
voidAdd(Titem);
boolIsEmpty();
TGetElement(inti);
voidDelete(inti);
voidClear();
intLocateElement(Titem);
voidReverse();
}
//链表节点类
classNode<T>
{
privateTtData;
privateNode<T>nNext;
publicTData
{
get{returnthis.tData;}
set{this.tData=value;}
}
publicNode<T>Next
{
get{returnthis.nNext;}
set{this.nNext=value;}
}
publicNode()
{
this.tData=default(T);
this.nNext=null;
}
publicNode(Tt)
{
this.tData=t;
this.nNext=null;
}
publicNode(Tt,Node<T>node)
{
this.tData=t;
this.nNext=node;
}
}
//该枚举表示单链表Add元素的位置，分头部和尾部两种
enumAddPosition{Head,Tail};
//单链表类
classLinkedList<T>:IListDS<T>
{
privateNode<T>tHead;//单链表的表头
publicNode<T>Head
{
get{returnthis.tHead;}
set{this.tHead=value;}
}
publicLinkedList()
{
this.tHead=null;
}
publicLinkedList(Node<T>node)
{
this.tHead=node;
}
publicvoidAdd(Titem,AddPositionp)//选择添加位置
{
if(p==AddPosition.Tail)
{
this.Add(item);//默认添加在末尾
}
else//从头部添加会节省查找的开销，时间复杂度为O(1)不必每次都循环到尾部，这恰好是顺序表的优点
{
Node<T>node=this.Head;
Node<T>nodeTmp=newNode<T>(item);
if(node==null)
{
this.Head=nodeTmp;
}
else
{
nodeTmp.Next=node;
this.tHead=nodeTmp;
}
}
}
#regionIListDS<T>成员
publicintGetLength()
{
Node<T>node=newNode<T>();
intcount=0;
node=this.tHead;
while(node!=null)
{
count++;
node=node.Next;
}
returncount;
}
publicvoidInsert(Titem,inti)//i最小从1开始
{
Node<T>insertNode=newNode<T>(item,null);//实例化待添加的Node
if(this.tHead==null&&i==1)
{
this.tHead=insertNode;
return;
}
if(i<1||i>this.GetLength()||(this.tHead==null&&i!=1))
{
Console.WriteLine("Therearenoelementsinthislinkedlist!");
return;
}
intj=1;
Node<T>node=this.tHead;
Node<T>nodeTmp;
while(node!=null&&j<i)//循环结束时，保证node为第i个node
{
node=node.Next;
j++;
}
nodeTmp=node.Next;//原来的单链表的第i+1个node
node.Next=insertNode;//第i个node后的node修改为待插入的node
insertNode.Next=nodeTmp;//待插入的node插入后，其后继node为原来链表的第i+1个node
}
publicvoidAdd(Titem)//添加至尾部，时间复杂度为O(n)，如果添加至头部，则会节省循环的开销
{
Node<T>LastNode=newNode<T>(item,null);//实例化待添加的Node
if(this.tHead==null)
{
this.tHead=LastNode;
}
else
{
Node<T>node=this.tHead;
while(node.Next!=null)
{
node=node.Next;
}
node.Next=LastNode;
}
}
publicboolIsEmpty()
{
returnthis.tHead==null;
}
publicTGetElement(inti)//设i最小从1开始
{
if(i<1||i>this.GetLength())
{
Console.WriteLine("Thelocationisnotright!");
returndefault(T);
}
else
{
if(i==1)
{
returnthis.tHead.Data;
}
else
{
Node<T>node=this.tHead;
intj=1;
while(j<i)
{
node=node.Next;
j++;
}
returnnode.Data;
}
}
}
publicvoidDelete(inti)//设i最小从1开始
{
if(i<1||i>this.GetLength())
{
Console.WriteLine("Thelocationisnotright!");
}
else
{
if(i==1)
{
Node<T>node=this.tHead;
this.tHead=node.Next;
}
else
{
Node<T>node=this.tHead;
intj=1;
while(j<i-1)
{
node=node.Next;
j++;
}
node.Next=node.Next.Next;
}
}
}
publicvoidClear()
{
this.tHead=null;//讲thead设为null后，则所有后继结点由于失去引用，等待GC自动回收
}
publicintLocateElement(Titem)//返回值最小从1开始
{
if(this.tHead==null)
{
Console.WriteLine("Therearenoelementsinthislinkedlist!");
return-1;
}
Node<T>node=this.tHead;
inti=0;
while(node!=null)
{
i++;
if(node.Data.Equals(item))//如果Data是自定义类型，则其Equals函数必须override
{
returni;
}
node=node.Next;
}
Console.WriteLine("Nofound!");
return-1;
}
publicvoidReverse()
{
if(this.tHead==null)
{
Console.WriteLine("Therearenoelementsinthislinkedlist!");
}
else
{
Node<T>node=this.tHead;
if(node.Next==null)//如果只有头节点，则不作任何改动
{
}
else
{
Node<T>node1=node.Next;
Node<T>node2;
while(node1!=null)
{
node2=node.Next.Next;
node.Next=node2;//可以发现node始终未变，始终是原来的那个头节点
node1.Next=this.tHead;
this.tHead=node1;
node1=node2;
}
}
}
}
#endregion
}
classProgram
{
staticvoidMain(string[]args)
{
/*测试单链表的清空
lList.Clear();
Node<int>n=newNode<int>();
n=lList.Head;
while(n!=null)
{
Console.WriteLine(n.Data);
n=n.Next;
}
Console.ReadLine();
*/
/*测试单链表返回元素个数
LinkedList<int>lList=newLinkedList<int>();
lList.Add(3);
Console.WriteLine(lList.GetLength());
Console.ReadLine();
*/
/*测试单链表插入
LinkedList<int>lList=newLinkedList<int>();
lList.Insert(0,1);
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
lList.Insert(99,3);
Node<int>n=newNode<int>();
n=lList.Head;
while(n!=null)
{
Console.WriteLine(n.Data);
n=n.Next;
}
Console.ReadLine();
*/
/*测试单链表获取某位置的值
LinkedList<int>lList=newLinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
Console.WriteLine(lList.GetElement(1));
Console.ReadLine();
*/
/*测试单链表删除某位置的值
LinkedList<int>lList=newLinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
Node<int>n=newNode<int>();
n=lList.Head;
while(n!=null)
{
Console.WriteLine(n.Data);
n=n.Next;
}
Console.ReadLine();
lList.Delete(2);
Node<int>m=newNode<int>();
m=lList.Head;
while(m!=null)
{
Console.WriteLine(m.Data);
m=m.Next;
}
Console.ReadLine();
*/
/*测试单链表按值查找元素位置
LinkedList<int>lList=newLinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
Console.WriteLine(lList.LocateElement(3));
Console.ReadLine();
*/
/*测试单链表Reverse操作（逆序）
LinkedList<int>lList=newLinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
lList.Add(5);
Node<int>m=newNode<int>();
m=lList.Head;
while(m!=null)
{
Console.WriteLine(m.Data);
m=m.Next;
}
Console.ReadLine();
lList.Reverse();
Node<int>n=newNode<int>();
n=lList.Head;
while(n!=null)
{
Console.WriteLine(n.Data);
n=n.Next;
}
Console.ReadLine();
*/
/*测试单链表从头部添加元素
LinkedList<int>lList=newLinkedList<int>();
lList.Add(1,AddPosition.Head);
lList.Add(2,AddPosition.Head);
lList.Add(3,AddPosition.Head);
lList.Add(4,AddPosition.Head);
lList.Add(5,AddPosition.Head);
Node<int>m=newNode<int>();
m=lList.Head;
while(m!=null)
{
Console.WriteLine(m.Data);
m=m.Next;
}
Console.ReadLine();
*/
/*测试对单链表清除重复元素操作（返回另一链表）。这个例子中避免使用Add（）方法，因为每个Add（）都要从头到尾进行遍历，不适用Add（）方法
就要求对目标链表的最后一个元素实时保存。另一种避免的方法在于从头部Add，但这样的最终结果为倒序
LinkedList<int>lList=newLinkedList<int>();//原链表
LinkedList<int>lList2=newLinkedList<int>();//保存结果的链表
lList.Add(1);
lList.Add(2);
lList.Add(1);
lList.Add(3);
lList.Add(3);
lList.Add(4);
lList.Add(5);
Node<int>m=newNode<int>();
m=lList.Head;
while(m!=null)
{
Console.WriteLine(m.Data);
m=m.Next;
}
Console.ReadLine();
Node<int>node1=lList.Head;//标识原链表的当前要参与比较大小的元素，即可能放入链表2中的元素
Node<int>node2;//标识结果单链表的最后一个元素，避免使用Add函数造成多次遍历
Node<int>node3;//对node1的后继进行暂时保存，并最终付给node1
node3=node1.Next;
lList2.Head=node1;//链表1的头结点肯定要加入链表2
node2=lList2.Head;//node2表示链表2的最后一个元素，此时最后一个元素为头结点
node2.Next=null;//由于是把node1赋给了链表2的头结点，必须把它的后续结点设为null，否则会一起带过来
node1=node3;//如果没有node3暂存node1的后继，对lList2.Head后继赋为null的就会同时修改node1的后继，因为两者指向同一块内存
while(node1!=null)
{
//在iList2中比较大小
Node<int>tmp=lList2.Head;
if(node1.Data.Equals(tmp.Data))
{
node1=node1.Next;
continue;//若相等，则node1向后移一位，重新计算
}
else
{
Node<int>tmp2=tmp;
tmp=tmp.Next;//tmp标识链表2的用于循环的节点，与node比较
if(tmp==null)//当链表2中现有元素与node1都不相等时
{
node3=node1.Next;
node2.Next=node1;
node2=node1;
node2.Next=null;
node1=node3;
continue;
}
while(tmp!=null)//tmp不为null时，一直循环到它为null
{
if(node1.Data.Equals(tmp.Data))
{
node1=node1.Next;
}
else
{
tmp2=tmp;
tmp=tmp.Next;
if(tmp==null)
{
node3=node1.Next;
node2.Next=node1;
node2=node1;
node2.Next=null;
node1=node3;
}
}
}
}
}
//输出清除重复处理后的数组
Node<int>n=newNode<int>();
n=lList2.Head;
while(n!=null)
{
Console.WriteLine(n.Data);
n=n.Next;
}
Console.ReadLine();
*/
}
}
}
更多关于C#相关内容感兴趣的读者可查看本站专题：《C#数据结构与算法教程》、《C#遍历算法与技巧总结》、《C#程序设计之线程使用技巧总结》、《C#操作Excel技巧总结》、《C#中XML文件操作技巧汇总》、《C#常见控件用法教程》、《WinForm控件用法总结》、《C#数组操作技巧总结》及《C#面向对象程序设计入门教程》
希望本文所述对大家C#程序设计有所帮助。