单链表
链表是有序列表，它在内存中是存储如下：
上图的表格来模拟链表的结构，其中每一行为一个节点（以第一行举例110，a2,180）。
- ‘data域’用来存放数据
- ‘next域’用来指向下一个节点。
- ‘头指针（也成为头节点）’，150是指向表格中第五行的‘地址为150’的a1节点。而‘next域’110指向 a2节点
小结
- 1.链表是以节点方式来存储，是链式存储。
- 2.每个节点包含‘data域’，‘next域’。
- 3.如图：发现链表的各个节点不一定是连续存放的。
- 4.链表分带‘头节点’，和‘没有带头节点的’链表，根据实际的需求来确定。
单链表介绍
单链表（带头节点）逻辑结构示意图如下：
最后一个节点的‘next域’为空。
单链表的应用
使用带head头的单项链表实现，对数据的增删改查操作。
- 第一种方法在添加数据时，直接添加到链表的尾部
- 第二种方法在添加数据时，根据排序将数据插入到指定位置。（如果这个位置被占用，则添加失败并给出提示）
代码实现思路：
添加（创建）
- 1.先创建一个head头节点，作用就是表示单链表的头
- 2.后面我们每加一个节点，就直接假如到链表的最后
遍历：
- 1.通过一个辅助变量遍历，帮助遍历整个单链表
数据结构定义
public class DataNode
{
public int Id { get; set; }
public string Name { get; set; }
public string NikeName { get; set; }
public DataNode Node { get; set; }
public DataNode(int id, string name, string nikeName)
{
Id = id;
Name = name;
NikeName = nikeName;
}
public override string ToString()
{
return $"DataNode[{Id},{Name},{NikeName}]";
}
}public class SingleLinkedList
{
/*
* 定义一个头节点，保证不要改动它因为被修改之后就找不到链表的最顶端。
* 先初始化一个头节点，头节点不要动，不存放具体的数据
*/
private DataNode head = new DataNode(0,"","");
/*
* 当不考虑编号的顺序时
* 1.找到当前链表的最后节点
* 2.将最后这个节点的next域指向新的节点即可
*/
public void Add(DataNode node)
{
//因为head节点不能改动，因此我们需要一个辅助变量辅助遍历temp
DataNode temp = head;
//遍历链表，找到最后
while (true)
{
//找到链表的最后
if (temp.NextNode == null)
{
break;
}
//如果没有找到则后移
temp = temp.NextNode;
}
//当推出while循环时，temp就指向了链表的最后
//将最后这个节点的next指向新的节点
temp.NextNode = node;
}
//显示链表（遍历）
public void List()
{
if (head.NextNode == null)
{
Console.WriteLine("链表为空");
return;
}
//因为头节点不能改动，因此我们需要一个辅助变量来遍历
DataNode temp = head.NextNode;
while (true)
{
//判断是否到链表最后
if (temp == null)
{
break;
}
//输出节点信息
Console.WriteLine(temp);
//将next后移，一定记住需要后移。不然就是死循环
temp = temp.NextNode;
}
}
}1.添加
class Program
{
static void Main(string[] args)
{
var node1 = new DataNode(1,"法外狂徒张三","三哥");
var node2 = new DataNode(2, "隔壁李四", "四哥");
var node3 = new DataNode(3, "楼下王五", "五哥");
var node4 = new DataNode(4, "同学老六", "六哥");
var list = new SingleLinkedList();
list.Add(node1);
list.Add(node2);
list.Add(node3);
list.Add(node4);
list.List();
}
}
如果当我们把list.add的添加顺序修改一下。会发现：
class Program
{
static void Main(string[] args)
{
var node1 = new DataNode(1,"法外狂徒张三","三哥");
var node2 = new DataNode(2, "隔壁李四", "四哥");
var node3 = new DataNode(3, "楼下王五", "五哥");
var node4 = new DataNode(4, "同学老六", "六哥");
var list = new SingleLinkedList();
list.Add(node1);
list.Add(node4);
list.Add(node2);
list.Add(node3);
list.List();
}
}
目前这种写法是按照添加顺序来显示的，add时并没有考虑编号。接下来将继续演示：
- 不管如何顺序的add，都要按照顺序排名（指定位置）来添加节点数据。
分析
需要按照变化的顺序添加
- 1.首先找到新添加的节点的位置，时通过辅助变量（指针）；通过遍历搞定
- 2.新的节点next域=temp.next
- 3.将temp.next = 新的节点
代码如下：
/*
* 第二种方式在添加节点时，根据排名将节点插入到指定位置
* 如果有这个排名，则添加失败并提示
*/
public void AddNodeByOrder(DataNode node)
{
//因为头节点不能东，因此我们仍然通过一个辅助变量来帮助找到添加的位置
//因为单链表，因此我们找的tmep是位于添加位置的前一个节点，否则插入不了
DataNode temp = head;
bool flag = false;//标识添加的编号是否存在，默认为false
while (true)
{
if (temp.NextNode == null)
{
//说明temp已经在链表的最后
break;
}
if (temp.NextNode.Id > node.Id)
{
//位置找到，就在temp的后面插入
break;
}
else if(temp.NextNode.Id == node.Id)
{
//说明希望添加的datanode的编号已经存在
flag = true;//说明编号存在
break;
}
//后移，遍历当前的链表
temp = temp.NextNode;
}
//判断flag的值
if (flag)
{
//不能添加，说明编号已经存在
Console.WriteLine($"准备插入的节点编号{node.Id}已经存在");
}
else
{
//插入到链表中，temp的后面
node.NextNode = temp.NextNode;
temp.NextNode = node;
}
}调用
class Program
{
static void Main(string[] args)
{
var node1 = new DataNode(1,"法外狂徒张三","三哥");
var node2 = new DataNode(2, "隔壁李四", "四哥");
var node3 = new DataNode(3, "楼下王五", "五哥");
var node4 = new DataNode(4, "同学老六", "六哥");
var list = new SingleLinkedList();
/* list.Add(node1);
list.Add(node4);
list.Add(node2);
list.Add(node3);*/
list.AddNodeByOrder(node1);
list.AddNodeByOrder(node4);
list.AddNodeByOrder(node2);
list.AddNodeByOrder(node3);
list.List();
}
}
然后我们再测试一下添加重复节点的效果：
class Program
{
static void Main(string[] args)
{
var node1 = new DataNode(1,"法外狂徒张三","三哥");
var node2 = new DataNode(2, "隔壁李四", "四哥");
var node3 = new DataNode(3, "楼下王五", "五哥");
var node4 = new DataNode(4, "同学老六", "六哥");
var list = new SingleLinkedList();
/* list.Add(node1);
list.Add(node4);
list.Add(node2);
list.Add(node3);*/
list.AddNodeByOrder(node1);
list.AddNodeByOrder(node4);
list.AddNodeByOrder(node2);
list.AddNodeByOrder(node3);
list.AddNodeByOrder(node3);
list.List();
}
}
2.修改
/*
* 修改节点的信息，根据编号来修改，即编号不能改
* 说明：
* 1.根据NewDataNode的id来修改即可
*/
public void Update(DataNode node)
{
//判断链表是否空
if (head.NextNode == null)
{
Console.WriteLine("链表为空");
return;
}
//找到需要修改的节点，根据id
//先顶一个一个辅助变量
DataNode temp = head.NextNode;
bool flag = false;//表示是否找到该节点
while (true)
{
if (temp == null)
{
break;//已经遍历完链表
}
if (temp.Id == node.Id)
{
//找到了
flag = true;
break;
}
temp = temp.NextNode;
}
//根据flag判断是否找到要修改的节点
if (flag)
{
temp.Name = node.Name;
temp.NikeName = node.NikeName;
}
else
{
//没有找到
Console.WriteLine($"没有找到编号的节点，不能修改{node.Id}");
}
}class Program
{
static void Main(string[] args)
{
var node1 = new DataNode(1,"法外狂徒张三","三哥");
var node2 = new DataNode(2, "隔壁李四", "四哥");
var node3 = new DataNode(3, "楼下王五", "五哥");
var node4 = new DataNode(4, "同学老六", "六哥");
var list = new SingleLinkedList();
/* list.Add(node1);
list.Add(node4);
list.Add(node2);
list.Add(node3);*/
list.AddNodeByOrder(node1);
list.AddNodeByOrder(node4);
list.AddNodeByOrder(node2);
list.AddNodeByOrder(node3);
list.List();
Console.WriteLine();
//修改节点
var newNode = new DataNode(2, "Juster", "Justerter!!!");
list.Update(newNode);
list.List();
}
}
3.删除
从单链表删除一个节点的思路
- 1.先找到需要删除的节点的，前一个节点temp
- 2.temp.next = temp.next.next
- 3.被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收
删除1号
class Program
{
static void Main(string[] args)
{
var node1 = new DataNode(1,"法外狂徒张三","三哥");
var node2 = new DataNode(2, "隔壁李四", "四哥");
var node3 = new DataNode(3, "楼下王五", "五哥");
var node4 = new DataNode(4, "同学老六", "六哥");
var list = new SingleLinkedList();
/* list.Add(node1);
list.Add(node4);
list.Add(node2);
list.Add(node3);*/
list.AddNodeByOrder(node1);
list.AddNodeByOrder(node4);
list.AddNodeByOrder(node2);
list.AddNodeByOrder(node3);
list.List();
Console.WriteLine();
//修改节点
//var newNode = new DataNode(2, "Juster", "Justerter!!!");
//list.Update(newNode);
//删除节点
list.Delete(1);
list.List();
}
}
全部删除
class Program
{
static void Main(string[] args)
{
var node1 = new DataNode(1,"法外狂徒张三","三哥");
var node2 = new DataNode(2, "隔壁李四", "四哥");
var node3 = new DataNode(3, "楼下王五", "五哥");
var node4 = new DataNode(4, "同学老六", "六哥");
var list = new SingleLinkedList();
/* list.Add(node1);
list.Add(node4);
list.Add(node2);
list.Add(node3);*/
list.AddNodeByOrder(node1);
list.AddNodeByOrder(node4);
list.AddNodeByOrder(node2);
list.AddNodeByOrder(node3);
list.List();
Console.WriteLine();
//修改节点
//var newNode = new DataNode(2, "Juster", "Justerter!!!");
//list.Update(newNode);
//删除节点
list.Delete(1);
list.Delete(4);
list.Delete(2);
list.Delete(3);
list.List();
}
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
