一文探索C#中實現(xiàn)雙向鏈表的方法

更新時間：2024年03月05日 11:16:18 作者：wenchm

這篇文章主要為大家詳細(xì)介紹了C#中的雙向鏈表的實現(xiàn),揭秘雙向鏈表內(nèi)實現(xiàn)諸多方法的那些事,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下

一、涉及到的知識點

1.定義

在雙向鏈表中，每個節(jié)點有兩個指針域，一個指向它的前一個節(jié)點（即直接前驅(qū)），另一個指向它的后一個節(jié)點（即直接后繼）。這種設(shè)計使得雙向鏈表可以進(jìn)行雙向遍歷，即可以從頭節(jié)點開始向前遍歷，也可以從尾節(jié)點開始向后遍歷。

雙向鏈表的節(jié)點結(jié)構(gòu)通常如下所示：

struct Node
{
    // 數(shù)據(jù)域
    int data;
    // 指向直接前驅(qū)的指針
    Node* prev;
    // 指向直接后繼的指針
    Node* next;
};

2.雙向鏈表與單向鏈表的區(qū)別

雙向鏈表的算法描述和單向鏈表基本相同，但是雙向鏈表在刪除和插入節(jié)點時與單向鏈表有很大的不同：雙向鏈表在刪除節(jié)點時，不但要修改節(jié)點的直接后繼指針，還要同時修改節(jié)點的直接前驅(qū)指針。在插入時更是要修改插入節(jié)點的前驅(qū)和后繼的兩個方向上的指針。

二、雙向鏈表實現(xiàn)基礎(chǔ)

為了讓實現(xiàn)的鏈表具有更多的實用性，鏈表的參數(shù)的數(shù)據(jù)類型選擇Objects。Objects參數(shù)可以是1個也可以2個甚至更多，總之為了表達(dá)雙向鏈表更能為實際生活中的需要，這一步就要極盡所能地、契合實際需要地設(shè)計Objects的參數(shù)。

1.定義參數(shù)類Objects

/// <summary>
/// 定義雙向鏈表的參數(shù)類型是Objects類型
/// </summary>
/// <param name="value">參數(shù)，數(shù)據(jù)數(shù)值</param>
/// <param name="name">參數(shù)，數(shù)據(jù)名稱</param>
/// <param name="index">參數(shù)，數(shù)據(jù)索引</param>
public class Objects(int value, string name, int index)
{
    public int Value { get; set; } = value;
    public string Name { get; set; } = name;
    public int Index { get; set; } = index;
}

2.定義節(jié)點類ListNode

 // 定義結(jié)點類
 public class ListNode(Objects obj)
 {
     public Objects _object = obj;
     public ListNode? _next;
     public ListNode? previous;
 
     public ListNode? Next
     {
         get
         {
             return _next;
         }
         set
         {
             _next = value;
         }
     }
 
     public Objects Object
     {
         get
         {
             return _object;
         }
         set
         {
             _object = value;
         }
     }
 }

3.定義鏈表類LinkedList及其方法

在鏈表類中要定義兩個指針_head、_tail，用于正向、逆向查詢；_current用于在鏈表類實時表達(dá)當(dāng)前節(jié)點指針;

  private ListNode? _head;
  private ListNode? _tail;
  private ListNode? _current;

鏈表中的方法是自定義的，是滿足實際需要時因地制宜設(shè)計的方法。因此，需要什么方法，就在鏈表中設(shè)計什么方法。

在本例中，切記一切方法的參數(shù)類型都是Objects類型的。

（1）在鏈表類中定義Append方法、Print方法

public class LinkedList
{
    //構(gòu)造函數(shù)
    public LinkedList()
    {
        _ListCountValue = 0;
        _head = null;
        _tail = null;
    }
 
    /// <summary>
    /// 鏈表名
    /// </summary>
    private string listname = "";
    public string ListName
    {
        get
        {
            return listname;
        }
        set
        {
            listname = value;
        }
    }
 
    /// <summary>
    /// 頭指針
    /// </summary>
    private ListNode? _head;
 
    /// <summary>
    /// 尾指針
    /// </summary>
    private ListNode? _tail;
 
    /// <summary>
    /// 定義字段當(dāng)前指針current
    /// 定義屬性Current
    /// 字段是一種變量，屬性是一種方法
    /// </summary>  
    private ListNode? _current;
    public ListNode? Current
    {
        get
        {
            return _current;
        }
        set
        {
            _current = value;
        }
    }
 
    // 定義鏈表數(shù)據(jù)的個數(shù)
    private int _ListCountValue;
 
    /// <summary>
    /// 尾部添加數(shù)據(jù)
    /// </summary>
    public void Append(Objects value)
    {
        ListNode newNode = new(value);
        if (IsNull())   //如果頭指針為空
        {
            _head = newNode;
            _tail = newNode;
        }
        else
        {
            _tail!.Next = newNode;   // 原尾節(jié)點的下節(jié)點=新節(jié)點
            newNode.previous = _tail;// 新節(jié)點的前節(jié)點=原尾結(jié)點
            _tail = newNode;         // 新尾結(jié)點=新節(jié)點
        }
        _current = newNode;    // 當(dāng)前節(jié)點=新節(jié)點
        _ListCountValue += 1;  // 節(jié)點總數(shù)增加1
    }
 
    /// <summary>
    /// 刪除當(dāng)前的數(shù)據(jù)
    /// </summary>
    public void Delete()
    {
        if (!IsNull())  //若為空鏈表
        {
            //刪除頭部
            if (IsBof())
            {
                _head = _current!.Next;
                _current = _head;
                _ListCountValue -= 1;
                return;
            }
            //刪除尾
            if (IsEof())
            {
                _tail = _current!.previous;
                _tail!.Next = null;
                _current = _tail;
                _ListCountValue -= 1;
                return;
            }
            //若刪除中間數(shù)據(jù)
            _current!.previous!.Next = _current.Next;
            _current = _current.previous;
            _ListCountValue -= 1;
            return;
        }
    }

（2）在鏈表類中定義MoveFirst、MovePrevious、MoveNext、MoveTail、Clear、GetCurrentValue、IsNull、IsEof、IsBof、

 /// <summary>
 /// 向后移動一個數(shù)據(jù)
 /// </summary>
 public void MoveNext()
 {
     if (!IsEof()) _current = _current!.Next;
 }
 
 /// <summary>
 /// 向前移動一個數(shù)據(jù)
 /// </summary>
 public void MovePrevious()
 {
     if (!IsBof()) _current = _current!.previous;
 }
 
 /// <summary>
 /// 移動到第一個數(shù)據(jù)
 /// </summary>
 public void MoveFirst()
 {
     _current = _head;
 }
 
 /// <summary>
 /// 移動到最后一個數(shù)據(jù)
 /// </summary>
 public void MoveTail()
 {
     _current = _tail;
 }
 
 /// <summary>
 /// 判斷是否為空鏈表
 /// </summary>
 public bool IsNull()
 {
     if (_ListCountValue == 0)
         return true;
     else
         return false;
 }
 
 /// <summary>
 /// 判斷是否為到達(dá)尾部
 /// Is End of File
 /// </summary>
 public bool IsEof()
 {
     if (_current == _tail)
         return true;
     else
         return false;
 }
 
 /// <summary>
 /// 判斷是否為到達(dá)頭部
 /// Is Beginning of File
 /// </summary>
 public bool IsBof()
 {
     if (_current == _head)
         return true;
     else
         return false;
 }
 /// <summary>
 /// 獲取當(dāng)前節(jié)點數(shù)據(jù)
 /// </summary>
 public Objects GetCurrentValue()
 {
     return _current!._object;
 }
 
 /// <summary>
 /// 取得鏈表的數(shù)據(jù)個數(shù)
 /// </summary>
 public int ListCount
 {
     get
     {
         return _ListCountValue;
     }
 }
 
 /// <summary>
 /// 清空鏈表
 /// </summary>
 public void Clear()
 {
     MoveFirst();
     while (!IsNull())
     {
         Delete();
     }
 }

（3）在鏈表類中定義Insert()、InsertAscending()、InsertUnAscending()、SortList()

 /// <summary>
 /// 對鏈表數(shù)據(jù)冒泡排序
 /// </summary>
 public static ListNode? SortList(ListNode? head)
 {
     if (head == null || head.Next == null)
     {
         return head;
     }
 
     bool swapped;
     do
     {
         swapped = false;
         ListNode? current = head;
         while (current != null && current.Next != null)
         {
             if (current.Next.Object.Value < current.Object.Value)
             {
                 (current.Next._object, current._object) = (current._object, current.Next._object);
                 swapped = true;
             }
             current = current.Next;
         }
     } while (swapped);
 
     return head;
 }
 
 /// <summary>
 /// 在當(dāng)前位置前插入數(shù)據(jù)
 /// </summary>
 public void Insert(Objects value)
 {
     ListNode newNode = new(value);
     if (IsNull())
     {
         //為空表，則添加
         Append(value);
         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>
 /// 進(jìn)行升序插入
 /// </summary>
 public void InsertAscending(Objects value)
 {
     //為空鏈表
     if (IsNull())
     {
         Append(value);
         return;
     }
     //移動到頭
     MoveFirst();
     if (value.Value < GetCurrentValue().Value)    //滿足條件，則插入，退出
     {
         Insert(value);
         return;
     }
     while (true)
     {
         if (value.Value < GetCurrentValue().Value)//滿足條件，則插入，退出
         {
             Insert(value);
             break;
         }
 
         if (IsEof())
         {
             Append(value);
             break;
         }
         MoveNext();
     }
 }
 
 /// <summary>
 /// 進(jìn)行非升序插入
 /// </summary>
 public void InsertUnAscending(Objects value)
 {
     //為空鏈表
     if (IsNull())
     {
         Append(value);
         return;
     }
     //移動到頭
     MoveFirst();
     if (value.Value > GetCurrentValue().Value)//滿足條件，則插入，退出
     {
         Insert(value);
         return;
     }
     while (true)
     {
         if (value.Value > GetCurrentValue().Value)//滿足條件，則插入，退出
         {
             Insert(value);
             break;
         }
         if (IsEof())
         {
             Append(value);
             break;
         }
         MoveNext();
     }
 }

（4）FindObjects(int value)、FindObjects(string name)、DeleteObjects(string name)、DeleteObjects(int value)

/// <summary>
/// 根據(jù)數(shù)據(jù)名稱查詢數(shù)據(jù)
/// </summary>
/// <param name="name"> 
/// 數(shù)據(jù)名稱
/// </param>
public Objects? FindObjects(string name)
{
    ListNode? nodes = _head;
    if (IsNull())
    {
        return null;
    }
    else if (IsEof())
    {
        return null;
    }
    else
        while (nodes!._object.Name != name)
        {
            if (nodes.Next == null)
            {
                _current = nodes;
                return null;
            }
            nodes = nodes.Next;
        }
    _current = nodes;
    return nodes._object;
}
 
/// <summary>
/// 根據(jù)參數(shù)值查詢數(shù)據(jù)
/// </summary>
/// <param name="value">
/// 數(shù)據(jù)編號
/// </param>
public Objects? FindObjects(int value)
{
    ListNode? nodes = _head;
    if (IsNull())
    {
        return null;
    }
    else if (IsEof())
    {
        return null;
    }
    else
        while (nodes!._object.Value != value)
        {
            if (nodes.Next == null)
            {
                _current = nodes;
                return null;
            }
            nodes = nodes.Next;
        }
    _current = nodes;
    return nodes._object;
}
 
/// <summary>
/// 根據(jù)數(shù)據(jù)名稱刪除數(shù)據(jù)
/// </summary>
/// <param name="name">
/// 數(shù)據(jù)名稱
/// </param>
public Objects? DeleteObjects(string name)
{
    Objects? objects;
    objects = FindObjects(name);
    Delete();
    return objects;
}
 
/// <summary>
/// 根據(jù)參數(shù)值刪除數(shù)據(jù)
/// </summary>
/// <param name="value">
/// 數(shù)據(jù)編號
/// </param>
public Objects? DeleteObjects(int value)
{
    Objects? objects;
    objects = FindObjects(value);
    Delete();
    return objects;
}
 
public void Print()
{
    ListNode? current = _head;
    while (current != null)
    {
        Console.WriteLine(current._object.Value);
        current = current.Next;
    }
}
public void Print()
 {
     ListNode? current = _head;
     while (current != null)
     {
         Console.WriteLine(current._object.Value);
         current = current.Next;
     }
 }
 
}

三、一些Objects類對象操作技巧

1.Objects類對象用于比較

Objects類對象是復(fù)合類型的數(shù)據(jù)，本身不能用于比較，但是其int類型的屬性值是可以進(jìn)行比較的。比如，應(yīng)該使用“Value”屬性來訪問對象的整數(shù)值。

ListNode newNode = new(obj);
if (_head == null || _head.Object.Value >= obj.Value)
{
    newNode.Next = _head;
    return newNode;
}
else
{
    ListNode? previous = _head;
    ListNode? current = _head!.Next;
    while (current != null && current.Object.Value < obj.Value)
    {
        previous = current;
        current = current!.Next;
    }
    newNode!.Next = current;
    previous!.Next = newNode;
}

if (_head != null)
{
    return _current!.Object.Value;
}
else
{
    return default; // 或者 return 0;
}

 while (current != null && current.Next != null)
 {
     if (current.Next.Object.Value < current.Object.Value)
     {
         (current.Next.Object.Value, current.Object.Value) = (current.Object.Value, current.Next.Object.Value);
         swapped = true;
     }
     current = current.Next;
 }

2. Objects類對象用于鏈表的初始化

Objects類對象是復(fù)合類型的數(shù)據(jù)，用于鏈表初始化時要復(fù)雜一些，不再向單純的int、string類型賦值得那么簡單直接。

Objects類對象用于鏈表初始化要體現(xiàn) Objects類的定義，實參和形參的數(shù)量和類型要一一對應(yīng)。

 LinkedList linkedList = new();
 
 linkedList.Append(new Objects(5, "Five", 1));
 linkedList.Append(new Objects(2, "Two", 2));
 linkedList.Append(new Objects(8, "Eight", 3));
 linkedList.Append(new Objects(1, "One", 4));

四、實例Main()

在實例的雙向鏈表類中，設(shè)計一個Append方法向鏈表的末尾追加初始數(shù)據(jù)5,2,8,1。然后用Print方法顯示鏈表數(shù)據(jù)。

鏈表類中的其他方法的示例，詳見Main方法。

 class Program
 {
     static void Main(string[] args)
     {
         ArgumentNullException.ThrowIfNull(args);
 
         LinkedList list = new();
 
         // 插入結(jié)點
         list.Append(new Objects(5, "five", 0));
         list.Append(new Objects(2, "two", 1));
         list.Append(new Objects(8, "eight", 2));
         list.Append(new Objects(1, "one", 3));
         list.Append(new Objects(3, "three", 4));
 
         // 獲取當(dāng)前結(jié)點的值
         Console.Write("當(dāng)前結(jié)點的值：");
         Console.WriteLine(list.GetCurrentValue().Value);
 
         // 移動到第一個結(jié)點
         list.MoveFirst();
         Console.Write("第一結(jié)點的值：");
         Console.WriteLine(list.GetCurrentValue().Value);
 
         // 移動到下一個結(jié)點
         list.MoveNext();
         Console.Write("下一結(jié)點的值：");
         Console.WriteLine(list.GetCurrentValue().Value);
 
         // 移動到上一個結(jié)點
         list.MovePrevious();
         Console.Write("上一結(jié)點的值：");
         Console.WriteLine(list.GetCurrentValue().Value);
 
         list.Print();
         Console.WriteLine("*初始數(shù)據(jù)*");
         // 刪除尾首2個結(jié)點
         list.MoveTail();
         list.Delete();
         list.MoveFirst();
         list.Delete();
         list.Print();
         Console.WriteLine("*刪除節(jié)點*");
 
         // 插入升序結(jié)點
         LinkedList.SortList(list._head);//先排序
 
         list.InsertAscending(new Objects(6, "six", 5));
         list.InsertAscending(new Objects(4, "four", 6));
         list.InsertAscending(new Objects(9, "none", 7));
         list.Print();
         Console.WriteLine("*升序插入*");
 
         // 插入非升序結(jié)點
         list.InsertUnAscending(new Objects(7, "seven", 8));
         list.InsertUnAscending(new Objects(3, "three", 9));
         list.InsertUnAscending(new Objects(10, "ten", 10));
         list.Print();
         Console.WriteLine("*非升序插入*");
 
         // 清空鏈表
         list.Clear();
         list.Print();
         Console.WriteLine();
         Console.WriteLine("**清空就沒有了**");
 
         // 插入數(shù)據(jù)
         list.Insert(new Objects(0, "zero", 11));
         list.Insert(new Objects(1, "one", 12));
         list.Insert(new Objects(2, "two", 13));
         list.Insert(new Objects(3, "three", 14));
         list.Print();
         Console.WriteLine("*新數(shù)據(jù)*");
         Console.WriteLine(list.GetCurrentValue().Value);
         Console.WriteLine("*最后插入的是當(dāng)前值*");
 
         list.MoveFirst();
         Console.WriteLine(list.GetCurrentValue().Value);
         Console.WriteLine("*當(dāng)前值居然是頭節(jié)點*");
 
         list.Insert(new Objects(5, "five", 15));
         list.Print();
         Console.WriteLine("*在當(dāng)前值前面插入5*");
 
         list.MoveNext();
         list.Insert(new Objects(6, "six", 16));
         list.Print();
         Console.WriteLine("*在當(dāng)前節(jié)點的下節(jié)點前面插入6*");
 
         list.MoveFirst();
         list.MovePrevious();
         list.Insert(new Objects(7, "seven", 17));
         list.Print();
         Console.WriteLine("*頭節(jié)點沒有前節(jié)點故在頭節(jié)點前面插入7*");
 
         list.FindObjects(3);
         Console.WriteLine(list.GetCurrentValue().Value);
         Console.WriteLine("*按數(shù)據(jù)值3查找*");
 
         list.FindObjects("three");
         Console.WriteLine(list.GetCurrentValue().Value);
         Console.WriteLine("*按參數(shù)名稱three查找*");
 
         list.DeleteObjects(3);
         list.Print();
         Console.WriteLine("*已經(jīng)刪除了值=3的參數(shù)*");
 
         list.DeleteObjects("six");
         list.Print();
         Console.WriteLine("*已經(jīng)刪除了名稱=six的參數(shù)*");
     }
 }

運行結(jié)果：

當(dāng)前結(jié)點的值：3
第一結(jié)點的值：5
下一結(jié)點的值：2
上一結(jié)點的值：5
5
2
8
1
3
*初始數(shù)據(jù)*
2
8
1
*刪除節(jié)點*
1
2
4
6
8
9
*升序插入*
10
7
3
1
2
4
6
8
9
*非升序插入*
**清空就沒有了**
3
2
1
0
*新數(shù)據(jù)*
3
*最后插入的是當(dāng)前值*
3
*當(dāng)前值居然是頭節(jié)點*
5
3
2
1
0
*在當(dāng)前值前面插入5*
5
6
3
2
1
0
*在當(dāng)前節(jié)點的下節(jié)點前面插入6*
7
5
6
3
2
1
0
*頭節(jié)點沒有前節(jié)點故在頭節(jié)點前面插入7*
3
*按數(shù)據(jù)值3查找*
3
*按參數(shù)名稱three查找*
7
5
6
2
1
0
*已經(jīng)刪除了值=3的參數(shù)*
7
5
2
1
0
*已經(jīng)刪除了名稱=six的參數(shù)*