C#实现链表

今天受一个帖子的刺激，再次复习起了数据结构与算法，那本《数据结构与算法（java版）》我还剩图和高级排序的几章没看，工作上也没我的事需要处理，就用C#重新写了一遍链表结构，权作复习。 定义List接口：     public    interface  List     {          bool  IsEmpty();          void  Unshift(Object obj);         Object Shift();          void  Push(Object obj);         Object Pop();          bool  Contain(Object obj);          void  Delete(Object obj);          void  PrintAll();         Object getHead();         Object getTail();         void Clear();     } 实现单向链表：   // 单向链表      public   class  SList:List     {          private  SNode head, tail;          public  SList()         {              this .head  =   this .tail  =   null ;         }          public   bool  IsEmpty()         {              return  head  ==   null ;         }          public   void  Unshift(Object obj)         {             head  =   new  SNode(obj, head);              if  (tail  ==   null )                 tail  =  head;         }          public  Object Shift()         {              if  (head  ==   null )                  throw   new  NullReferenceException();             Object value  =  head.value;              if  (head  ==  tail)                 head  =  tail  =   null ;              else                 head  =  head.next;              return  value;         }          public   void  Push(Object obj)         {              if  ( ! IsEmpty())             {                 tail.next  =   new  SNode(obj);                 tail  =  tail.next;             }              else                 head  =  tail  =   new  SNode(obj);         }          public  Object Pop()         {              if  (head  ==   null )                  throw   new  NullReferenceException();             Object obj  =  tail.value;              if  (head  ==  tail)                 head  =  tail  =   null ;              else             {                  // 查找前驱节点                  for  (SNode temp  =  head; temp.next  !=   null   &&   ! temp.next.Equals(tail); temp  =  temp.next)                     tail  =  temp;                 tail.next  =   null ;             }              return  obj;         }          public   void  PrintAll()         {              string  result  =   "" ;              for  (SNode temp  =  head; temp  !=   null ; temp  =  temp.next)                 result  +=   "   "   +  temp.value.ToString();             Console.WriteLine(result);         }          public   bool  Contain(Object obj)         {              if  (head  ==   null )                  return   false ;              else             {                  for  (SNode temp  =  head; temp  !=   null ; temp  =  temp.next)                 {                      if  (temp.value.Equals(obj))                          return   true ;                 }             }              return   false ;         }          public   void  Delete(Object obj)         {              if  ( ! IsEmpty())             {                  if  (head  ==  tail  &&  head.value.Equals(obj))                     head  =  tail  =   null ;                  else   if  (head.value.Equals(obj))                     head  =  head.next;                  else                 {                      // temp_prev为删除值的前驱节点                      for  (SNode temp_prev  =  head, temp  =  head.next; temp  !=   null ; temp_prev  =  temp_prev.next, temp  =  temp.next)                     {                          if  (temp.value.Equals(obj))                         {                             temp_prev.next  =  temp.next;   // 设置前驱节点的next为下个节点                               if  (temp  ==  tail)                                tail  =  temp_prev;                             temp  =   null ;                              break ;                         }                     }                 }             }         }          public   Object getHead()         {              return   this .head.value;         }          public  Object getTail()         {              return   this .tail.value;         }         public void Clear()         {             do             {                 Delete(head.value);             } while (!IsEmpty());         }     }      class  SNode     {          public  Object value;          public  SNode next;          public  SNode(Object value, SNode next)         {              this .value  =  value;              this .next  =  next;         }          public  SNode(Object value)         {              this .value  =  value;              this .next  =   null ;         }     } 实现双向链表：   // 双向链表      public   class  LinkedList:List     {          private  LinkedNode head, tail;          public  LinkedList()         {             head  =  tail  =   null ;         }          public   bool  IsEmpty()         {              return  head  ==   null ;         }          public   void  Unshift(Object obj)         {              if  (IsEmpty())                 head  =  tail  =   new  LinkedNode(obj);              else             {                 head  =   new  LinkedNode(obj,  null , head);                 head.next.prev  =  head;             }         }          public  Object Shift()         {              if  (IsEmpty())                  throw   new  NullReferenceException();             Object obj  =  head.value;              if  (head  ==  tail)                 head  =  tail  =   null ;              else             {                 head  =  head.next;                 head.prev  =   null ;             }              return  obj;         }          public   void  Push(Object obj)         {              if  (IsEmpty())                 head  =  tail  =   new  LinkedNode(obj);              else             {                 tail  =   new  LinkedNode(obj, tail,  null );                 tail.prev.next  =  tail;             }         }          public  Object Pop()         {              if  (IsEmpty())                  throw   new  NullReferenceException();             Object value  =  tail.value;              if  (head  ==  tail)                 head  =  tail  =   null ;              else             {                 tail  =  tail.prev;                 tail.next  =   null ;             }              return  value;         }          public   bool  Contain(Object obj)         {              if  (IsEmpty())                  return   false ;              else             {                  for  (LinkedNode temp  =  head; temp  !=   null ; temp  =  temp.next)                      if  (temp.value.Equals(obj))                          return   true ;             }              return   false ;         }          public   void  Delete(Object obj)         {              if  (IsEmpty())                  throw   new  NullReferenceException();              if  (head  ==  tail)                 head  =  tail  =   null ;              else             {                  for  (LinkedNode temp  =  head; temp  !=   null ; temp  =  temp.next)                 {                      if  (temp.value.Equals(obj))                     {                          if  (temp.value.Equals(obj))                         {                              if  (temp  ==  tail)                             {                                 tail  =  tail.prev;                                 tail.next  =   null ;                                  break ;                             }                              else   if  (temp  ==  head)                             {                                 head.next.prev  =   null ;                                 head  =  head.next;                             }                              else                                 temp.prev.next  =  temp.next;                         }                     }                 }             }         }          public   void  PrintAll()         {              string  result  =   "" ;              for (LinkedNode temp = head;temp != null ;temp = temp.next)                 result  +=   "   "   +  temp.value.ToString();             Console.WriteLine(result);         }          public  Object getHead()         {              return   this .head.value;         }          public  Object getTail()         {              return   this .tail.value;         }         public void Clear()         {             do             {                 Delete(head.value);             } while (!IsEmpty());         }     }      class  LinkedNode     {          public  Object value;          public  LinkedNode prev;          public  LinkedNode next;          public  LinkedNode(Object value, LinkedNode prev, LinkedNode next)         {              this .value  =  value;              this .next  =  next;              this .prev  =  prev;         }          public  LinkedNode(Object value)         {              this .value  =  value;         }     } 文章转自庄周梦蝶  ，原文发布时间5.17 相关资源：C#泛型实现单向链表实现