C#数据结构03_单链表
C#实现单链表
·
说明
（此系列帖子记录数据结构学习成果,如侵犯视频作者权益，立删)
视频链接: 离忧夏天C#数据结构
了解链表
单链表属于链式存储方式，用于存储一系列元素，与数组不同的地方在于，链表是通过指针来链接存储在内存中的各个独立节点。
在C#中,链表之间是通过引用相互关联起来的
图示：
链表的结构组成
在单链表中，每个元素都封装在一个称为节点Node的结构中，节点包含两部分：
- 数据域：用于存放节点中包含的元素
- 指针域：存放一个指针，用于指向下一个节点(实际存储的下一个节点在内存中的地址)
在链表中，起始点叫做头结点(Head)，而尾结点通常指向null，表示链表的结束。
单链表的基本实现
单链表的实现通常涉及两个类：
一个是 Node 类，定义节点的结构；
另一个是 LinkedList 类，它管理节点的集合，提供各种操作方法，比如添加、删除和查找节点。
这里我们把Node类放入LinkedList类中便于观察
public T data; //数据域
public Node next; //指针域
(这里的next设置为Node类型,是因为我们需要在这个节点知道下一个节点的位置，每一个节点其实都是Node类的一个实例，因此我们的next存储的是下一个节点的实例)
链表的基本结构Node类
private class Node
{
public T data; //实际存储的数据
public Node next; //指向下一个节点的引用
public Node(T data,Node next)
{
this.data = data;
this.next = next;
}
//默认构造函数
public Node(T data)
{
this.data = data;
this.next = null;
}
public override string ToString()
{
return data.ToString();
}
}
链表的基本结构LinkedList类
class LinkedList01<T>
{
private Node head; //头节点
private int size; //链表长度
//默认构造函数,head->null
public LinkedList01()
{
head = null;
size = 0;
}
//定义属性,获取链表长度
public int Count => size;
//判断链表是否为空
public bool IsEmpty => size == 0;
//重写ToString用于测试
public override string ToString()
{
StringBuilder sb = new StringBuilder();
Node cur = head;
while (cur != null)
{
sb.Append(cur.data + "->");
cur = cur.next;
}
sb.Append("NULL");
return sb.ToString();
}
}
链表的基本操作
增
对于链表的插入,我们只讲解插入的操作，首先需要将要pre指向我们插入的位置，Node就是我们需要插入的节点，Pre是插入位置的前一个节点，这里必须严格执行①，是因为如果先执行②会导致pre.next直接指向Node节点，从而导致失去指向C节点的指针。
public void Add(int index ,T data)
{
if (index < 0 || index > size)
throw new ArgumentException("非法索引");
//操作索引为0
if (index == 0)
{
Node node = new Node(data);
node.next = head;
head = node;
//既head = new Node(data,head);
}
else
{
Node pre = head;
//让pre指向插入位置
for (int i = 0; i < index-1; i++)
pre = pre.next;
Node node = new Node(data);
node.next = pre.next;
pre.next = node;
}
size++;
}
//头尾添加
public void AddFirst(T data) => Add(0, data);
public void AddLast(T data) => Add(size, data);
查，改
//查找元素(依据索引)
public T Get(int index)
{
if (index < 0 || index >= size)
throw new ArgumentException("非法索引");
Node cur = head;
for (int i = 0; i < index; i++)
cur = cur.next;
return cur.data;
}
//获取头尾元素
public T GetFirst() => Get(0);
public T GetLast() => Get(size - 1);
//修改元素
public void Set(int index, T newData)
{
if (index < 0 || index >= size)
throw new ArgumentException("非法索引");
Node cur = head;
for (int i = 0; i < index; i++)
cur = cur.next;
cur.data = newData;
}
//是否包含元素
public bool Contains(T data)
{
Node cur = head;
while (cur != null)
{
if(cur.data.Equals(data))
return true;
cur = cur.next;
}
return false;
}
删
//删除元素(根据索引)
public T RemoveAt(int index)
{
if (index < 0 || index >= size)
throw new ArgumentException("非法索引");
//删除头结点
if(index == 0)
{
Node delNode = head;
head = head.next;
size--;
return delNode.data;
}
else
{
Node pre = head;
for (int i = 0; i < index - 1; i++)
pre = pre.next;
Node delNode = pre.next;
pre.next = delNode.next;
size--;
return delNode.data;
}
}
//删除头尾
public T RemoveFirst() => RemoveAt(0);
public T RemoveLast() => RemoveAt(size - 1);
//通过查找元素删除
public void Remove(T data)
{
//空链直接退出
if (head == null)
return;
//判断头结点是否为data
if(head.data.Equals(data))
{
head = head.next;
size--;
}
else
{
Node cur = head; //指向头结点
Node pre = null; //指向待删除结点
while (cur != null)
{
if(cur.data.Equals(data))
break; //找到data,退出循环
pre = cur;
cur = cur.next;
}
if(cur != null)
{
pre.next = pre.next.next;
size--;
}
}
}
总代码
using System;
using System.Text;
namespace DataStructure
{
public class LinkedList01<T>
{
private class Node
{
public T data; //实际存储的数据
public Node next; //指向下一个节点的引用
public Node(T data,Node next)
{
this.data = data;
this.next = next;
}
//默认构造函数
public Node(T data)
{
this.data = data;
this.next = null;
}
public override string ToString()
{
return data.ToString();
}
}
private Node head; //头节点
private int size; //链表长度
//默认构造函数,head->null
public LinkedList01()
{
head = null;
size = 0;
}
//定义属性,获取链表长度
public int Count => size;
//判断链表是否为空
public bool IsEmpty => size == 0;
//添加元素
public void Add(int index ,T data)
{
if (index < 0 || index > size)
throw new ArgumentException("非法索引");
//操作索引为0
if (index == 0)
{
Node node = new Node(data);
node.next = head;
head = node;
//既head = new Node(data,head);
}
else
{
Node pre = head;
//让pre指向插入位置
for (int i = 0; i < index-1; i++)
pre = pre.next;
Node node = new Node(data);
node.next = pre.next;
pre.next = node;
}
size++;
}
//头尾添加
public void AddFirst(T data) => Add(0, data);
public void AddLast(T data) => Add(size, data);
//删除元素(根据索引)
public T RemoveAt(int index)
{
if (index < 0 || index >= size)
throw new ArgumentException("非法索引");
//删除头结点
if(index == 0)
{
Node delNode = head;
head = head.next;
size--;
return delNode.data;
}
else
{
Node pre = head;
for (int i = 0; i < index - 1; i++)
pre = pre.next;
Node delNode = pre.next;
pre.next = delNode.next;
size--;
return delNode.data;
}
}
//删除头尾
public T RemoveFirst() => RemoveAt(0);
public T RemoveLast() => RemoveAt(size - 1);
//通过查找元素删除
public void Remove(T data)
{
//空链直接退出
if (head == null)
return;
//判断头结点是否为data
if(head.data.Equals(data))
{
head = head.next;
size--;
}
else
{
Node cur = head; //指向头结点
Node pre = null; //指向待删除结点
while (cur != null)
{
if(cur.data.Equals(data))
break; //找到data,退出循环
pre = cur;
cur = cur.next;
}
if(cur != null)
{
pre.next = pre.next.next;
size--;
}
}
}
//查找元素(依据索引)
public T Get(int index)
{
if (index < 0 || index >= size)
throw new ArgumentException("非法索引");
Node cur = head;
for (int i = 0; i < index; i++)
cur = cur.next;
return cur.data;
}
//获取头尾元素
public T GetFirst() => Get(0);
public T GetLast() => Get(size - 1);
//修改元素
public void Set(int index, T newData)
{
if (index < 0 || index >= size)
throw new ArgumentException("非法索引");
Node cur = head;
for (int i = 0; i < index; i++)
cur = cur.next;
cur.data = newData;
}
//是否包含元素
public bool Contains(T data)
{
Node cur = head;
while (cur != null)
{
if(cur.data.Equals(data))
return true;
cur = cur.next;
}
return false;
}
//重写ToString用于测试
public override string ToString()
{
StringBuilder sb = new StringBuilder();
Node cur = head;
while (cur != null)
{
sb.Append(cur.data + "->");
cur = cur.next;
}
sb.Append("NULL");
return sb.ToString();
}
}
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
19
0- 0
已为社区贡献1条内容
所有评论(0)