程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> 關於C# >> 數據結構(C#):雙鏈表

數據結構(C#):雙鏈表

編輯:關於C#

雙鏈表每個數據節點都有兩個指針,分別指向其後繼和前驅節點。與單鏈表只能訪問其後繼結點相比 ,具有更大的靈活性;當然占用更多的存儲空間。

前面的單鏈表和這裡的雙鏈表都使用了空的頭結點或稱啞節點,目的是實現有序鏈表時更方便。

直接看代碼:

/*
* File   :  DoubleLinkedList.cs
* Author  :  Zhenxing Zhou
* Date   :  2008-12-06, 2008-12-07
* Blog   :  http://www.xianfen.net/
*/
using System;
using System.Collections.Generic;

namespace Xianfen.Net.DataStructure
{
   public class DoubleLinkedListNode<T>
   {
     private T m_Value;
     private DoubleLinkedListNode<T> m_Next;
     private DoubleLinkedListNode<T> m_Prior;

     public T Value
     {
       get { return m_Value; }
       set { m_Value = value; }
     }

     public DoubleLinkedListNode<T> Next
     {
       get { return m_Next; }
       set { m_Next = value; }
     }

     public DoubleLinkedListNode<T> Prior
     {
       get { return m_Prior; }
       set { m_Prior = value; }
     }

     public DoubleLinkedListNode()
     {

     }

     public DoubleLinkedListNode(T t)
     {
       m_Value = t;
     }
   }

   public class DoubleLinkedList<T> : ILinearList<T>
   {
     protected int m_Count;
     protected DoubleLinkedListNode<T> m_Head;
     protected DoubleLinkedListNode<T> m_Tail;

     public DoubleLinkedList()
     {
       m_Count = 0;
       m_Head = new DoubleLinkedListNode<T>();
       m_Tail = m_Head;
     }

     public DoubleLinkedList(T t)
       : this()
     {
       m_Count = 1;
       m_Head.Next = new DoubleLinkedListNode<T>(t);
       m_Tail = m_Head.Next;
       m_Tail.Prior = m_Head;
     }

     public void Add(T t)
     {
       InsertAt(t, m_Count);
     }

     public void AddHead(T t)
     {
       InsertAt(t, 0);
     }

     public void AddTail(T t)
     {
       Add(t);
     }

     public void Clear()
     {
       m_Count = 0;
       m_Tail = m_Head;
       m_Head.Next = null;
       m_Head.Prior = null;
     }

     public int Count
     {
       get { return m_Count; }
     }

     public int Find(T t)
     {
       DoubleLinkedListNode<T> currentNode = m_Head;
       int pos = 0;

       while ((currentNode = currentNode.Next) != null)
       {
         if (currentNode.Value.Equals(t))
         {
           return pos;
         }

         pos++;
       }

       return -1;
     }

     public T GetAt(int pos)
     {
       return GetNodeAt(pos).Value;
     }

     public T GetHead()
     {
       return GetNodeAt(0).Value;
     }

     public T GetTail()
     {
       return m_Tail.Value;
     }

     public void InsertAt(T t, int pos)
     {
       if (pos > m_Count || pos < 0)
       {
         throw new IndexOutOfRangeException("pos");
       }

       if (m_Count == int.MaxValue)
       {
         throw new ArithmeticException();
       }

       DoubleLinkedListNode<T> insertNode = new DoubleLinkedListNode<T> (t);

       if (pos == m_Count)
       {
         insertNode.Prior = m_Tail;
         m_Tail.Next = insertNode;
         m_Tail = insertNode;
         m_Count++;
         return;
       }

       DoubleLinkedListNode<T> currentNode = GetNodeAt(pos);

       insertNode.Prior = currentNode.Prior;
       insertNode.Next = currentNode;
       currentNode.Prior.Next = insertNode;
       currentNode.Prior = insertNode;
       m_Count++;
     }

     private DoubleLinkedListNode<T> GetNodeAt(int pos)
     {
       if (pos >= m_Count || pos < 0)
       {
         throw new IndexOutOfRangeException("pos");
       }

       DoubleLinkedListNode<T> currentNode = null;

       // 最近的途徑找到pos位置的節點
       if (pos > m_Count / 2)
       {
         currentNode = m_Tail;
         pos = m_Count - pos - 1;

         while (pos-- > 0)
         {
           currentNode = currentNode.Prior;
         }
       }
       else
       {
         currentNode = m_Head.Next;

         while (pos-- > 0)
         {
           currentNode = currentNode.Next;
         }
       }

       return currentNode;
     }

     public bool IsEmpty
     {
       get { return m_Count == 0; }
     }

     public void RemoveAll()
     {
       Clear();
     }

     public void RemoveAt(int pos)
     {
       if (pos == m_Count - 1)
       {
         m_Tail = m_Tail.Prior;
         m_Tail.Next = null;
         m_Count--;
         return;
       }

       DoubleLinkedListNode<T> currentNode = GetNodeAt(pos);

       currentNode.Prior.Next = currentNode.Next;
       currentNode.Next.Prior = currentNode.Prior;
       m_Count--;
     }

     public void RemoveHead()
     {
       RemoveAt(0);
     }

     public void RemoveTail()
     {
       RemoveAt(m_Count - 1);
     }

     public void SetAt(int pos, T t)
     {
       GetNodeAt(pos).Value = t;
     }

     public IEnumerator<T> GetEnumerator()
     {
       DoubleLinkedListNode<T> currentNode = m_Head;

       while ((currentNode = currentNode.Next) != null)
       {
         yield return currentNode.Value;
       }
     }

     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
     {
       return GetEnumerator();
     }
   }
}

如果發現BUG請留言指出,下一篇介紹循環鏈表的實現。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved