C#的链表操作[数据结构-线性表]

链式存储结构图解：

 上图中，a1,是数据，紧跟着后面的d1是下一个节点的地址值。也就是一个节点的最后存储的是下一个节点的地址值，最后一个节点的存储的下一个地址值是null，代表链表结束。 

 

1，定义链表类

/// <summary>
/// 单项链表
/// </summary>
public class Node
{
/// <summary>
/// 指针：链表节点的引用，指向下一个节点
/// </summary>
public Node next;

/// <summary>
/// 链表节点对象，即链表的内容
/// </summary>
public object data;

public Node(object data)
{
this.data = data;
next = null;
}
}

 

2，链表的操作类

/// <summary>
/// 链表操作
/// </summary>
public class LinkNode
{
/// <summary>
/// 链表头结点
/// </summary>
public Node head;
/// <summary>
/// 节点的位置
/// </summary>
private int pos = 0;

public LinkNode()
{
this.head = null;
}

/// <summary>
/// 链表是否为空
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public bool IsEmpty(Node node)
{
bool b = false;

if (node == null)
{
b = true;
}

return b;
}

/// <summary>
/// 节点数
/// </summary>
/// <returns></returns>
public long Length()
{
return Length(head);
}

/// <summary>
/// 节点数
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public long Length(Node node)
{
long len = 0;

while (node != null)
{
len++;
node = node.next;
}

return len;
}

/// <summary>
/// 增加节点
/// </summary>
/// <param name="o"></param>
/// <returns>头插法</returns>
public Node AddNodeHead(object o)
{
Node newNode = new Node(o);
if (IsEmpty(this.head))
{
this.head = newNode;
}
else
{
newNode.next = head;
head = newNode;
}

return this.head;
}

/// <summary>
/// 增加节点
/// </summary>
/// <param name="o"></param>
/// <returns>尾插法</returns>
public Node AddNodeAtLast(object o)
{
Node newNode = new Node(o);
Node p = head;

if (IsEmpty(head))
{
newNode.next = head;
head = newNode;
}
else
{
while (p.next != null)
{
p = p.next;
}
p.next = newNode;
}

return head;
}

/// <summary>
/// 在指定位置插入节点
/// </summary>
/// <param name="index">位置</param>
/// <param name="o">节点数据</param>
/// <returns></returns>
public Node Insert(int index, object o)
{
if (head == null)
{
head = null;
}
else
{
Node node = new Node(o);

long con = Length();//节点个数
if (index == 1)
{
node.next = head;
head = node;
}
else if (index == con)
{
Node p = head;
while (p.next != null)
{
p = p.next;
}
p.next = node;
}
else if (1 < index && index < con)
{
int pos = 1;
Node current = head;
Node previous = head;
while (pos != index)
{
previous = current;
current = current.next;
pos++;
}

node.next = current;
previous.next = node;
}
else
{

}
}

return head;
}

/// <summary>
/// 删除头节点
/// </summary>
/// <returns></returns>
public Node DeleteHead()
{
if (head != null)
{
head = head.next;
}
return head;
}
/// <summary>
/// 删除节点
/// </summary>
/// <returns></returns>
public Node Delete(int index)
{
int con = Convert.ToInt32(Length());
if (1 <= index && index <= con)
{
Node current = head;
Node previous = head;
int pos = 1;
while (pos != index)
{
pos++;
previous = current;
current = current.next;
}
if (current == head)
{
head = head.next;
}
else
{
previous.next = current.next;
}
}

return head;
}

/// <summary>
/// 反转链表
/// </summary>
/// <returns></returns>
public Node Reversal()
{
Node ReversalNode = head;
head = null;
while (ReversalNode != null)
{
AddNodeHead(ReversalNode.data);
ReversalNode = ReversalNode.next;
}

return head;
}
}