目录
②增加元素的方法:因为是单链表,所以增加元素一定是只能在末尾添加元素,即在头结点后面添加元素
前置知识:
数据结构:
数据结构:数据元素之间的相互关系
常用的数据结构
数组、链表、栈、队列、树、图,堆,散列表
线性表:
线性表是一种数据结构是由n个具有相同特性的数据元素的有限序列
例如:数组、链表、栈、队列,ArrayList
顺序存储:
数组、Stack、Queue、ArrayList->顺序存储
只是 数组、Stack、Queue、ArrayList的组织规则不同而已
顺序存储
用一组地址连续的存储单元依次存储线性表的各个元素,数据元素之间的逻辑关系由存储单元的邻接关系来体现。内存地址连续,一整片的内存
顺序存储和链式存储 是数据结构中的两种存储方式
链式存储:
单向链表、双向链表、循环链表->链式存储
链式存储(链接存储)
用一组任意的存储单元存储线性表中的各个数据元素,内存地址不连续跳跃式的。
如需了解更多,可看这一篇文章:
好的,回归主线,今天咱们学习的重点是单向链表以及双向链表,循环链表。
一、链表中的结点类LinkedNode
什么是LinkedNode呢,他有什么作用呢?他其实就是组成链表的基本单位,链表就是一个个的LinkedNode串起来的,只不过串的方式不太一样。下面代码示例中不一定使用的是LinkedNode这个名字,使用的是其他的名字不过没关系,学习而已。例如:
在单向链表中:每个链表结点有一个指向下一个链表结点的类似于C语言中的指针的东西,就是说明了,当前节点的下一个就是你,二者建立了联系。对于单向链表中,第一个结点,我们称之为头结点,因为他只能向后指,不能朝前看,所以每次寻找某一个元素,需要进行遍历,而且你永远找不到自己的上一个元素是什么。于是有了双向链表。
在双向链表中:每个链表节点存有两个指针,一个是指向当前结点的上一个结点,一个是指向当前结点的下一个结点,其余的和单向链表相同。
所谓循环链表:就是在单链表中,将最后一个结点的下一个指向第一个结点。
好的,接下来我们实现这个节点类:
单向链表的节点类:
两种定义方式:
1、申明字段节点类:
/// <summary>
/// 单向链表节点定义(字段版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class ListNode_Field<T>
{
// 节点存储的数据(字段)
public T data;
// 指向下一个节点的指针(字段)
// "?" 表示这是一个可空类型,允许值为 null
public ListNode_Field<T>? next;
/// <summary>
/// 构造函数
/// </summary>
/// <param name="val">节点数据</param>
public ListNode_Field(T val)
{
data = val;
next = null;
}
}
2、申明属性节点类:
/// <summary>
/// 单向链表节点定义(属性版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class SingleListNode<T>
{
// 节点存储的数据(属性)
public T Data { get; set; }
// 指向下一个节点的指针(属性)
// "?" 表示这是一个可空类型,允许值为 null
public SingleListNode<T>? Next { get; set; }
/// <summary>
/// 构造函数
/// </summary>
/// <param name="data">节点数据</param>
public SingleListNode(T data)
{
Data = data;
Next = null; // 初始化时指针置空
}
}
这两种方式任意选择一种进行申明即可,推荐使用属性,因为可以自己处理的手段更多。
二、两种方式实现单向链表
好的接下来我们实现一个单向链表,因为有了这些基本节点类,所以才会有下面的代码。同样我们会使用属性节点类和字段节点类进行说明。其实都差不多的。
总的设计思路:
1、提供一个头结点
2、利用这个头结点进行增删改查
接下来我们一一实现:下面是一个利用字段节点声明的单向链表
①定框架:
public class SingleLinkedList_Field<T>
{
//设置一个私有头结点
private ListNode_Field<T>? head;
}
②增加元素的方法:因为是单链表,所以增加元素一定是只能在末尾添加元素,即在头结点后面添加元素
步骤:
(1)先申明一个新的节点
(2)判断头结点是否为空,为空则添加的元素就是头结点元素,反之遍历找到最后一个节点,然后将最后一个结点的next指向当前新创造的节点
/// <summary>
/// 在链表尾部添加新节点
/// </summary>
public void Add(T data)
{
ListNode_Field<T> newNode = new ListNode_Field<T>(data);
if (head == null)
{
head = newNode;
return;
}
// 遍历链表找到最后一个节点
ListNode_Field<T> current = head;
while (current.next != null)
{
current = current.next;
}
current.next = newNode; // 直接操作字段
}
当然这个添加元素,你也可以想想怎么在中间插入一个元素,思想是将上一个的next指向插入元素,插入元素的next指向上一个元素的下一个
③删除元素的方法:删除链表中第一个符合删除目标值的节点
步骤:
(1)先看有没有头结点,没有头结点删除个屁啊
(2)然后看删除的是不是头结点,是的话直接将头结点的next指向下一个就好啦
(3)不是头结点的话,就稍微有一点点麻烦,需要先遍历,和Add方法差不多的
/// <summary>
/// 删除第一个匹配的节点
/// </summary>
public bool Remove(T data)
{
if (head == null) return false;
// 处理头节点匹配的情况
if (head.data != null && head.data.Equals(data))
{
head = head.next; // 直接操作字段
return true;
}
ListNode_Field<T> current = head;
while (current.next != null)
{
if (current.next.data != null && current.next.data.Equals(data))
{
current.next = current.next.next; // 直接操作字段
return true;
}
current = current.next;
}
return false;
}
④查找节点是否存在,这个就很简单,直接遍历一遍就好了。
/// <summary>
/// 查找节点是否存在
/// </summary>
public bool Contains(T data)
{
ListNode_Field<T>? current = head;
while (current != null)
{
if (current.data != null && current.data.Equals(data))
{
return true;
}
current = current.next;
}
return false;
}
⑤更新某一个节点的数据
步骤:
(1)找到该节点
(2)操作该节点的数据
/// <summary>
/// 更新第一个匹配的节点的值
/// </summary>
public bool Update(T oldData, T newData)
{
ListNode_Field<T>? node = FindNode(oldData);
if (node == null) return false;
node.data = newData; // 直接操作字段
return true;
}
/// <summary>
/// 辅助方法:查找指定数据的节点
/// </summary>
private ListNode_Field<T>? FindNode(T data)
{
ListNode_Field<T>? current = head;
while (current != null)
{
if (current.data != null && current.data.Equals(data))
{
return current;
}
current = current.next;
}
return null;
}
好的,那么我们就完成了一个最简单的单向链表的数据结构!
附上使用属性申明的单行链表,是一样的:
/// <summary>
/// 单向链表实现(属性版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class SingleLinkedList_Property<T> : ISingleLinkedList<T>
{
// 头节点(私有属性)
private SingleListNode<T>? head;
/// <summary>
/// 在链表尾部添加新节点
/// </summary>
/// <param name="data">要添加的数据</param>
public void Add(T data)
{
// 显式声明类型(不使用 var)
SingleListNode<T> newNode = new SingleListNode<T>(data);
if (head == null)
{
head = newNode; // 链表为空时,新节点作为头节点
return;
}
// 遍历链表找到最后一个节点
SingleListNode<T> current = head;
while (current.Next != null)
{
current = current.Next;
}
current.Next = newNode; // 将新节点链接到尾部
}
/// <summary>
/// 删除第一个匹配的节点
/// </summary>
/// <param name="data">要删除的数据</param>
/// <returns>是否删除成功</returns>
public bool Remove(T data)
{
if (head == null) return false;
// 处理头节点匹配的情况
if (head.Data != null && head.Data.Equals(data))
{
head = head.Next; // 头节点指向下一个节点
return true;
}
// 遍历链表查找匹配的节点
SingleListNode<T> current = head;
while (current.Next != null)
{
if (current.Next.Data != null && current.Next.Data.Equals(data))
{
current.Next = current.Next.Next; // 跳过匹配的节点
return true;
}
current = current.Next;
}
return false;
}
/// <summary>
/// 查找节点是否存在
/// </summary>
/// <param name="data">要查找的数据</param>
/// <returns>是否存在</returns>
public bool Contains(T data)
{
SingleListNode<T>? current = head;
while (current != null)
{
if (current.Data != null && current.Data.Equals(data))
{
return true;
}
current = current.Next;
}
return false;
}
/// <summary>
/// 更新第一个匹配的节点的值
/// </summary>
/// <param name="oldData">旧数据</param>
/// <param name="newData">新数据</param>
/// <returns>是否更新成功</returns>
public bool Update(T oldData, T newData)
{
SingleListNode<T>? node = FindNode(oldData);
if (node == null) return false;
node.Data = newData; // 直接修改节点的数据
return true;
}
/// <summary>
/// 辅助方法:查找指定数据的节点
/// </summary>
private SingleListNode<T>? FindNode(T data)
{
SingleListNode<T>? current = head;
while (current != null)
{
if (current.Data != null && current.Data.Equals(data))
{
return current;
}
current = current.Next;
}
return null;
}
}
三、测试
测试部分呢,因为两种都差不多,所以我们使用一个接口,让他们都实现里面的方法,然后统一测试
测试接口:
/// <summary>
/// 统一接口(便于测试不同版本的链表)
/// </summary>
public interface ISingleLinkedList<T>
{
void Add(T data);
bool Remove(T data);
bool Contains(T data);
bool Update(T oldData, T newData);
}
两个链表只要继承了这个接口就好
写一个测试函数:
static void TestLinkedList<T>(T list) where T : ISingleLinkedList<int>
{
// 添加节点
list.Add(1);
list.Add(2);
list.Add(3);
Console.WriteLine("添加 1, 2, 3 后链表内容应为:1 -> 2 -> 3");
// 测试查找
Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 True
Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 False
// 测试删除
list.Remove(2);
Console.WriteLine("删除 2 后链表内容应为:1 -> 3");
Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 False
// 测试更新
list.Update(3, 4);
Console.WriteLine("更新 3 为 4 后链表内容应为:1 -> 4");
Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 True
}
开始测试:
static void Main(string[] args)
{
// 测试属性版本链表
Console.WriteLine("测试属性版本链表:");
TestLinkedList(new SingleLinkedList_Property<int>());
// 测试字段版本链表
Console.WriteLine("\n测试字段版本链表:");
TestLinkedList(new SingleLinkedList_Field<int>());
}
测试结果:
如果再讲双向链表和循环链表,会显得很杂乱,我们将会在下一篇文章讨论,诸位共勉!
附:本文所有代码
namespace 单向链表
{
/// <summary>
/// 单向链表节点定义(属性版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class SingleListNode<T>
{
// 节点存储的数据(属性)
public T Data { get; set; }
// 指向下一个节点的指针(属性)
// "?" 表示这是一个可空类型,允许值为 null(解决 CS8618 警告)
public SingleListNode<T>? Next { get; set; }
/// <summary>
/// 构造函数
/// </summary>
/// <param name="data">节点数据</param>
public SingleListNode(T data)
{
Data = data;
Next = null; // 初始化时指针置空
}
}
/// <summary>
/// 单向链表节点定义(字段版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class ListNode_Field<T>
{
// 节点存储的数据(字段)
public T data;
// 指向下一个节点的指针(字段)
// "?" 表示这是一个可空类型,允许值为 null
public ListNode_Field<T>? next;
/// <summary>
/// 构造函数
/// </summary>
/// <param name="val">节点数据</param>
public ListNode_Field(T val)
{
data = val;
next = null;
}
}
internal class Program
{
static void Main(string[] args)
{
// 测试属性版本链表
Console.WriteLine("测试属性版本链表:");
TestLinkedList(new SingleLinkedList_Property<int>());
// 测试字段版本链表
Console.WriteLine("\n测试字段版本链表:");
TestLinkedList(new SingleLinkedList_Field<int>());
}
static void TestLinkedList<T>(T list) where T : ISingleLinkedList<int>
{
// 添加节点
list.Add(1);
list.Add(2);
list.Add(3);
Console.WriteLine("添加 1, 2, 3 后链表内容应为:1 -> 2 -> 3");
// 测试查找
Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 True
Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 False
// 测试删除
list.Remove(2);
Console.WriteLine("删除 2 后链表内容应为:1 -> 3");
Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 False
// 测试更新
list.Update(3, 4);
Console.WriteLine("更新 3 为 4 后链表内容应为:1 -> 4");
Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 True
}
}
/// <summary>
/// 统一接口(便于测试不同版本的链表)
/// </summary>
public interface ISingleLinkedList<T>
{
void Add(T data);
bool Remove(T data);
bool Contains(T data);
bool Update(T oldData, T newData);
}
/// <summary>
/// 单向链表实现(属性版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class SingleLinkedList_Property<T> : ISingleLinkedList<T>
{
// 头节点(私有属性)
private SingleListNode<T>? head;
/// <summary>
/// 在链表尾部添加新节点
/// </summary>
/// <param name="data">要添加的数据</param>
public void Add(T data)
{
// 显式声明类型(不使用 var)
SingleListNode<T> newNode = new SingleListNode<T>(data);
if (head == null)
{
head = newNode; // 链表为空时,新节点作为头节点
return;
}
// 遍历链表找到最后一个节点
SingleListNode<T> current = head;
while (current.Next != null)
{
current = current.Next;
}
current.Next = newNode; // 将新节点链接到尾部
}
/// <summary>
/// 删除第一个匹配的节点
/// </summary>
/// <param name="data">要删除的数据</param>
/// <returns>是否删除成功</returns>
public bool Remove(T data)
{
if (head == null) return false;
// 处理头节点匹配的情况
if (head.Data != null && head.Data.Equals(data))
{
head = head.Next; // 头节点指向下一个节点
return true;
}
// 遍历链表查找匹配的节点
SingleListNode<T> current = head;
while (current.Next != null)
{
if (current.Next.Data != null && current.Next.Data.Equals(data))
{
current.Next = current.Next.Next; // 跳过匹配的节点
return true;
}
current = current.Next;
}
return false;
}
/// <summary>
/// 查找节点是否存在
/// </summary>
/// <param name="data">要查找的数据</param>
/// <returns>是否存在</returns>
public bool Contains(T data)
{
SingleListNode<T>? current = head;
while (current != null)
{
if (current.Data != null && current.Data.Equals(data))
{
return true;
}
current = current.Next;
}
return false;
}
/// <summary>
/// 更新第一个匹配的节点的值
/// </summary>
/// <param name="oldData">旧数据</param>
/// <param name="newData">新数据</param>
/// <returns>是否更新成功</returns>
public bool Update(T oldData, T newData)
{
SingleListNode<T>? node = FindNode(oldData);
if (node == null) return false;
node.Data = newData; // 直接修改节点的数据
return true;
}
/// <summary>
/// 辅助方法:查找指定数据的节点
/// </summary>
private SingleListNode<T>? FindNode(T data)
{
SingleListNode<T>? current = head;
while (current != null)
{
if (current.Data != null && current.Data.Equals(data))
{
return current;
}
current = current.Next;
}
return null;
}
}
/// <summary>
/// 单向链表实现(字段版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class SingleLinkedList_Field<T> :ISingleLinkedList<T>
{
// 头节点(私有字段)
private ListNode_Field<T>? head;
/// <summary>
/// 在链表尾部添加新节点
/// </summary>
public void Add(T data)
{
ListNode_Field<T> newNode = new ListNode_Field<T>(data);
if (head == null)
{
head = newNode;
return;
}
// 遍历链表找到最后一个节点
ListNode_Field<T> current = head;
while (current.next != null)
{
current = current.next;
}
current.next = newNode; // 直接操作字段
}
/// <summary>
/// 删除第一个匹配的节点
/// </summary>
public bool Remove(T data)
{
if (head == null) return false;
// 处理头节点匹配的情况
if (head.data != null && head.data.Equals(data))
{
head = head.next; // 直接操作字段
return true;
}
ListNode_Field<T> current = head;
while (current.next != null)
{
if (current.next.data != null && current.next.data.Equals(data))
{
current.next = current.next.next; // 直接操作字段
return true;
}
current = current.next;
}
return false;
}
/// <summary>
/// 查找节点是否存在
/// </summary>
public bool Contains(T data)
{
ListNode_Field<T>? current = head;
while (current != null)
{
if (current.data != null && current.data.Equals(data))
{
return true;
}
current = current.next;
}
return false;
}
/// <summary>
/// 更新第一个匹配的节点的值
/// </summary>
public bool Update(T oldData, T newData)
{
ListNode_Field<T>? node = FindNode(oldData);
if (node == null) return false;
node.data = newData; // 直接操作字段
return true;
}
/// <summary>
/// 辅助方法:查找指定数据的节点
/// </summary>
private ListNode_Field<T>? FindNode(T data)
{
ListNode_Field<T>? current = head;
while (current != null)
{
if (current.data != null && current.data.Equals(data))
{
return current;
}
current = current.next;
}
return null;
}
}
}