C#實現常用的數據結構：鏈表

僅共學習使用

節點定義及其鏈表實現，代碼如下：
//class ListNode and class list definitions.

using System;

namespace LinkedListLibrary
{
 /// <summary>
 /// class to represent one node in a list
 /// </summary>
 class ListNode
 {
  private object data;
  private ListNode next;

  //constructer to creat ListNode that refers to dataValue
  //and in last node in list
  public ListNode(object dataValue):this(dataValue,null)
  {
  }

  //constructer to creat ListNode that refers to dataValue
  //and refer to next ListNode in List
  public ListNode(object dataValue,ListNode nextNode)
  {
   data = dataValue;
   next = nextNode;
  }

  //property Next
  public ListNode Next
  {
   get
   {
    return next;
   }
   set
   {
    next = value;
   }
  }
  //property Data
  public object Data
  {
   get{
    return data;
   }
  }
 }//end class ListNode

 //class List definition
 public class List
 {
  private ListNode firstNode;
  private ListNode lastNode;
  private string name;  //string like "list" to display

  //construct empty list with specifIEd name
  public List(string listName){
   name = listName;
   firstNode = lastNode = null;
  }

  //construct empty list with "list" as its name
  public List(

):this("list"){
  }

  //Insert object at front of list.If List is empty,
  //firstNode and lastNode will refer to same object.
  //Otherwise,firstNode refer to new node.
  public void InsertAtFront(object insertItem){
   lock(this){
    if(IsEmpty()){
     firstNode = lastNode = new ListNode(insertItem);
    }
    else{
     firstNode = new ListNode(insertItem,firstNode);
    }
   }
  }

  //return true if list is empty
  public bool IsEmpty(){
   lock(this){
    return firstNode == null;
   }
  }

  //Insert object at the end of list.If List is empty,
  //firstNode and lastNode will refer to same object.
  //otherwise,lastNode's Next property refers to new node
  public void InsertAtBack(object insertItem){
   lock(this){
    if(IsEmpty()){
     firstNode = lastNode = new ListNode(insertItem);
    }
    else{
     lastNode = lastNode.Next = new ListNode(insertItem);
    }
   }
  }

  //remove first node from list
  public object RemoveFromFront(){
   lock(this){
    if(IsEmpty()){
     throw new EmptyListException( name );
    }

    object removeItem = firstNode.Data; //retrIEve data

    //reset firstNode and lastNode refereances
    if(firstNode == lastNode)
     firstNode = lastNode = null;
    else
     firstNode = firstNode.Next;

    return removeItem; //return removed data
   }

  }

  //remove last node from list
  public object RemoveFromBack()
  {
   lock(this){
    if(IsEmpty()){
     throw new EmptyListException( name );
    }

    object removeItem = lastNode.Data; //retrIEve data

    //reset firstNode and lastNode refereances
    if(firstNode == lastNode)
     firstNode = lastNode = null;
    else{
     ListNode current = firstNode;

     //loop while current node is not lastNode
     while(current.Next != lastNode){
      current = current.Next;   //move to next node
     }
     
     //current is new lastNode
     lastNode = current;
     current.Next = null;
    }
    return removeItem; //return removed data
   } 
  }

  //output list contents
  virtual public void Print(){
   lock(this){
    if(IsEmpty()){
     Console.WriteLine("Empty " + name) ;
     return;
    }

    Console.Write("The " + name + " is: ");

    ListNode current = firstNode;

    //output current node data while not at end of list
    while(current != null){
     Console.Write(current.Data + "");
     current = current.Next;
    }

    Console.WriteLine("\n");
   }
  }

 }// end class List

 //class EmptyListException definition

 public class EmptyListException : ApplicationException
 {
  public EmptyListException(string name):base("The " + name + "is empty"){
  }
 }//end class EmptyListException
}//end namespace linkedlistlibrary


使用上面的鏈表，代碼如下：
using System;
using LinkedListLibrary;

namespace ListTest
{
 /// <summary>
 /// ListTest 的摘要說明。
 /// </summary>
 public class ListTest
 {
  /// <summary>
  /// 應用程序的主入口點。
  /// </summary>
  [STAThread]
  static void Main(string[] args)
  {
   //
   // TODO: 在此處添加代碼以啟動應用程序
   //
   List list = new List();

   //create data to store in list
   bool aBoolean = true;
   char aCharactor = '$';
   int anInteger = 34567;
   string aString = "hello";

   //use List insert methods
   list.InsertAtFront(aBoolean);
   list.Print();
   list.InsertAtFront(aCharactor);
   list.Print();
   list.InsertAtBack(anInteger);
   list.Print();
   list.InsertAtBack(aString);
   list.Print();

   //use list remove methods
   object removedObject;

   //remove data from list and print after each removal
   try
   {
    removedObject = list.RemoveFromFront();
    Console.WriteLine(removedObject + " removed");
    list.Print();

    removedObject = list.RemoveFromFront();
    Console.WriteLine(removedObject + " removed");
    list.Print();

    removedObject = list.RemoveFromBack();
   &nbsp;Console.WriteLine(removedObject + " removed");
    list.Print();

    removedObject = list.RemoveFromBack();
    Console.WriteLine(removedObject + " removed");
    list.Print();
   }
    //process exception if list empty when attempt is made to remove item
   catch(EmptyListException emptyListException)
   {
    Console.Error.WriteLine("\n" + emptyListException);
   }
  }//end method Main
 }//end class ListTest
}