单链表是什么?
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) +指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
代码实现
- 定义链表节点类
/// <summary>
/// 链表节点
/// </summary>
public class ListNode<T>
{
public T data; // 存储的数据
public ListNode<T> next; // 下一个节点的引用
public ListNode(){}
public ListNode(T data){
this.data = data;
}
public ListNode(T data,ListNode<T> next) : this(data){
this.next = next;
}
}
- 实现链表类,封装对链表的基本操作
/// <summary>
/// 单链表类(实现链表的一些基本操作)
/// </summary>
public class SingleLinkedList<T>
{
public ListNode<T> head = null; // 表头节点
private int count = 0;
public int Count{
get{return count;}
}
/// <summary>
/// 根据索引获取元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T Get(int index){
if(index < 0 || index >= count) throw new IndexOutOfRangeException("链表索引越界");
if(index == 0) return head.data;
return GetPrevNode(index).next.data;
}
/// <summary>
/// 设置索引位置上的元素
/// </summary>
/// <param name="index"></param>
/// <param name="newData"></param>
public void Set(int index, T newData){
if(index < 0 || index >= count) throw new IndexOutOfRangeException("链表索引越界");
if(index == 0) head.data = newData;
GetPrevNode(index).next.data = newData;
}
/// <summary>
/// 添加到链表尾部
/// </summary>
/// <param name="data"></param>
public void Append(T data){
ListNode<T> newNode = new ListNode<T>(data);
if(head == null){
head = newNode;
}else{
ListNode<T> tempNode = head;
while(tempNode.next != null){
tempNode = tempNode.next;
}
tempNode.next = newNode;
}
count++;
}
/// <summary>
/// 添加到指定的索引位置
/// </summary>
/// <param name="index"></param>
/// <param name="data"></param>
public void Insert(int index,T data){
if(index < 0 || index > count) throw new IndexOutOfRangeException("链表索引越界");
ListNode<T> newNode = new ListNode<T>(data);
if(index == 0){
newNode.next = head;
head = newNode;
}else{
ListNode<T> prevNode = GetPrevNode(index);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
count++;
}
/// <summary>
/// 获取元素所在的索引
/// </summary>
/// <param name="data"></param>
/// <returns></returns>
public int IndexOf(T data){
ListNode<T> tempNode = head;
for (int i = 0; i < count; i++) {
if(tempNode.data.Equals(data))
return i;
tempNode = tempNode.next;
}
return -1;
}
/// <summary>
/// 移除元素
/// </summary>
/// <param name="data"></param>
public void Remove(T data){
int index = IndexOf(data);
if(index != -1){
RemoveAt(index);
}
}
/// <summary>
/// 移除索引位置上的元素,并返回该元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T RemoveAt(int index){
if(index < 0 || index >= count) throw new IndexOutOfRangeException("链表索引越界");
T removeData = default(T);
if(index == 0){
removeData = head.data;
head = head.next;
}else{
ListNode<T> prevNode = GetPrevNode(index);
ListNode<T> currentNode = prevNode.next;
removeData = currentNode.data;
prevNode.next = currentNode.next;
}
count--;
return removeData;
}
/// <summary>
/// 是否为空链表表
/// </summary>
public bool IsEmpty{
get{return count == 0;}
}
/// <summary>
/// 清空链表
/// </summary>
public void Clear(){
head = null;
count = 0;
}
/// <summary>
/// 重写ToString方法,方便查看链表信息
/// </summary>
/// <returns></returns>
public override string ToString()
{
StringBuilder sb = new StringBuilder();
sb.AppendFormat("Count={0}\n",count);
sb.Append("[");
for (int i = 0; i < count; i++) {
if(i == count - 1)
sb.Append(Get(i).ToString());
else
sb.AppendFormat("{0}, ",Get(i));
}
sb.Append("]");
return sb.ToString();
}
/// <summary>
/// 获取索引位置的上一个节点
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
private ListNode<T> GetPrevNode(int index){
ListNode<T> tempNode = head;
for(int i = 0; i < index - 1; i++){
tempNode = tempNode.next;
}
return tempNode;
}
}
测试
class Program
{
public static void Main(string[] args)
{
SingleLinkedList<int> list = new SingleLinkedList<int>();
for(int i = 0; i < 10; i++){
list.Append(i);
}
Console.WriteLine(list);
list.Set(9,100);
Console.WriteLine(list);
list.RemoveAt(9);
list.RemoveAt(7);
list.Insert(3,99);
Console.WriteLine(list);
list.Remove(99);
Console.WriteLine(list);
Console.ReadKey(true);
}
}