C#如何實現單向鏈表

鏈表是一種重要的數據結構，該結構由節點組成。每個節點包含兩部分數據，第一部分是節點本身的數據，第二部分是指向下一個節點的指針。對於單向鏈表，鏈表中存在兩個特殊的節點，分別為“頭節點”和“尾節點”。頭節點本身沒有數據，只存儲下一個節點的指針，尾節點只存儲數據。結點的定義及對線性表的操作如下：

首先，定義一個結點類用於對結點的描述。其中，私有成員Value用於儲存節點本身的數據，Next用於存儲下一個節點的指針，Previous用於存儲上一個節點的指針。對於鏈表的操作，無非是進行節點的查找、插入和刪除操作。代碼如下：

//  結點類
        public class ListNode
        {
            public ListNode(int NewValue)//,int NewCurrent)
            {
                Value = NewValue;
                //Current = NewCurrent;
            }
            //前一個
            public ListNode Previous;
            // 後一個
            public ListNode Next;
            // 值
            public int Value;
            ////指針
            //public int Current;
        }

然後定義了一個Clist類，主要對線性表基本操作的編程。其中包括，Head、Tail、Current三個指針和Append、MoveFrist、MovePrevious、MoveNext、MoveLast、Delete、InsertAscending、InsertUnAscending、Clear、 GetCurrentValue方法，用於實現移動、添加、刪除、升序插入、降序插入、清空鏈表、取得當前的值等操作。代碼如下：

// 定義結點之後，開始類線性表的操作編程了.在ClIST 類中,采用了，Head ,Tail,  Current，三個指針，使用Append ，MoveFrist,MovePrevious，MoveNext, MoveLast , Delete, InsertAscending, InsertUnAscending, Clear 實現移動，添加、刪除,升序插入，降序插入，清空鏈表操作，GetCurrentValue（） 方法取得當前的值。
public class Clist
{
/// <summary>
/// 初始化線性表
/// </summary>
public Clist()
{
    //構造函數
    //初始化
    ListCountValue = 0;
    Head = null;
    Tail = null;
}
// 頭指針
private ListNode Head;
// 尾指針
private ListNode Tail;
// 當前指針
private ListNode Current;
//鏈表數據的個數
private int ListCountValue;

在鏈表尾部添加數據的代碼如下：

//尾部添加數據
/// <summary>
/// 尾部添加數據
/// </summary>
/// <param name="DataValue"></param>
public void Append(int DataValue)//,int DataCurrent)
{
    ListNode NewNode = new ListNode(DataValue);//,DataCurrent);
    if (IsNull())
    //如果頭指針為空
    {
        Head = NewNode;
        Tail = NewNode;
    }
    else
    {
        Tail.Next = NewNode;
        NewNode.Previous = Tail;
        Tail = NewNode;
    }
    Current = NewNode;
    //鏈表數據個數加一
    ListCountValue += 1;
}

刪除當前位置的結點的代碼如下：

//刪除當前的數據
/// <summary>
/// 刪除當前的數據
/// </summary>
public void Delete()
{
    //若為空鏈表
    if (!IsNull())
    {
        //若刪除頭
        if (IsBof())
        {
            Head = Current.Next;
            Current = Head;
            ListCountValue -= 1;
            return;
        }
        //若刪除尾
        if (IsEof())
        {
            Tail = Current.Previous;
            Current = Tail;
            ListCountValue -= 1;
            return;
        }
        //若刪除中間數據
        Current.Previous.Next = Current.Next;
        Current = Current.Previous;
        ListCountValue -= 1;
        return;
    }
}

向後移動一個結點的代碼如下：

// 向後移動一個數據
/// <summary>
/// 向後移動一個數據
/// </summary>
public void MoveNext()
{
    if (!IsEof()) Current = Current.Next;
}

向前移動一個結點的代碼如下：

// 向前移動一個數據
/// <summary>
/// 向前移動一個數據
/// </summary>
public void MovePrevious()
{
    if (!IsBof()) Current = Current.Previous;
}

移動到第一個結點的代碼如下：

// 移動到第一個數據
/// <summary>
/// 移動到第一個數據
/// </summary>
public void MoveFrist()
{
    Current = Head;
}

移動到最後一個結點的代碼如下：

// 移動到最後一個數據
/// <summary>
/// 移動到最後一個數據
/// </summary>
public void MoveLast()
{
    Current = Tail;
}

判斷鏈表是否為空的代碼如下：

// 判斷是否為空鏈表
/// <summary>
/// 判斷是否為空鏈表
/// </summary>
/// <returns></returns>
public bool IsNull()
{
    if (ListCountValue == 0)
        return true;

    return false;
}

判斷是否為鏈表的尾部的代碼如下：

// 判斷是否為到達尾
/// <summary>
/// 判斷是否為到達尾
/// </summary>
/// <returns></returns>
public bool IsEof()
{
    if (Current == Tail)
        return true;
    return false;
}

判斷是否為鏈表的頭部的代碼如下：

// 判斷是否為到達頭部
/// <summary>
/// 判斷是否為到達頭部
/// </summary>
/// <returns></returns>
public bool IsBof()
{
    if (Current == Head)
        return true;
    return false;
}

獲取當前位置的值的代碼如下：

/// <summary>
/// 獲取當前位置的值
/// </summary>
/// <returns></returns>
public int GetCurrentValue()
{
    return Current.Value;
}

獲取鏈表的結點數的代碼如下：

// 取得鏈表的數據個數
/// <summary>
/// 取得鏈表的數據個數
/// </summary>
public int ListCount
{
    get
    {
        return ListCountValue;
    }
}

清空鏈表的代碼如下：

// 清空鏈表
/// <summary>
/// 清空鏈表
/// </summary>
public void Clear()
{
    MoveFrist();
    while (!IsNull())
    {
        //若不為空鏈表,從尾部刪除
        Delete();
    }
}

在當前位置前插入結點的代碼如下：

// 在當前位置前插入數據
/// <summary>
/// 在當前位置前插入數據
/// </summary>
/// <param name="DataValue"></param>
public void Insert(int DataValue)
{
    ListNode NewNode = new ListNode(DataValue);
    if (IsNull())
    {
        //為空表，則添加
        Append(DataValue);
        return;
    }

    if (IsBof())
    {
        //為頭部插入
        NewNode.Next = Head;
        Head.Previous = NewNode;
        Head = NewNode;
        Current = Head;
        ListCountValue += 1;
        return;
    }
    //中間插入
    NewNode.Next = Current;
    NewNode.Previous = Current.Previous;
    Current.Previous.Next = NewNode;
    Current.Previous = NewNode;
    Current = NewNode;
    ListCountValue += 1;
}

進行升序插入的代碼如下：

// 進行升序插入
/// <summary>
/// 進行升序插入
/// </summary>
/// <param name="InsertValue"></param>
public void InsertAscending(int InsertValue)
{
    //參數：InsertValue 插入的數據
    //為空鏈表
    if (IsNull())
    {
        //添加
        Append(InsertValue);
        return;
    }
    //移動到頭
    MoveFrist();
    if ((InsertValue < GetCurrentValue()))
    {
        //滿足條件，則插入，退出
        Insert(InsertValue);
        return;
    }
    while (true)
    {
        if (InsertValue < GetCurrentValue())
        {
            //滿族條件，則插入，退出
            Insert(InsertValue);
            break;
        }
        if (IsEof())
        {
            //尾部添加
            Append(InsertValue);
            break;
        }
        //移動到下一個指針
        MoveNext();
    }
}

進行降序插入的代碼如下：

// 進行降序插入
/// <summary>
/// 進行降序插入
/// </summary>
/// <param name="InsertValue"></param>
public void InsertUnAscending(int InsertValue)
{
    //參數：InsertValue 插入的數據
    //為空鏈表
    if (IsNull())
    {
        //添加
        Append(InsertValue);
        return;
    }
    //移動到頭
    MoveFrist();
    if (InsertValue > GetCurrentValue())
    {
        //滿足條件，則插入，退出
        Insert(InsertValue);
        return;
    }
    while (true)
    {
        if (InsertValue > GetCurrentValue())
        {
            //滿族條件，則插入，退出
            Insert(InsertValue);
            break;
        }
        if (IsEof())
        {
            //尾部添加
            Append(InsertValue);
            break;
        }
        //移動到下一個指針
        MoveNext();
    }
}