目录
8.再增加GetCurrentValue()方法取得当前的值
一、链表定义
链表是一种特殊的数据结构，能够动态地存储一种结构类型数据。在开发复杂的系统时，经常会使用链表存储数据。
链表是一种重要的数据结构，该结构由节点组成。每个节点包含两部分数据，第一部分是节点本身的数据，第二部分是指向下一个节点的指针。对于单向链表，链表中存在两个特殊的节点，分别为“头节点”和“尾节点”。头节点本身没有数据，只存储下一个节点的指针，尾节点只存储数据。
二、链表设计
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指针向后移动一位。
- MoveLast：将Current指针移动到最后一个数据。
public class LinkedList
{
private Node _head;
private Node _tail;
private Node _current;
public LinkedList()
{
_head = null;
_tail = null;
_current = null;
}
public 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 void MoveFirst()
{
if (_head != null)
{
_current = _head;
}
}
public void MovePrevious()
{
if (_current != null && _current.Previous != null)
{
_current = _current.Previous;
}
}
public void MoveNext()
{
if (_current != null && _current.Next != null)
{
_current = _current.Next;
}
}
public void MoveLast()
{
if (_tail != null)
{
_current = _tail;
}
}
}3.再实现删除方法
要实现删除操作，添加一个名为 Delete 的方法。在该方法中，需要处理三种情况：删除头部结点、删除尾部结点和删除中间结点。
public 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 的方法
要实现插入操作，添加一个名为 Insert 的方法。在该方法中，需要处理四种情况：在头部插入、在尾部插入、在头部之前插入和在中间插入。
public void Insert(int data)
{
var newNode = new Node(data);
// 在头部插入
if (_head == null)
{
_head = newNode;
_tail = newNode;
}
// 在尾部插入
else if (_current == null)
{
_tail.Next = newNode;
newNode.Previous = _tail;
_tail = newNode;
}
// 在头部之前插入
else if (_current == _head)
{
var currentHead = _head;
_head = newNode;
_head.Next = currentHead;
currentHead.Previous = _head;
}
// 在中间插入
else
{
var nextNode = _current.Next;
var previousNode = _current;
nextNode.Previous = newNode;
newNode.Next = nextNode;
previousNode.Next = newNode;
newNode.Previous = previousNode;
}
_current = newNode;
}需要在当前指向的结点处插入新结点时调用 Insert 方法。注意，在插入新结点后，Current 指针会指向新插入的结点。
5.再增加InsertAscending升序插入
// 升序插入
public void InsertAscending(int data)
{
var newNode = new Node(data);
// 找到插入位置
Node previousNode = null;
Node nextNode = _head;
while (nextNode != null && nextNode.Data < data)
{
previousNode = nextNode;
nextNode = nextNode.Next;
}
// 在找到的位置插入新结点
if (previousNode == null)
{
// 插入到头部
Insert(data);
}
else if (nextNode == null)
{
// 插入到尾部
previousNode.Next = newNode;
newNode.Previous = previousNode;
newNode.Next = null;
_tail = newNode;
}
else
{
// 插入到中间
previousNode.Next = newNode;
newNode.Previous = previousNode;
newNode.Next = nextNode;
nextNode.Previous = newNode;
}
_current = newNode;
}6.再增加 InsertUnAscending 的方法
添加一个名为 InsertUnAscending 的方法，该方法实现非升序插入功能。这意味着新结点将根据给定的值在链表中找到合适的位置并插入。
// 非升序插入
public void InsertUnAscending(int data)
{
var newNode = new Node(data);
if (_head == null)
{
_head = newNode;
_tail = newNode;
_current = newNode;
}
else if (data < _head.Data)
{
newNode.Next = _head;
_head = newNode;
}
else if (data > _tail.Data)
{
newNode.Previous = _tail;
_tail = newNode;
}
else
{
var current = _head;
while (current.Next != null && current.Next.Data < data)
{
current = current.Next;
}
newNode.Next = current.Next;
newNode.Previous = current;
if (current.Next != null)
{
current.Next.Previous = newNode;
}
current.Next = newNode;
}
}该方法首先检查链表是否为空。如果为空，则将新结点设置为头部、尾部和当前结点。如果新结点的值小于头部结点的值，则将新结点设置为头部，并将其指向原来的头部结点。如果新结点的值大于尾部结点的值，则将新结点设置为尾部，并将其指向原来的尾部结点。否则，我们将遍历链表，找到新结点应该插入的位置，然后将新结点插入到合适的位置。
7.再增加一个Clear方法，清空链表
// 清空链表
public void Clear()
{
_head = null;
_tail = null;
_current = null;
}将链表的头部、尾部和当前结点都设置为 null，从而清空整个链表。
8.再增加GetCurrentValue()方法取得当前的值
// 获取当前结点的值
public int GetCurrentValue()
{
if (_current == null)
{
throw new InvalidOperationException("当前结点为空。");
}
return _current.Data;
}该方法检查当前结点是否为 null。如果是，则抛出一个异常，因为当前结点为空。否则，它返回当前结点的值。
三、设计一个Main方法演示上述方法的应用
using System;
class Program
{
static void Main(string[] args)
{
var linkedList = new LinkedList();
// 插入结点
linkedList.Append(5);
linkedList.Append(2);
linkedList.Append(8);
linkedList.Append(1);
linkedList.Append(3);
// 获取当前结点的值
Console.WriteLine("当前结点的值：");
Console.WriteLine(linkedList.GetCurrentValue());
// 移动到第一个结点
linkedList.MoveFirst();
Console.WriteLine("第一个结点的值：");
Console.WriteLine(linkedList.GetCurrentValue());
// 移动到上一个结点
linkedList.MovePrevious();
Console.WriteLine("上一个结点的值：");
Console.WriteLine(linkedList.GetCurrentValue());
// 移动到下一个结点
linkedList.MoveNext();
Console.WriteLine("下一个结点的值：");
Console.WriteLine(linkedList.GetCurrentValue());
// 移动到最后一个结点
linkedList.MoveLast();
Console.WriteLine("最后一个结点的值：");
Console.WriteLine(linkedList.GetCurrentValue());
// 删除当前结点
linkedList.Delete();
// 插入升序结点
linkedList.InsertAscending(6);
linkedList.InsertAscending(4);
linkedList.InsertAscending(9);
// 插入非升序结点
linkedList.InsertUnAscending(7);
linkedList.InsertUnAscending(10);
// 打印链表
Console.WriteLine("Before clearing:");
linkedList.Print();
// 清空链表
linkedList.Clear();
// 打印清空后的链表
Console.WriteLine("After clearing:");
linkedList.Print();
}
}