转载 C#如何实现双向链表

宿海仁太

1        <P> </P>
2        双向链表的算法描述和单向链基本相同，但是双向链表在删除和插入时与单向链表有很大的不同。

view sourcePRint?1        双向链表在删除结点时，不但要修改结点的直接后继指针，还要同时修改结点的直接前驱指针。

view sourceprint?1        在插入时更是要修改插入结点的前驱和后继的两个方向上的指针。具体代码如下：


view sourceprint?01        public class Objects  
02        {  
03             private int number;   
04             private string name;  
05             private int counter;  
06             //构造函数  
07             public Objects(int num, string Name, int count)  
08             {  
09                 number = num;  
10                 name = Name;  
11                 counter = count;  
12             }  
13             public int Number  
14             {  
15                 get
16                 {  
17                     return number;  
18                 }  
19                 set
20                 {  
21                     number = value;  
22                 }  
23             }  
24             public string Name  
25             {  
26                 get
27                 {  
28                     return name;  
29                 }  
30                 set
31                 {  
32                     name = value;  
33                 }  
34             }  
35             public int Counter  
36             {  
37                 get
38                 {  
39                     return counter;  
40                 }  
41                 set
42                 {  
43                     counter = value;  
44                 }  
45             }  
46        }

代码
//结点类
public class ListNode
{
  public ListNode(Objects bugs)
  {
      goods = bugs;
  }
  /**/
  /// <summary>
  /// 前一个
  /// </summary>      
  public ListNode Previous;
  /**/
  /// <summary>
  /// 后一个
  /// </summary>
  public ListNode Next;
  public ListNode next
  {
      get
      {
          return Next;
      }
      set
      {
          Next = value;
      }
  }
  /**/
  /// <summary>
  /// 值
  /// </summary>
  public Objects goods;
  public Objects Goods
  {
      get
      {
          return goods;
      }
      set
      {
          goods = value;
      }
  }
}

在asp.net 中的双向链表的实现

定义链表中的节点的代码如下。
代码
pic class Clists
{
  public Clists()
  {
      //构造函数
      //初始化
      ListCountValue = 0;
      Head = null;
      Tail = null;
  }
  /**/
  /// <summary>
  /// 表名
  /// </summary>
  private string clistname = "";
  public string ClistName
  {
      get
      {
          return clistname;
      }
      set
      {
          clistname = value;
      }
  }
  /**/
  /// <summary>
  /// 头指针
  /// </summary>
  private ListNode Head;
  
  /**/
  /// <summary>
/// 尾指针
/// </summary>
private ListNode Tail;
  
/**/
/// <summary>
/// 当前指针
/// </summary>   
private ListNode Current;
public ListNode current
{
    get
    {
        return Current;
    }
    set
    {
        Current = value;
    }
}
  
/**/
/// <summary>
/// 链表数据的个数
/// </summary>  
private int ListCountValue;
在链表尾部添加数据的实现代码如下。
/**/
/// <summary>
/// 尾部添加数据
/// </summary>
public void Append(Objects DataValue)
{
    ListNode NewNode = new ListNode(DataValue);
    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;
            Tail.next = null;
            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>
public bool IsNull()
{
    if (ListCountValue == 0)
    return true;
    else
    return false;
}
/**/
/// <summary>
/// 判断是否为到达尾部
/// </summary>
public bool IsEof()
{
    if (Current == Tail)
    return true;
    else
    return false;
}
/**/
/// <summary>
/// 判断是否为到达头部
/// </summary>
public bool IsBof()
{
    if (Current == Head)
     return true;
    else
    return false;
}
public Objects GetCurrentValue()
{
    return Current.goods;
}
/**/
/// <summary>
/// 取得链表的数据个数
/// </summary>
  
public int ListCount
{
    get
    {
        return ListCountValue;
    }
}
清空链表的实现代码如下。


/**/
/// <summary>
/// 清空链表
/// </summary>
public void Clear()
{
    MoveFrist();
    while (!IsNull())
    {
        //若不为空链表,从尾部删除
        Delete();
    }
}
在当前位置前插入数据的代码如下。


/// <summary>
/// 在当前位置前插入数据
/// </summary>
public void Insert(Objects 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>
public void InsertAscending(Objects InsertValue)
{
    //参数：InsertValue 插入的数据
    //为空链表
    if (IsNull())
    {
        //添加
        Append(InsertValue);
        return;
    }
    //移动到头
    MoveFrist();
    if ((InsertValue.Number < GetCurrentValue().Number))
    {
        //满足条件，则插入，退出
        Insert(InsertValue);
        return;
    }
    while (true)
    {
        if (InsertValue.Number < GetCurrentValue().Number)
        {
            //满族条件，则插入，退出
            Insert(InsertValue);
            break;
        }
        if (IsEof())
        {
            //尾部添加
            Append(InsertValue);
            break;
        }
        //移动到下一个指针
        MoveNext();
    }
}
进行降序插入的代码如下。

  /**/
  /// <summary>
  /// 进行降序插入
  /// </summary>
  
  /**/
  /*货物入库*/
  public void InsertUnAscending(Objects InsertValue)
  {
      //参数：InsertValue 插入的数据
      //为空链表
      if (IsNull())
      {
          //添加
          Append(InsertValue);
          return;
      }
      //移动到头
      MoveFrist();
      if (InsertValue.Number > GetCurrentValue().Number)
      {
          //满足条件，则插入，退出
          Insert(InsertValue);
          return;
      }
      while (true)
      {
          if (InsertValue.Number > GetCurrentValue().Number)
          {
              //满足条件，则插入，退出
              Insert(InsertValue);
              break;
          }
          if (IsEof())
          {
              //尾部添加
              Append(InsertValue);
              break;
          }
          //移动到下一个指针
          MoveNext();