关于链表的知识整理
什么是链表
链表是物理存储单元上的非连续、非顺序存储结构，数据元素的逻辑顺序通过链表中指针链接的顺序来实现。 链表由一系列节点组成，链表中的每个元素都称为节点，节点可以在运行时动态生成。 每个节点包含两个部分：数据域，用于存储数据元素；指针域，用于存储下一个节点地址。
链表和数组的区别
请回忆一下数组的概念。 数组是具有相同数据类型的元素按一定顺序排列的集合。 根据概念，数组在内存中是连续的，链表是不连续的。由于不同的存储方法，数组静态分配内存，链表动态分配内存，数组元素在堆栈区域，链表元素在堆栈区域数组在内存中是连续的，因此可以利用下标对齐。 时间复杂度为o(1)，链表进行要素定位的时间复杂度为o ) n )； 但是，数组的连续性数组为了插入或删除要素的时间复杂度o(n )，链表的时间复杂度o )1)。 归纳起来，数组和链表的区别如下
1 .数组静态分配内存，链表动态分配内存
2 .数组在内存中是连续的，链表是不连续的
3 .数组元素位于堆栈区域，链表元素位于堆区域
4 .数组用下标对齐，时间复杂度为o(1)，链表为元素的时间复杂度o ) n )；
5 .数组元素的插入或删除的时间复杂度o(n )、链表的时间复杂度o )1)。
实现C#链表的基本操作
以单链表为例，根据链表的定义定义了链表节点的数据结构
公共类节点
{
私有数据；
私有节点下一步；
//带参数的构造函数
//用于实例化主要用例需要处理的节点
公共节点(titem，Node next ) )。
{
数据=项目；
this.next=next；
}
//无参数构造函数，用例实例化节点
公共节点() )
{
DATA=default(t；
next=null；
}
公共节点下一步
{
get { return next； }
set { this.next=value； }
}
公共数据
{
get {返回数据； }
set { this.data=value； }
}
}
其次，实现链表的操作，构建链表。 在构建链表的过程中，我们决定了头节点的对象。 头部节点是一个非常有用的节点，可以在后续代码中慢慢体验
公共类我的链接列表
{
公共节点头{ get }； set； }
//构造函数
公共我的链接列表(
{
头=空；
}
}
1 .求出链表的长度。 思路：从第一个节点向后访问到最后一个节点。 代码如下所示
公共int length (
{
var p=Head；
int len=0；
while(p！=null )
{
len；
p=p.Next；
}
return len；
}
2 .清空链表的话，这个里面会变得简单。 直接将头部节点设置为空就可以了。 代码如下所示
公共void clear (
{
头=空；
}
3 .类似地，用于确定链表是否为空的头节点
公共布尔isempty (
{
if (头==空) )。
{
返回真；
}
else
{
返回假；
}
}
4 .要在链表末尾添加新元素并添加新元素，必须首先确定链表是否为空。 如果为空，则为第一个节点指定值。 如果不为空，则必须修改最后一个节点的next点。 代码如下所示
公共语音应用(titem ) ) ) )。
{
if (头==空) )。
{
头=new node (item，null )；
返回；
}
var p=new Node (；
p=Head；
while(p.next！=null )
{
p=p.Next；
}
p.next=newnode(item，null )；
}
5 .在单链接列表中第I个节点的位置之前插入指定的节点。 必须首先找到要插入的位置，然后修改相邻节点的方向。 代码如下所示
公共void insert (titem，int i ) )。
{
if (isempty (|| i1|) )
{
返回；
}
//如果插入到最初的位置，只需将该节点的next指向head即可
if(I==1) ) )。
{
varfirst=newnode(item，null )；
first.Next=Head；
头=第一；
返回；
}
var p=new Node (；
p=Head；
var left=new Node (；
var right=new Node (；
int j=1；
while(p.next！=null j i )
{
left=p；
right=p.Next；
j；
}
varq=newnode(item，null )；
left.Next=q；
q.Next=right；
}
6 .删除指定节点，找到删除前的节点，修改该节点的next点即可省略代码。 请参阅。 请参阅。 请参阅。
7 .还有删除、获取、检索链表等操作，但基本思想是一样的，不做介绍
链表相关经典主题
1 .求单链表的节点数
2 .翻转单链接列表
3 .查找单链接列表中倒数第k个节点(k 0 )
4 .查找单链表的中间节点
5 .从末尾到末尾打印单链表
6 .已知两个单链表pHead1和pHead2分别有序，将它们合并为一个链表仍然有序
7 .判断单链表中是否有环
8 .判断两个单链表是否相交
9 .求出两个单链表相交的第一个节点
10 .我们知道单链表中存在循环。 求出进入循环的第一个节点
11 .给出单链表的起始指针pHead和节点指针pToBeDeleted，o(1)时间复杂度删除节点pToBeDeleted
是的，到此为止了。 主题是剑指邀请中的主题。 大家解答一下，有问题的话请联系我