🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，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界面的控件布局时，可以使用链表来连接控件之间的关系。

需要注意的是，链表由于其动态性，也会导致访问元素的时间复杂度较高，因此在需要频繁访问、查找元素的场景下，不建议使用链表。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！

(完)c#数据结构与算法

【愚公系列】2023年11月数据结构(二)-链表

🚀前言

🚀一、链表

🔎1.基本思想

🔎2.链表常用操作

🦋2.1 初始化链表

🦋2.2 插入节点

🦋2.3 删除节点

🦋2.4 访问节点

🦋2.5 查找节点

🔎3.常见链表类型

🦋3.1 单链表

🦋3.2 双向链表

🦋3.3 循环双向链表

🔎4.优点和缺点

🔎5.应用场景

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

(完)c#数据结构与算法

【愚公系列】2023年11月 数据结构(二)-链表

🚀前言

🚀一、链表

🔎1.基本思想

🔎2.链表常用操作

🦋2.1 初始化链表

🦋2.2 插入节点

🦋2.3 删除节点

🦋2.4 访问节点

🦋2.5 查找节点

🔎3.常见链表类型

🦋3.1 单链表

🦋3.2 双向链表

🦋3.3 循环双向链表

🔎4.优点和缺点

🔎5.应用场景

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

【愚公系列】2023年11月数据结构(二)-链表