linkedlist.cs

来自「Data Structures and Algorithms with Obj」· CS 代码 · 共 245 行

namespace Opus6
{
    using System;
    using System.Text;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: LinkedList.cs,v 1.6 2001/10/28 19:50:09 brpreiss Exp $")]
    public class LinkedList
    {
        public void Append(object item)
        {
            Element element1 = new Element(this, item, null);
            if (this.head == null)
            {
                this.head = element1;
            }
            else
            {
                this.tail.next = element1;
            }
            this.tail = element1;
        }

        public void Copy(LinkedList list)
        {
            if (list != this)
            {
                this.Purge();
                for (Element element1 = list.head; element1 != null; element1 = element1.next)
                {
                    this.Append(element1.datum);
                }
            }
        }

        public void Extract(object item)
        {
            Element element1 = this.head;
            Element element2 = null;
            while ((element1 != null) && (element1.datum != item))
            {
                element2 = element1;
                element1 = element1.next;
            }
            if (element1 == null)
            {
                throw new ArgumentException("item not found");
            }
            if (element1 == this.head)
            {
                this.head = element1.next;
            }
            else
            {
                element2.next = element1.next;
            }
            if (element1 == this.tail)
            {
                this.tail = element2;
            }
        }

        public static void Main()
        {
            LinkedList list1 = new LinkedList();
            list1.Append(0x39);
            list1.Append("hello");
            list1.Append(null);
            Opus6.Console.WriteLine(list1);
            Opus6.Console.WriteLine("IsEmpty returns {0}", list1.IsEmpty);
        }

        public void Prepend(object item)
        {
            Element element1 = new Element(this, item, this.head);
            if (this.head == null)
            {
                this.tail = element1;
            }
            this.head = element1;
        }

        public void Purge()
        {
            this.head = null;
            this.tail = null;
        }

        public override string ToString()
        {
            StringBuilder builder1 = new StringBuilder();
            builder1.Append("LinkedList {");
            for (Element element1 = this.head; element1 != null; element1 = element1.next)
            {
                builder1.Append(element1.datum);
                if (element1.next != null)
                {
                    builder1.Append(",");
                }
            }
            builder1.Append("}");
            return builder1.ToString();
        }


        public object First
        {
            get
            {
                if (this.head == null)
                {
                    throw new ContainerEmptyException();
                }
                return this.head.datum;
            }
        }

        public Element Head
        {
            get
            {
                return this.head;
            }
        }

        public bool IsEmpty
        {
            get
            {
                return (this.head == null);
            }
        }

        public object Last
        {
            get
            {
                if (this.tail == null)
                {
                    throw new ContainerEmptyException();
                }
                return this.tail.datum;
            }
        }

        public Element Tail
        {
            get
            {
                return this.tail;
            }
        }


        protected Element head;
        protected Element tail;


        public sealed class Element
        {
            internal Element(LinkedList list, object datum, LinkedList.Element next)
            {
                this.list = list;
                this.datum = datum;
                this.next = next;
            }

            public void Extract()
            {
                LinkedList.Element element1 = null;
                if (this.list.head == this)
                {
                    this.list.head = this.next;
                }
                else
                {
                    element1 = this.list.head;
                    while ((element1 != null) && (element1.next != this))
                    {
                        element1 = element1.next;
                    }
                    if (element1 == null)
                    {
                        throw new InvalidOperationException();
                    }
                    element1.next = this.next;
                }
                if (this.list.tail == this)
                {
                    this.list.tail = element1;
                }
            }

            public void InsertAfter(object item)
            {
                this.next = new LinkedList.Element(this.list, item, this.next);
                if (this.list.tail == this)
                {
                    this.list.tail = this.next;
                }
            }

            public void InsertBefore(object item)
            {
                LinkedList.Element element1 = new LinkedList.Element(this.list, item, this);
                if (this == this.list.head)
                {
                    this.list.head = element1;
                }
                else
                {
                    LinkedList.Element element2 = this.list.head;
                    while ((element2 != null) && (element2.next != this))
                    {
                        element2 = element2.next;
                    }
                    element2.next = element1;
                }
            }


            public object Datum
            {
                get
                {
                    return this.datum;
                }
            }

            public LinkedList.Element Next
            {
                get
                {
                    return this.next;
                }
            }


            internal object datum;
            internal LinkedList list;
            internal LinkedList.Element next;
        }
    }
}