C# 链表
/// <summary>
/// 链表是线性表(A1,A2,A3,A4,A5,A6)对应的链式存储结构
/// H-->|A1|-->|A2|-->|Ai-1|-->|Ai|-->|An|
/// H 是虚拟节点，相当于根节点(Root)
/// An = {data, next};
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T>
{
/// <summary>
/// 数据
/// </summary>
public T Data { set; get; }
/// <summary>
/// 后驱节点的引用
/// </summary>
public Node<T> Next { set; get; }
public Node()
{
Data = default(T);
Next = null;
}
public Node(T data)
{
this.Data = data;
}
public Node(T data, Node<T> node):this(data)
{
this.Next = node;
}
}
public class MyList<T>
{
/// <summary>
/// 头节点,也可以说是虚拟的根节点
/// </summary>
public Node<T> Head { set; get; }
public MyList()
{
Head = new Node<T>();
}
/// <summary>
/// 链表的length属性
/// </summary>
public int Length
{
get
{
Node<T> point = Head;
int len = 0;
while(point.Next!= null)
{
len++;
point = point.Next;
}
return len;
}
}
/// <summary>
/// 清空单链表
/// </summary>
public void Clear()
{
Head.Next = null;
}
public bool IsEmpty
{
get
{
return this.Length == 0 ? true : false;
}
}
public void Add(T item)
{
Node<T> node = new Node<T>(item);
// 一个节点都没有
if (Head.Next == null)
{
Head.Next = node;
}
else
{
Node<T> point = Head.Next;
while(point.Next != null)
{
point = point.Next;
}
point.Next = node;
}
}
/// <summary>
/// 根据 索引(从0开始) 查找元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetItem(int index)
{
if(index < 0 || index >= this.Length)
{
throw new Exception("the index is error.");
}
if(!this.IsEmpty)
{
Node<T> point = Head.Next;
int j = 0;
while (point!= null && j< index)
{
if(j++ == index)
{
break;
}
point = point.Next;
}
return point.Data;
}
else
{
throw new Exception("the list is empty.");
}
}
/// <summary>
/// 根据value查找下标（从0开始）
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
if (!this.IsEmpty)
{
Node<T> point = Head.Next;
int index = 0;
while (point != null && !point.Data.Equals(value))
{
++index;
point = point.Next;
}
return index;
}
else
{
throw new Exception("the list is empty.");
}
}
/// <summary>
/// 根据下标删除节点
/// </summary>
/// <param name="index"></param>
public T Delete(int index)
{
if (this.IsEmpty || index < 0)
{
throw new Exception("the list is empty or the position is error.");
}
else
{
Node<T> point = Head;
int j = -1;
while(point.Next!=null)
{
if(++j == index)
{
break;
}
point = point.Next; //这个节点是 这个下标 前面的那个节点 例如index=0，此时point = head
}
Node<T> delNode = point.Next; //delNode 也就是要删除的节点
point.Next = delNode.Next;
T value = delNode.Data;
delNode = null;
return value;
}
}
public void Insert(int index, T value)
{
Node<T> point = Head;
int j = 0;
while(point.Next != null)
{
if(j++ == index)
{
break;
}
point = point.Next;
}
Node<T> insertNode = new Node<T>(value);
insertNode.Next = point.Next;
point.Next = insertNode;
}
public void InsertPost(int index, T value)
{
Node<T> point = Head;
int j = 0;
while(point.Next != null)
{
point = point.Next;
if(j++ == index)
{
break;
}
}
Node<T> insertNode = new Node<T>(value);
insertNode.Next = point.Next;
point.Next = insertNode;
}
}
