【愚公系列】2023年12月 数据结构(二)-链表
【摘要】 数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。
🏆 作者简介，愚公搬代码
🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。
🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。
-
数组（Array）：是一种线性数据结构，它将一组具有相同类型的数据元素存储在一起，并为每个元素分配一个唯一的索引。数组的特点是具有随机访问的能力。
-
链表（Linked List）：也是一种线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。链表的特点是可以动态地插入或删除节点，但访问某个节点时需要从头开始遍历。
-
栈（Stack）：是一种后进先出（LIFO）的数据结构，它只能在栈顶进行插入和删除操作。栈通常用于实现递归算法、表达式求值和内存管理等场景。
-
队列（Queue）：是一种先进先出（FIFO）的数据结构，它可以在队尾插入元素，在队头删除元素。队列通常用于数据的缓存、消息队列和网络通信等场景。
-
哈希表（Hash Table）：也称为散列表，它是一种根据关键字直接访问数据的数据结构。哈希表通常由数组和散列函数组成，可以在常数时间内进行插入、删除和查找操作。
-
树（Tree）：是一种非线性数据结构，它由一系列的节点组成，每个节点可以有若干个子节点。树的特点是可以动态地插入或删除节点，常见的树结构包括二叉树、平衡树和搜索树等。
-
堆（Heap）：是一种特殊的树结构，它通常用于实现优先队列和堆排序等算法。堆分为最大堆和最小堆，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反。
-
图（Graph）：是一种由节点和边组成的非线性数据结构，它可以用来表示各种实体之间的关系，如社交网络、路线图和电路图等。图的遍历和最短路径算法是常见的图算法。
🚀一、链表
🔎1.基本思想
链表是一种常用的数据结构，它的基本思想是以节点为基本元素，每个节点包含两个部分：数据和指针。其中，数据部分用于存储节点所表示的数据，指针部分则用于指向下一个节点。通过节点的指针关系，将一系列的节点连接起来，形成链表。
链表与数组相比，其优势在于具有动态性。链表的节点在内存中是非连续存储的，因此可以在运行时动态地创建和删除节点，而不需要提前分配好固定大小的空间。
在链表中，头节点是链表的第一个节点，尾节点是链表的最后一个节点。链表的遍历可以从头节点开始，依次访问每个节点，并根据指针关系跳转到下一个节点。链表的操作包括插入节点、删除节点、查找节点等。
在实际应用中，链表常用于实现队列、栈、哈希表等数据结构，也经常用于优化算法的时间和空间复杂度。
/* 链表节点类 */
class ListNode {
int val; // 节点值
ListNode next; // 指向下一节点的引用
ListNode(int x) => val = x; //构造函数
}
🔎2.链表常用操作
🦋2.1 初始化链表
1、自定义链表的初始化
/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// 构建引用指向
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
2、内置链表的初始化
当然C#中链表的初始化可以使用LinkedList类。以下是示例代码：
LinkedList<int> list = new LinkedList<int>();
这将创建一个空链表，你可以通过使用AddLast()方法将元素添加到末尾，使用AddFirst()方法将元素添加到开头。你可以使用foreach循环遍历链表中的元素。例如：
list.AddLast(1);
list.AddLast(2);
list.AddFirst(3);
foreach (int item in list)
{
Console.WriteLine(item);
}
这将输出：
3
1
2
🦋2.2 插入节点
1、自定义链表插入节点
/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode n0, ListNode P) {
ListNode? n1 = n0.next;
P.next = n1;
n0.next = P;
}
2、内置链表插入节点
在C#中，可以使用LinkedList<T>类实现链表操作。下面是一个示例代码，演示如何在链表中插入一个节点：
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.AddLast(3);
// 在第二个节点后插入一个新节点
var node = list.Find(2);
list.AddAfter(node, 4);
// 输出整个链表
foreach(var item in list)
{
Console.Write(item + " ");
}
}
}
在上面的代码中，首先创建了一个整型的链表，然后向其中添加了三个节点。接着，通过Find()方法找到链表中的第二个节点，然后调用AddAfter()方法，在该节点后插入了一个新节点。最后遍历整个链表并输出结果。
注：需要添加using System.Collections.Generic;命名空间。
🦋2.3 删除节点
1、自定义链表删除节点
/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode n0) {
if (n0.next == null)
return;
// n0 -> P -> n1
ListNode P = n0.next;
ListNode? n1 = P.next;
n0.next = n1;
}
2、内置链表删除节点
在C#中，可以使用LinkedList<T>类来实现链表操作。以下是删除链表节点的示例代码：
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// 创建链表
LinkedList<int> list = new LinkedList<int>();
// 添加节点
list.AddLast(1);
list.AddLast(2);
list.AddLast(3);
// 输出链表
Console.WriteLine("原始链表:");
foreach (var item in list)
{
Console.Write(item + " ");
}
// 删除第二个节点
LinkedListNode<int> node = list.Find(2);
list.Remove(node);
// 输出删除后的链表
Console.WriteLine("\n删除节点后的链表:");
foreach (var item in list)
{
Console.Write(item + " ");
}
Console.ReadKey();
}
}
在示例中，我们首先创建了一个LinkedList对象，并添加了三个节点。然后，我们使用Find方法查找要删除的节点，并使用Remove方法从链表中删除它。最后，我们输出删除后的链表。
🦋2.4 访问节点
1、自定义链表访问节点
/* 访问链表中索引为 index 的节点 */
ListNode? access(ListNode head, int index) {
for (int i = 0; i < index; i++) {
if (head == null)
return null;
head = head.next;
}
return head;
}
2、内置链表访问节点
可以使用链表的Node类和LinkedList类来访问链表节点。以下是访问链表节点的示例代码：
// 创建一个新的链表
LinkedList<string> linkedList = new LinkedList<string>();
// 在链表末尾添加元素
linkedList.AddLast("first");
linkedList.AddLast("second");
linkedList.AddLast("third");
// 访问链表元素
LinkedListNode<string> currentNode = linkedList.First;
while (currentNode != null)
{
Console.WriteLine(currentNode.Value);
currentNode = currentNode.Next;
}
上面的代码创建了一个新的字符串链表linkedList并向其末尾添加了三个元素。然后，使用linkedList.First方法获取第一个节点，并使用currentNode.Next方法依次访问链表中的所有节点，并使用currentNode.Value方法获取每个节点的值。最后，使用Console.WriteLine()方法将每个节点的值打印到控制台。
🦋2.5 查找节点
1、自定义链表查找节点
/* 在链表中查找值为 target 的首个节点 */
int find(ListNode head, int target) {
int index = 0;
while (head != null) {
if (head.val == target)
return index;
head = head.next;
index++;
}
return -1;
}
2、内置链表查找节点
在 C# 中，可以使用 LinkedList<T> 类来实现链表，并使用 Find() 方法查找节点。
首先需要创建一个 LinkedList 对象，并向其中添加节点，例如：
LinkedList<int> myLinkedList = new LinkedList<int>();
myLinkedList.AddLast(1);
myLinkedList.AddLast(2);
myLinkedList.AddLast(3);
myLinkedList.AddLast(4);
接下来，可以使用 Find() 方法来查找节点。例如，查找值为 3 的节点：
LinkedListNode<int> node = myLinkedList.Find(3);
if (node != null)
{
Console.WriteLine("Node found: " + node.Value);
}
else
{
Console.WriteLine("Node not found.");
}
在这个例子中，Find() 方法将返回一个 LinkedListNode 对象，表示找到的节点。如果该节点不存在，则返回 null。
注意，Find() 方法只会返回第一个找到的符合条件的节点。如果需要查找所有符合条件的节点，可以使用 LINQ 查询语句来实现。
🔎3.常见链表类型
常见链表类型包括：
- 单向链表：每个节点只有一个指针，指向下一个节点。
- 双向链表：每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
- 循环链表：尾节点指针指向头节点，形成一个环形结构。
- 双向循环链表：尾节点的后继节点指向头节点，头节点的前驱节点指向尾节点，形成一个双向循环的环形结构。
- 带头节点的链表：在链表头部添加一个空节点，作为链表的起点。
- 带尾节点的链表：在链表尾部添加一个空节点，作为链表的终点。
- 静态链表：使用数组来实现链表结构，节点间的指针用数组下标来表示。
/* 双向链表节点类 */
class ListNode {
int val; // 节点值
ListNode next; // 指向后继节点的引用
ListNode prev; // 指向前驱节点的引用
ListNode(int x) => val = x; // 构造函数
}
🦋3.1 单链表
//链表类，包含链表定义及基本操作方法
public class MyLinkList<T>
{
private Node<T> head; //单链表的头结点
//头结点属性
public Node<T> Head
{
get
{
return head;
}
set
{
head = value;
}
}
//构造器
public MyLinkList()
{
head = null;
}
//求单链表的长度
public int GetLength()
{
Node<T> p = head;
int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
//清空单链表
public void Clear()
{
head = null;
}
//判断单链表是否为空
public bool IsEmpty()
{
if (head == null)
{
return true;
}
else
{
return false;
}
}
//在单链表的末尾添加新元素
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();
if (head == null)
{
head = q;
return;
}
p = head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
//在单链表的第i个结点的位置前插入一个值为item的结点
public void Insert(T item, int i)
{
if (IsEmpty() || i < 1 || i > GetLength())
{
Console.WriteLine("LinkList is empty or Position is error!");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head;
head = q;
return;
}
Node<T> p = head;
Node<T> r = new Node<T>();
int j = 1;
while (p.Next != null && j < i)
{
r = p;
p = p.Next;
++j;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}
}
//在单链表的第i个结点的位置后插入一个值为item的结点
public void InsertPost(T item, int i)
{
if (IsEmpty() || i < 1 || i > GetLength())
{
Console.WriteLine("LinkList is empty or Position is error!");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
int j = 1;
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;
}
}
//删除单链表的第i个结点
public T Delete(int i)
{
if (IsEmpty() || i < 0 || i > GetLength())
{
Console.WriteLine("LinkList is empty or Position is error!");
return default(T);
}
Node<T> q = new Node<T>();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
int j = 1;
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 " + i + "th node is not exist!");
return default(T);
}
}
//获得单链表的第i个数据元素
public T GetElem(int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("LinkList is empty or position is error! ");
return default(T);
}
Node<T> p = new Node<T>();
p = head;
int j = 1;
while (p.Next != null && j < i)
{
++j;
p = p.Next;
}
if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The " + i + "th node is not exist!");
return default(T);
}
}
//在单链表中查找值为value的结点
public int Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("LinkList is Empty!");
return -1;
}
Node<T> p = new Node<T>();
p = head;
int i = 1;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
++i;
}
return i;
}
//显示链表
public void Display()
{
Node<T> p = new Node<T>();
p = this.head;
while (p != null)
{
Console.Write(p.Data + " ");
p = p.Next;
}
}
}
public class Program
{
static void Main(string[] args)
{
MyLinkList<string> myLinkList = new MyLinkList<string>(); //实例化一个单链表
Console.WriteLine(myLinkList.GetLength()); //获取长度
//添加元素
myLinkList.Append("good");
myLinkList.Append("monring");
myLinkList.Append("lwk");
myLinkList.Insert("!", 5); //在i结点前插元素，位置错误测试
myLinkList.InsertPost("!", 5); //在i结点后插元素，位置错误测试
myLinkList.InsertPost("!", 3); //后插元素
myLinkList.Insert(",", 3); //前插元素
myLinkList.Display(); //显示链表元素
Console.WriteLine(myLinkList.GetElem(4));//获取结点,并显示
myLinkList.Delete(1); //删除结点
myLinkList.Display();
Console.WriteLine(myLinkList.GetLength()); //显示链表长度
Console.Read();
}
}
🦋3.2 双向链表
using System;
using System.Text;
namespace 线性表
{
public class DbLinkList<T> : IListDS<T>
{
private DbNode<T> head;
public DbNode<T> Head
{
get { return head; }
set { head = value; }
}
public DbLinkList()
{
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()
{
DbNode<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)
{
DbNode<T> d = new DbNode<T>(item);
DbNode<T> n = new DbNode<T>();
if (head == null)
{
head = d;
return;
}
n = head;
while (n.Next != null)
{
n = n.Next;
}
n.Next = d;
d.Prev = n;
}
//前插
public void InsertBefore(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
//在最开头插入
if (i == 0)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head;//把"头"改成第二个元素
head.Prev = q;
head = q;//把自己设置为"头"
return;
}
DbNode<T> n = head;
DbNode<T> d = new DbNode<T>();
int j = 0;
//找到位置i的前一个元素d
while (n.Next != null && j < i)
{
d = n;
n = n.Next;
j++;
}
if (n.Next == null) //说明是在最后节点插入(即追加)
{
DbNode<T> q = new DbNode<T>(item);
n.Next = q;
q.Prev = n;
q.Next = null;
}
else
{
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
d.Next = q;
q.Prev = d;
q.Next = n;
n.Prev = q;
}
}
}
/// <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)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head.Next;
head.Next.Prev = q;
head.Next = q;
q.Prev = head;
return;
}
DbNode<T> p = head;
int j = 0;
while (p != null && j < i)
{
p = p.Next;
j++;
}
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = p.Next;
if (p.Next != null)
{
p.Next.Prev = q;
}
p.Next = q;
q.Prev = p;
}
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);
}
DbNode<T> q = new DbNode<T>();
if (i == 0)
{
q = head;
head = head.Next;
head.Prev = null;
return q.Data;
}
DbNode<T> p = head;
int j = 0;
while (p.Next != null && j < i)
{
j++;
q = p;
p = p.Next;
}
if (j == i)
{
p.Next.Prev = q;
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);
}
DbNode<T> p = new DbNode<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;
}
DbNode<T> p = new DbNode<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()
{
DbLinkList<T> result = new DbLinkList<T>();
DbNode<T> t = this.head;
result.Head = new DbNode<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能直接回收
}
//得到某个指定的节点(为了下面测试从后向前遍历)
private DbNode<T> GetNodeAt(int i){
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return null;
}
DbNode<T> p = new DbNode<T>();
p = head;
if (i == 0)
{
return p;
}
int j = 0;
while (p.Next != null && j < i)
{
j++;
p = p.Next;
}
if (j == i)
{
return p;
}
else
{
Console.WriteLine("The node is not exist!");
return null;
}
}
/// <summary>
/// 测试用prev属性从后面开始遍历
/// </summary>
/// <returns></returns>
public string TestPrevErgodic()
{
DbNode<T> tail = GetNodeAt(Count() - 1);
StringBuilder sb = new StringBuilder();
sb.Append(tail.Data.ToString() + ",");
while (tail.Prev != null)
{
sb.Append(tail.Prev.Data.ToString() + ",");
tail = tail.Prev;
}
return sb.ToString().TrimEnd(',');
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
DbNode<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(',');
}
}
}
Console.WriteLine("-------------------------------------");
Console.WriteLine("双链表测试开始...");
DbLinkList<string> dblink = new DbLinkList<string>();
dblink.Head = new DbNode<string>("x");
dblink.InsertBefore("w", 0);
dblink.InsertBefore("v", 0);
dblink.Append("y");
dblink.InsertBefore("z", dblink.Count());
Console.WriteLine(dblink.Count());//5
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink[1]);//w
Console.WriteLine(dblink[0]);//v
Console.WriteLine(dblink[4]);//z
Console.WriteLine(dblink.IndexOf("z"));//4
Console.WriteLine(dblink.RemoveAt(2));//x
Console.WriteLine(dblink.ToString());//v,w,y,z
dblink.InsertBefore("x", 2);
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink.GetItemAt(2));//x
dblink.Reverse();
Console.WriteLine(dblink.ToString());//z,y,x,w,v
dblink.InsertAfter("1", 0);
dblink.InsertAfter("2", 1);
dblink.InsertAfter("6", 5);
dblink.InsertAfter("8", 7);
dblink.InsertAfter("A", 10);//Position is error!
Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8
string _tail = dblink.GetItemAt(dblink.Count()-1);
Console.WriteLine(_tail);
Console.WriteLine(dblink.TestPrevErgodic());//8
Console.ReadKey(); //8,v,6,w,x,y,2,1,z
双链表的插入操作要稍微复杂一点，示意图如下：
同样对于删除操作，也要额外处理prev指向
🦋3.3 循环双向链表
using System;
public class LinkedList
{
private Node head;
private int size;
public LinkedList()
{
head = null;
size = 0;
}
public bool IsEmpty()
{
return head == null;
}
public int GetSize()
{
return size;
}
public void Add(int data)
{
Node newNode = new Node(data);
if (IsEmpty())
{
head = newNode;
head.Prev = head;
head.Next = head;
}
else
{
Node tail = head.Prev;
tail.Next = newNode;
newNode.Prev = tail;
newNode.Next = head;
head.Prev = newNode;
}
size++;
}
public void Remove(int data)
{
if (IsEmpty())
{
throw new Exception("List is empty!");
}
Node current = head;
bool found = false;
for (int i = 0; i < size; i++)
{
if (current.Data == data)
{
found = true;
break;
}
current = current.Next;
}
if (!found)
{
throw new Exception("Not found!");
}
if (size == 1)
{
head = null;
}
else if (current == head)
{
head = head.Next;
head.Prev = current.Prev;
current.Prev.Next = head;
}
else
{
current.Prev.Next = current.Next;
current.Next.Prev = current.Prev;
}
size--;
}
public void Display()
{
if (IsEmpty())
{
Console.WriteLine("List is empty!");
}
Node current = head;
for (int i = 0; i < size; i++)
{
Console.Write(current.Data + " ");
current = current.Next;
}
Console.WriteLine();
}
public class Node
{
public int Data { get; set; }
public Node Prev { get; set; }
public Node Next { get; set; }
public Node(int data)
{
Data = data;
Prev = null;
Next = null;
}
}
}
上述代码中包含了循环双向链表的基本操作：添加、删除和显示。使用示例如下：
LinkedList list = new LinkedList();
list.Add(1);
list.Add(2);
list.Add(3);
list.Display(); // 输出：1 2 3
list.Remove(2);
list.Display(); // 输出：1 3
🔎4.优点和缺点
链表是一种数据结构，它由多个节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点和缺点如下：
优点：
-
动态性：链表的大小可以动态增加或减少，随时修改数据结构，不需要像数组一样预先申请空间。
-
插入和删除的效率高：由于链表的节点是通过指针相连的，所以插入和删除节点时只需要修改相邻节点的指针即可，而不需要像数组一样移动其他元素。
-
不会浪费太多空间：由于链表只需要为实际存储的数据分配空间，因此不会浪费太多空间。同时，链表还可以通过链表节点池和内存池等方式管理内存，进一步减少空间浪费。
-
链表相对于数组，没有固定大小的限制。
缺点：
-
无法快速访问节点：链表中的节点是通过指针相连的，因此访问一个节点时需要从头节点开始遍历链表，直到找到目标节点为止。如果要访问的节点在链表中的位置比较靠后，那么访问效率就会很低。
-
空间开销较大：由于每个链表节点包含指向下一个节点的指针，因此相比数组，链表需要更多的内存空间。
-
不支持随机访问：链表中的节点是通过指针相连的，因此访问一个节点时需要从头节点开始遍历链表，直到找到目标节点为止。如果要访问的节点在链表中的位置比较靠后，那么访问效率就会很低。无法通过下标的方式访问链表中的元素，也无法通过二分查找等方式快速定位元素。
-
链表在某些操作上的性能不如数组，比如数组在随机访问元素和在内存中连续分配元素时会更加高效。
🔎5.应用场景
链表通常用于以下场景：
-
需要动态地增加或删除元素的场景，比如实现栈、队列、循环队列等数据结构。
-
实现哈希表等数据结构时，因为哈希表中的每个元素对应的位置是不确定的，因此需要使用链表来解决哈希碰撞问题。
-
实现大量数据的排序算法时，比如归并排序和快速排序等，链表的特点可以减少数据移动的次数和空间开销。
-
实现图的深度优先搜索和广度优先搜索时，可以使用链表来表示图中的节点和边。
-
实现UI界面的控件布局时，可以使用链表来连接控件之间的关系。
需要注意的是，链表由于其动态性，也会导致访问元素的时间复杂度较高，因此在需要频繁访问、查找元素的场景下，不建议使用链表。
🚀感谢：给读者的一封信
亲爱的读者，
我在这篇文章中投入了大量的心血和时间，希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验，我相信这些信息对您非常有帮助。
如果您觉得这篇文章对您有所帮助，我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担，但它会对我继续创作高质量的内容产生积极的影响。
我之所以写这篇文章，是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命，也鼓励我花更多的时间和精力创作更多有价值的内容。
如果您愿意支持我的创作，请扫描下面二维码，您的支持将不胜感激。同时，如果您有任何反馈或建议，也欢迎与我分享。
再次感谢您的阅读和支持！
最诚挚的问候， “愚公搬代码”
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）