单向链表
其实就是一种链式存储的数据结构,它和数组不同,数组的存储结构就是连续的,且长度是固定的。而链表不一样,它可以是连续的,也可以是不连续的,而且是可以动态扩容的。
链表中的数据是以节点的形式表现出来的。结构为:数据+指针
┌───┬───┐
│data│next│
└───┴───┘
data域–存放结点值的元素。
next域–存放结点的直接后继的地址的指针域[指针]。
自己为了练习,把它敲了一遍,放在下面,有什么不足的地方希望大家多多指教~~
public class Node<T>//节点类
{
private Node<T> m_Next;//直接后继节点
private T data;//插入进来的元素
public Node<T> Next
{
get
{
return m_Next;
}
set
{
m_Next = value;
}
}
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}
public Node()
{
m_Next = null;
data = default(T);
}
public Node(T _data)
{
data = _data;
m_Next = null;
}
}//节点类
public class MyList<T>
{
private uint length;
private Node<T> m_head;//头结点
private Node<T> m_tail;//尾节点
public uint Count//判断链表的长度
{
get
{
return length;
}
}
public bool IsEmpty
{
get
{
return (m_head == null ? true : false);
}
}
public void Push_List(T _data)
{
Node<T> newNode = new Node<T>(_data);
if (IsEmpty)
{
m_head = newNode;
}
else
{
m_tail.Next = newNode;
}
m_tail = newNode;
++length;
}//直接插入的情况
public bool Push_Front(T _data, uint position)//前插的情况
{
if (IsEmpty)
{
Console.WriteLine("链表为空,不可进行前插操作");
return false;
}
else if (position > length)
{
Console.WriteLine("界限超界,无法进行前插操作");
return false;
}
if (position == 0)//成为了头结点的情况
{
Node<T> newNode = new Node<T>(_data);
newNode.Next = m_head;
m_head = newNode;
++length;
return true;
}
else//除了头以后的前插
{
Node<T> tempNode = m_head;
Node<T> tempFront = null;
uint tempIndex = 1;
while (tempNode.Next != null && tempIndex <= position)
{
tempFront = tempNode;
tempNode = tempNode.Next;
++tempIndex;
}
//如果找到了相应的位置
Node<T> newNode = new Node<T>(_data);
newNode.Next = tempNode;
tempFront.Next = newNode;
++length;
return true;
}
}
public bool Push_Back(T _data, uint position)//后插的情况
{
Node<T> newNode = new Node<T>(_data);
if (IsEmpty)
{
Console.WriteLine("链表为空,不可进行后插操作");
return false;
}
else if (position > length)
{
Console.WriteLine("链表超界,不可进行后插操作");
return false;
}
if (position == 0)
{
newNode.Next = m_head.Next;
m_head.Next = newNode;
++length;
return true;
}
else if (position == length - 1)//成为了尾节点的情况
{
m_tail.Next = newNode;
m_tail = newNode;
m_tail.Next = m_head;
length++;
return true;
}
else //除了头和尾的插入
{
Node<T> tempNode = m_head;
uint tempIndex = 1;
while (tempNode.Next != null && tempIndex <= length)
{
tempNode = tempNode.Next;
++length;
}
tempNode.Next = newNode.Next;
tempNode.Next = newNode;
length++;
return true;
}
}
public T Check_Data(uint _position)
{
T clockNode = default(T);
if (m_head == null)
Console.WriteLine("链表为空,不可进行查询操作");
else
{
uint tempIndex = 1;
Node<T> tempNode = m_head;
while (tempNode.Next != null && tempIndex <= _position)
{
tempNode = tempNode.Next;
++tempIndex;
}
clockNode = tempNode.Data;
}
return clockNode;
}
public bool Delete(uint position)//删除指定元素
{
if (IsEmpty)
{
Console.WriteLine("链表为空,不能进行删除操作");
return false;
}
else if (position > length)
{
Console.WriteLine("输入下标超出界限,无法进行删除操作");
return false;
}
else
{
uint tempIndex = 1;
Node<T> tempNode = m_head;
Node<T> clockNode = null;
while ((tempNode.Next != null && tempIndex < length))
{
clockNode = tempNode;
tempNode = tempNode.Next;
++tempIndex;
}
clockNode.Next = tempNode.Next;
if (position == length - 1)
{
m_tail = tempNode;
}
--length;
}
return true;
}
public bool Clear()//清除整个表
{
if (IsEmpty)
{
Console.WriteLine("链表已经为空");
return true;
}
else
{
Node<T> tempNode = m_head;
Node<T> frontNode = null;
uint position = 1;
while (position <= length)
{
frontNode = tempNode;
tempNode = tempNode.Next;
}
return true;
}
}
}
}