C#实现--单链表(链式)

C#实现--单链表(链式)

using System;
using System.Collections.Generic;
using System.Text;

namespace SingleLinkedList
{
class Program
{
static void Main(string[] args)
{

//实例调用

}
}

//定义单链表的结点
//结点存储数据和下一个结点的地址(引用).这里用一个类表示.
public class Node<T>
{
private T data; //数据
private Node<T> next; //引用

//构造器
public Node(T val, Node<T> p)
{
data = val;
next = p;
}

//构造器2
public Node(Node<T> p)
{
next = p;
}

//构造器3
public Node(T val)
{
data = val;
next = null;
}

//构造器4
public Node()
{
data = default(T);
next = null;
}

//数据域属性
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}

//引用域属性
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}

//单链表类--定义操作结点的一些方法(如删除, 插入等).
//IList<T>是.net自带的一个接口. 这里实现了这个接口.
public class LinkList<T> : IList<T>
{
private Node<T> head; //单链表的头引用

//头引用 属性
public Node<T> Head
{
get { return head; }
set { head = value; }
}

//构造器
public LinkList()
{
head = null;
}

///<summary>
///求单链表的长度
///需要从表头开始, 一个结点一个结点遍历,直到表的末尾.
///</summary>

public int GetLength()
{
Node<T> p = head;

int len = 0;
while (p != null)
{
++len;
p = p.Next;
}

return len;
}

///<summary>
/// 清空单链表
/// head=null即可.
/// 单链表清空后,原来结点所占用的空间不会一直保留, 而由垃圾回收器进行回收.
///</summary>
public void Clear()
{
head = null;
}

///<summary>
/// 判断单链表是否为空
/// head==null,即为空
///</summary>
public bool IsEmpty()
{
if (head == null)
{
return true;
}
else
{
return false;
}
}

///<summary>
///附加操作
///在单链表的末尾添加新元素
/// </summary>
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();

if (head == null)
{
head = q;
return;
}

p = head;
while (p.Next != null)
{
p = p.Next;
}

p.Next = q;
}

//在单链表的第 i 个结点位置前插入一个值为 item 的结点.
public void Insert(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error!");
return;
}

//就一个head元素.(插入到head前即可)
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head;
return;
}

//非head(中间某一元素前插入P)
Node<T> p = head;
Node<T> r = new Node<T>();
int j = 1;

while (p.Next != null && j < i)
{
r = p;
p = p.Next;
++j;
}

if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}

}

//在单链表的第 i 个结点的位置后插入一个值为 item的结点.
public void InsertPost(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error!");
return;
}

if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}

Node<T> p = head;
int j = 1;

while (p != null && j < i)
{
p = p.Next;
++j;
}

if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
}

//删除单链表的第 i 个结点
public T Delete(int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}

Node<T> q = new Node<T>();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}

Node<T> p = head;
int j = 1;

//从头一直找到 i 所在的位置
//条件是: (1).单链表没有到末尾, (2).还没有到 i 所在的位置 ( j< i).
while (p.Next != null && j < i)
{
++j;
q = p;
p = p.Next;
}

if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The item node is not exist!");
return default(T);
}
}

//获得单链表的第 i 个数据元素
public T GetElem(int i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return default(T);
}

Node<T> p = new Node<T>();
p = head;
int j = 1;

while (p.Next != null & j < i)
{
++j;
p = p.Next;
}

if (j == i)
{
return p.Data; //找到了.
}
else
{
Console.WriteLine("The item node is not exist!");
return default(T);
}
}

///<summary>
///在单链表中查找值为 value 的结点
///</summary>
public int Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is Empty!");
return -1;
}

Node<T> p = new Node<T>();
p = head;
int i = 1;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
++i;
}

return i;
}

}

}