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;
        }
    }