C#数据结构之单链表(LinkList)实例详解
作者:Jimmy.Yang 发布时间:2021-09-15 21:40:14
本文实例讲述了C#数据结构之单链表(LinkList)实现方法。分享给大家供大家参考,具体如下:
这里我们来看下“单链表(LinkList)”。在上一篇《C#数据结构之顺序表(SeqList)实例详解》的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动。如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大。
而链表结构正好相反,先来看下结构:
每个元素至少具有二个属性:data和next。data用来存放数据,而next用来指出它后面的元素是谁(有点“指针”的意思)。
链表中的元素,通常也称为节点Node,下面是泛型版本的Node.cs
namespace 线性表
{
public class Node<T>
{
private T data;
private Node<T> next;
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
public Node(Node<T> p)
{
next = p;
}
public Node(T val)
{
data = val;
next = null;
}
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; }
}
}
}
链表在存储上并不要求所有元素按顺序存储,因为用节点的next就能找到下一个节点,这好象一根“用珠子串成的链子”,要找到其中的某一颗珠子,只要从第一颗节点(通常称为Head节点)开始,不断根据next指向找到下一个,直到找到需要的节点为止。
链表中需要有一个Head节点做为开始,这跟顺序表有所不同,下面是单链表的实现:
using System;
using System.Text;
namespace 线性表
{
public class LinkList<T> : IListDS<T>
{
private Node<T> head;
public Node<T> Head
{
get { return head; }
set { head = value; }
}
public LinkList()
{
head = null;
}
/// <summary>
/// 类索引器
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
return this.GetItemAt(index);
}
}
/// <summary>
/// 返回单链表的长度
/// </summary>
/// <returns></returns>
public int Count()
{
Node<T> p = head;
int len = 0;
while (p != null)
{
len++;
p = p.Next;
}
return len;
}
/// <summary>
/// 清空
/// </summary>
public void Clear()
{
head = null;
}
/// <summary>
/// 是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return head == null;
}
/// <summary>
/// 在最后附加元素
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
Node<T> d = new Node<T>(item);
Node<T> n = new Node<T>();
if (head == null)
{
head = d;
return;
}
n = head;
while (n.Next != null)
{
n = n.Next;
}
n.Next = d;
}
//前插
public void InsertBefore(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
//在最开头插入
if (i == 0)
{
Node<T> q = new Node<T>(item);
q.Next = Head;//把"头"改成第二个元素
head = q;//把自己设置为"头"
return;
}
Node<T> n = head;
Node<T> d = new Node<T>();
int j = 0;
//找到位置i的前一个元素d
while (n.Next != null && j < i)
{
d = n;
n = n.Next;
j++;
}
if (n.Next == null) //说明是在最后节点插入(即追加)
{
Node<T> q = new Node<T>(item);
n.Next = q;
q.Next = null;
}
else
{
if (j == i)
{
Node<T> q = new Node<T>(item);
d.Next = q;
q.Next = n;
}
}
}
/// <summary>
/// 在位置i后插入元素item
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void InsertAfter(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
if (i == 0)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
int j = 0;
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;
}
else
{
Console.WriteLine("Position is error!");
}
}
/// <summary>
/// 删除位置i的元素
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T RemoveAt(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 == 0)
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
int j = 0;
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 node is not exist!");
return default(T);
}
}
/// <summary>
/// 获取指定位置的元素
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T GetItemAt(int i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return default(T);
}
Node<T> p = new Node<T>();
p = head;
if (i == 0)
{
return p.Data;
}
int j = 0;
while (p.Next != null && j < i)
{
j++;
p = p.Next;
}
if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The node is not exist!");
return default(T);
}
}
//按元素值查找索引
public int IndexOf(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is Empty!");
return -1;
}
Node<T> p = new Node<T>();
p = head;
int i = 0;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
i++;
}
return i;
}
/// <summary>
/// 元素反转
/// </summary>
public void Reverse()
{
LinkList<T> result = new LinkList<T>();
Node<T> t = this.head;
result.Head = new Node<T>(t.Data);
t = t.Next;
//(把当前链接的元素从head开始遍历,逐个插入到另一个空链表中,这样得到的新链表正好元素顺序跟原链表是相反的)
while (t!=null)
{
result.InsertBefore(t.Data, 0);
t = t.Next;
}
this.head = result.head;//将原链表直接挂到"反转后的链表"上
result = null;//显式清空原链表的引用,以便让GC能直接回收
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
Node<T> n = this.head;
sb.Append(n.Data.ToString() + ",");
while (n.Next != null)
{
sb.Append(n.Next.Data.ToString() + ",");
n = n.Next;
}
return sb.ToString().TrimEnd(',');
}
}
}
下面是单链表插入和删除的算法图解:
可以看到:链表在元素插入/删除时,无需对后面的元素进行移动,只需要修改自身以及相邻节点的next指向即可,所以插入/删除元素的开销要比顺序表小得多。但是也应该注意到,其它操作比如:查找元素,反转倒置链表等,有可能需要遍历整个链表中的所有元素。
测试代码片断:
Console.WriteLine("-------------------------------------");
Console.WriteLine("单链表测试开始...");
LinkList<string> link = new LinkList<string>();
link.Head = new Node<string>("x");
link.InsertBefore("w", 0);
link.InsertBefore("v", 0);
link.Append("y");
link.InsertBefore("z", link.Count());
Console.WriteLine(link.Count());//5
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link[1]);//w
Console.WriteLine(link[0]);//v
Console.WriteLine(link[4]);//z
Console.WriteLine(link.IndexOf("z"));//4
Console.WriteLine(link.RemoveAt(2));//x
Console.WriteLine(link.ToString());//v,w,y,z
link.InsertBefore("x", 2);
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link.GetItemAt(2));//x
link.Reverse();
Console.WriteLine(link.ToString());//z,y,x,w,v
link.InsertAfter("1", 0);
link.InsertAfter("2", 1);
link.InsertAfter("6", 5);
link.InsertAfter("8", 7);
link.InsertAfter("A", 10);//Position is error!
Console.WriteLine(link.ToString()); //z,1,2,y,x,w,6,v,8
至于具体在实际应用中应该选用顺序表 or 链表,主要是看:对于元素插入/删除的频繁程度以及对于内存分配的苛刻程度。 如果不要求一开始就分配一组连续的内存区域,可以根据元素的增加而自动加大内存的使用量,或者插入/删除的次数很多,那么建议使用链表,反之用顺序表。
最后指出:可以给节点再添加一个prev元素,用于指出前一个节点是谁,即同时有next和prev二个指向,这种改进后的链表称为“双向链表”,它有助于某些情况下减少遍历循环的次数,本文中的这种仅有一个next指向的链表,称为“单链表”。
希望本文所述对大家C#程序设计有所帮助。
猜你喜欢
- 参考资料:alibaba-easyexcel.github.io简介EasyExcel是一个基于Java的简单、省内存的读写Excel的开源
- 本系列代码地址:https://github.com/JoJoTec/spring-cloud-parentOpenFeign 的由来和实现
- 一般来讲,项目更换JDK版本的情况比较少,但是有时难免会遇到。电脑安装不同版本的JDK这里不做介绍。这里记录一下修改项目JDK版本要注意的几
- 背景接上文《失踪人口回归,mybatis-plus 3.3.2 发布》[1] ,提供了一个非常实用的功能 「数据安全保护」 功能,不仅支持数
- 前言学会使用 API 文档是一个开发者基本的素养,而许多初学者并不会在意 API 文档的使用,甚至从来没有接触过,所以写下这篇文章探讨 AP
- 如有错误,望指正;SpringBoot可以有三种方式定义初始化器,来为容器中增加自定义的对象,具体如下:1、定义在spring.factor
- 前言 短时间提升自己最快的手段就是背面试题,最近总结了Java常用的面试题,分享给大家,希望大家都能圆梦大厂,加油,我命由我不由天
- 前言前面小空带同学们学了EditText控件,又用其实践做了个验证码功能,以为这就完了吗?然而并没有。Android在5.0以后引入了Mat
- 四道Java基础题,你能对几道?一、==符的使用首先看一段比较有意思的代码Integer a = 1000,b=1000; Integer
- 项目源码:https://gitee.com/tanwubo/jwt-spring-security-demo登录通过自定义的WxApple
- 一.导入方式由于jdk中没有servlet对应的jar包,所以需要咱们手动引入,有两种方式:1.可以采取向lib目录导入servlet-ap
- 1.IO流介绍IO流可以用到的地方很多,就比如设计模式、下载、传输等等。学好IO流,为之后的进一步学习打下基础,那么,先来说说什么是流?流是
- Android实现TextView超链接一共有五种方式:推荐第四种、第五种1. 直接在xml文件中配置autoLink属性(简单易用,效果单
- 序言for循环语句是java循环语句中最常用的循环语句,一般用在循环次数已知的情况下使用。for循环语句的语法格式如下:java语言 for
- 为了能正常输出XML格式的内容,必须要对不被XML允许的那些特殊字符进行转换。本文介绍的正是如何使用C#判断XML字符串是否含特殊字符并进行
- 前言 实际业务开发中,集合的判断和操作也是经常
- 在Java的逻辑运算符中,有这么四类:&&(短路与),&,|,||(短路或)。&&和&都是表
- 这里我记录一个比较简单方便操作的JAVA上传文件图片到服务器并且保存,具体内容如下首先是页面html的 我这是提交一
- Dockerfile 构建java web 环境Dockfile 介绍:Dockfile是一种被Docker程序解释的脚本,Dockerfi
- 先上效果图: 工具类在解析的过程中,我们会和byte做各种运算,所以我定义了一个byte工具类ByteUtils:using Sy