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;

            }

                head = tail = new snode(obj);

        public object pop()

            object obj = tail.value;

                //查找前驅節點

                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)

                return false;

                for (snode temp = head; temp != null; temp = temp.next)

                {

                    if (temp.value.equals(obj))

                        return true;

                }

            return false;

        public void delete(object obj)

                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.next = null;

實作雙向連結清單：

 //雙向連結清單

    public class linkedlist:list

        private linkednode head, tail;

        public linkedlist()

            head = tail = null;

            if (isempty())

                head = tail = new linkednode(obj);

                head = new linkednode(obj, null, head);

                head.next.prev = head;

            object obj = head.value;

                head.prev = null;

                tail = new linkednode(obj, tail, null);

                tail.prev.next = tail;

            object value = tail.value;

                tail = tail.prev;

                for (linkednode temp = head; temp != null; temp = temp.next)

                            {

                                tail = tail.prev;

                                tail.next = null;

                                break;

                            }

                            else if (temp == head)

                                head.next.prev = null;

                                head = head.next;

                            else

                                temp.prev.next = temp.next;

            for(linkednode temp=head;temp!=null;temp=temp.next)

        public object gethead()

    }

    class linkednode

        public linkednode prev;

        public linkednode next;

        public linkednode(object value, linkednode prev, linkednode next)

            this.prev = prev;

        public linkednode(object value)

文章轉自莊周夢蝶  ，原文釋出時間5.17