C#单向链表实现：Append,Move,Delete,InsertAscending, InsertUnAscending,Clear

���录

（）

一、链表定义

二、链表设计 

（）

1.先定义一个结点类（Node）

2.再定义链表类（LinkedList）并依次设计其方法

3.再实现删除方法

4.再实现Insert 的方法

5.再增加InsertAscending升序插入

6.再增加 InsertUnAscending 的方法

7.再增加一个Clear方法，清空链表

8.再增加GetCurrentValue()方法取得当前的值

三、设计一个Main方法演示上述方法的应用

---

一、链表定义

        链表是一种特殊的数据结构，能够动态地存储一种结构类型数据。在开发复杂的系统时，经常会使用链表存储数据。

        链表是一种重要的数据结构，该结构由节点组成。每个节点包含两部分数据，第一部分是节点本身的数据，第二部分是指向下一个节点的指针。对于单向链表，链表中存在两个特殊的节点，分别为“头节点”和“尾节点”。头节点本身没有数据，只存储下一个节点的指针，尾节点只存储数据。

二、链表设计 

1.先定义一个结点类（Node）

public class Node{    public object Data { get; set; }    public Node Next { get; set; }    public Node Previous { get; set; }    public Node(object data)    {        Data = data;        Next = null;        Previous = null;    }}

2.再定义链表类（LinkedList）并依次设计其方法

        链表类中使用了三个指针：Head、Tail和Current。Head指针指向链表的头部，Tail指针指向链表的尾部，Current指针指向当前正在访问的结点。

        定义了以下方法来实现结点的移动和添加：

• Append：在链表的尾部添加一个新的结点。
• MoveFirst：将Current指针移动到链表的头部。
• MovePrevious：将Current指针向前移动一位。
• MoveNext：将Current指针向后移动一位。

  public class LinkedList{    private static Node _head;    private static Node _current;    public LinkedList()    {        _head = null;        _tail = null;        _current = null;    }    public static void Append(object data)    {        var newNode = new Node(data);        if (_head == null)        {            _head = newNode;            _tail = newNode;        }        else        {            _tail.Next = newNode;            newNode.Previous = _tail;            _tail = newNode;        }    }    public static void MoveFirst()    {        if (_head != null)        {            _current = _head;        }    }    public static void MovePrevious()    {        if (_current != null && _current.Previous != null)        {            _current = _current.Previous;        }    }    public static void MoveNext()    {        if (_current != null && _current.Next != null)        {            _current = _current.Next;        }    }}

  3.再实现删除方法

          要实现删除操作，添加一个名为 Delete 的方法。在该方法中，需要处理三种情况：删除头部结点、删除尾部结点和删除中间结点。

  public static void Delete(){    if (_current == null)    {        return;    }    // 删除头部结点    if (_current == _head)    {        if (_head == _tail)        {            _head = null;            _tail = null;        }        else        {            _head = _head.Next;            _head.Previous = null;        }    }    // 删除尾部结点    else if (_current == _tail)    {        _tail = _tail.Previous;        _tail.Next = null;    }    // 删除中间结点    else    {        var nextNode = _current.Next;        var previousNode = _current.Previous;        nextNode.Previous = previousNode;        previousNode.Next = nextNode;    }    _current = null;}

          在需要删除当前指向的结点时调用 Delete 方法。注意，在删除结点后，Current 指针会变成 null，需要重新定位到链表的头部或尾部。 

  4.再实现Insert 的方法

  /// /// 在当前位置插入数据，/// 不对数据排序，也不比较数据/// public static void Insert(int value){    // 创建一个新的节点    var newNode = new Node(value);    // 如果链表为空，将新节点设置为头节点    if (_head == null)    {        _head = newNode;        _current = newNode;        return;    }    // 找到当前节点    var current = _current;    if (current == null)    {        //current = _head;        _current = _head;        while (_current.Next != null)        {            _current = _current.Next;        }        current = _current;    }    // 在当前位置插入新节点    newNode.Next = current.Next;    newNode.Previous = current;    current.Next = newNode;    _current = newNode;}

          需要在当前节点的后面插入新结点时调用 Insert 方法。注意，在插入新节点后，Current 指针会指向新插入的节点。

  5.再增加InsertAscending升序插入

   ///  /// 升序插入方法 /// 如果原链表数据未排序，则需先排序然后插入 ///  public static Node InsertAscending(int value) {     Node newNode = new(value);     if (_head == null || (int)_head.Data >= value)     {         newNode!.Next = _head;         return newNode;     }     else     {         Node? previous = _head;         Node? current = _head.Next;         while (current != null && (int)current.Data  
  6.再增加 InsertUnAscending 的方法
   
          添加一个名为 InsertUnAscending 的方法，该方法实现非升序插入功能。这意味着新结点将根据给定的值在链表中找到合适的位置并插入。
   
  /// /// 非升序插入节点数据的方法/// 非升序插入意味着元素不是按升序插入链表中/// 相反，元素可以以任何顺序插入链表中/// 具体实现是由程序的需求决定的/// public static void InsertUnAscending(int data){    var newNode = new Node(data);    if (_head == null)    {        _head = newNode;    }    else    {        Node? temp = _head;        while (temp!.Next != null && (int)temp.Next.Data  
          该方法首先检查链表是否为空。如果为空，则将新结点设置为头部、尾部和当前结点。如果新结点的值小于头部结点的值，则将新结点设置为头部，并将其指向原来的头部结点。如果新结点的值大于尾部结点的值，则将新结点设置为尾部，并将其指向原来的尾部结点。否则，我们将遍历链表，找到新结点应该插入的位置，然后将新结点插入到合适的位置。
   
  7.再增加一个Clear方法，清空链表
   
  // 清空链表public static void Clear(){    _head = null;    _tail = null;    _current = null;}
   
          将链表的头部、尾部和当前结点都设置为 null，从而清空整个链表。
   
  8.再增加GetCurrentValue()方法取得当前的值
   
  // 获取当前结点的值public static int GetCurrentValue(){    if (_head != null)    {        return (int)_current!.Data;    }    else    {        throw new InvalidOperationException("The linked list is empty.");    }}
   
          在这个修改后的实现中，如果head为null，我们抛出一个InvalidOperationException异常，指示链表为空。
   
          另外，您还可以根据您的需求选择返回一个默认值或进行其他处理：
   
  public static int GetCurrentValue(){    if (_head != null)    {        return (int)_head.Data;    }    else    {        return default; // 或者 return 0;    }}
   
  9.再增加对链表数据冒泡排序SortList方法
   
  /// /// 对链表数据冒泡排序/// public static Node? SortList(Node? head){    if (head == null || head.Next == null)    {        return head;    }    bool swapped;    do    {        swapped = false;        Node? current = head;        while (current != null && current.Next != null)        {            if ((int)current.Next.Data  
  三、设计一个Main方法演示上述方法的应用
   
  // 单向链表Main方法namespace _131_1{    class Program    {        static void Main(string[] args)        {            ArgumentNullException.ThrowIfNull(args);            // 插入结点            LinkedList.Append(5);            LinkedList.Append(2);            LinkedList.Append(8);            LinkedList.Append(1);            LinkedList.Append(3);            // 获取当前结点的值            Console.Write("当前结点的值：");            Console.WriteLine(LinkedList.GetCurrentValue());            // 移动到第一个结点            LinkedList.MoveFirst();            Console.Write("第一结点的值：");            Console.WriteLine(LinkedList.GetCurrentValue());            // 移动到下一个结点            LinkedList.MoveNext();            Console.Write("下一结点的值：");            Console.WriteLine(LinkedList.GetCurrentValue());            // 移动到上一个结点            LinkedList.MovePrevious();            Console.Write("上一结点的值：");            Console.WriteLine(LinkedList.GetCurrentValue());            LinkedList.Print();            Console.WriteLine("*初始数据*");            // 删除尾首2个结点            LinkedList.Delete();            LinkedList.MoveFirst();            LinkedList.Delete();            LinkedList.Print();            Console.WriteLine("*删除节点*");            // 插入升序结点            LinkedList.SortList(LinkedList._head);//先排序            LinkedList.InsertAscending(6);            LinkedList.InsertAscending(4);            LinkedList.InsertAscending(9);            LinkedList.Print();            Console.WriteLine("*升序插入*");            // 插入非升序结点            LinkedList.InsertUnAscending(7);            LinkedList.InsertUnAscending(3);            LinkedList.InsertUnAscending(10);            LinkedList.Print();            Console.WriteLine("*非升序插入*");            // 清空链表            LinkedList.Clear();            LinkedList.Print();            Console.WriteLine();            Console.WriteLine("**清空就没有了**");            // 插入数据            LinkedList.Insert(0);            LinkedList.Insert(1);            LinkedList.Insert(2);            LinkedList.Insert(3);            LinkedList.Print();            Console.WriteLine("*新数据*");            LinkedList.MoveFirst();            LinkedList.MoveNext();            Console.WriteLine(LinkedList.GetCurrentValue());            Console.WriteLine("*********");            LinkedList.Insert(5);            LinkedList.Print();            Console.WriteLine("*插入5*");            LinkedList.MovePrevious();            LinkedList.Insert(6);            LinkedList.Print();            Console.WriteLine("**插入6**");        }    }}//运行结果：/*当前结点的值：3第一结点的值：5下一结点的值：2上一结点的值：552813*初始数据*813*删除节点*134689*升序插入*1334678910*非升序插入***清空就没有了**0123*新数据*1*********01523*插入5*016523**插入6** */