发信人: Jobs (温少), 信区: DotNET        
标  题: 双向链表的C#实现（改进版本）
发信站: BBS 水木清华站 (Sun Jan  5 13:57:15 2003)


/**
*  
*  

    @author     <a href="wen">mailto:szuJobs@hotmail.com">wenshaojin</a>
    @created    January 2, 2003
    @version    1

*
**/
using System;
using System.Collections;
using System.IO;

using Matrix.Common.Utils;

namespace Matrix.Common.Collections
{
    /// <summary>
    /// 双向链表
    /// </summary>
    /// <remarks>
    /// 在需要经常中间插入和删除的数据列表，使用双向链表比ArrayList要快
    /// </remarks>
    public class DoublyLinkedList : IEnumerable
    {
        private DoublyLinkedListNode _first;
        private int _count;

        public DoublyLinkedList()
        {
            _count = 0;
            _first = null;
        }

        /// <summary>
        /// 链表中节点的数量
        /// </summary>
        public int Count
        {
            get
            {
                return _count;
            }
        }

        public object this[int pos]
        {
            get
            {
                if(pos < 0 || pos >= this._count)
                {
                    throw new ArgumentOutOfRangeException("pos");
                }

                DoublyLinkedListNode current = this._first;

                int index = 0;

                while(index < pos && current != null)
                {
                    index ++;
                    current = current.Right;
                }

                return current.Data;
            }
            set
            {
                if(pos < 0 || pos >= this._count)
                {
                    throw new ArgumentOutOfRangeException("pos");
                }

                DoublyLinkedListNode current = this._first;

                int index = 0;

                while(index < pos && current != null)
                {
                    index ++;
                    current = current.Right;
                }

                current.Data = value;
            }
        }

        private DoublyLinkedListNode FindNode(int pos)
        {
            //p will eventually point to k'th node
            DoublyLinkedListNode p = this._first;
            for(int i=0; i<pos && p != null; i++) // move p to pos'th
            {
                p = p.Right;
            }

            if(pos > 0 && p == null) // no pos'th
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            return p;
        }

        private void InsertBefore(DoublyLinkedListNode p, object data)
        {
            DoublyLinkedListNode y = new DoublyLinkedListNode();
            y.Data = data;

            y.Left = p.Left;
            y.Right = p;
            p.Left.Right = y;
            p.Left = y;
        }

        private void Remove(DoublyLinkedListNode p)
        {
            if(p == this._first)
            {
                this._first = this._first.Right;
                this._first.Left = null;
            }
            else if(p.Right == null)
            {
                p.Left.Right = null;
            }
            else
            {
                p.Left.Right = p.Right;
                p.Right.Left = p.Left;
            }
        }

        /// <summary>
        /// 从链表中删除指定元素
        /// </summary>
        /// <param name="pos"></param>
        public void RemoveAt(int pos)
        {
            if(pos < 0)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            DoublyLinkedListNode p = FindNode(pos);

            if(p == null)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            this.Remove(p);

            _count --;
        }

        /// <summary>
        /// 查找删除
        /// </summary>
        /// <param name="obj"></param>
        /// <returns>返回删除节点数量</returns>
        public int Remove(object item)
        {
            int itemCount = 0;
            DoublyLinkedListNode p = this._first;

            while(p != null)
            {
                object pData = p.Data;
                if(item == pData  
                    || pData!= null && pData.Equals(item)
                    )
                {
                    if(p == this._first)
                    {
                        this._first = this._first.Right;
                        this._first.Left = null;
                    }
                    else if(p.Right == null)
                    {
                        p.Left.Right = null;
                    }
                    else
                    {
                        p.Left.Right = p.Right;
                        p.Right.Left = p.Left;
                    }

                    this._count --;
                    itemCount ++;
                }

                p = p.Right;
            }

            return itemCount;
        }


        public bool Contains(object obj)
        {
            DoublyLinkedListNode p = this._first;

            while(p != null)
            {
                object pData = p.Data;
                if(obj == pData  
                    || pData!= null && pData.Equals(obj)
                    )
                {
                    return true;
                }

                p = p.Right;
            }

            return false;
        }


        public int IndexOf(object obj)
        {
            int itemIndex = 0;
            DoublyLinkedListNode p = this._first;

            while(p != null)
            {
                object pData = p.Data;
                if(obj == pData  
                    || pData!= null && pData.Equals(obj)
                    )
                {
                    return itemIndex;
                }

                p = p.Right;
                itemIndex ++;
            }

            return -1;
        }

        public void Insert(int pos, object data)
        {
            if(pos < 0)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            if(pos == 0)
            {
                DoublyLinkedListNode y = new DoublyLinkedListNode();
                y.Data = data;

                if(this._first == null)
                {
                    this._first = y;
                }
                else
                {
                    y.Right = this._first;
                    this._first.Left = y;
                    this._first = y;
                }
            }
            else
            {
                DoublyLinkedListNode p = FindNode(pos);

                InsertBefore(p, data);
            }

            _count ++;
        }

        public void MoveToFirst(int pos)
        {
            if(pos < 0 || this._first == null)
            {
                throw new ArgumentOutOfRangeException("pos"); //// no pos'th
            }

            if(pos == 0)
            {
                return;
            }

            DoublyLinkedListNode q = FindNode(pos);

            if(q == null)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            this.Remove(q);

            this._first.Left = q;
            q.Right = this._first;
            q.Left = null;
            this._first = q;
        }

        public void Swap(int posA, int posB)
        {
            if(posA <0 || posA >= this._count)
            {
                throw new ArgumentOutOfRangeException("posA");
            }

            if(posB <0 || posB >= this._count)
            {
                throw new ArgumentOutOfRangeException("posB");
            }

            DoublyLinkedListNode p = FindNode(posA);
            DoublyLinkedListNode q = FindNode(posB);

            this.Swap(p, q);
        }

        private void Swap(DoublyLinkedListNode p , DoublyLinkedListNode q)
        {
            if(p == q)
            {
                return;
            }

            DoublyLinkedListNode pLeft = p.Left;
            DoublyLinkedListNode pRight = p.Right;
            DoublyLinkedListNode qLeft = q.Left;
            DoublyLinkedListNode qRight = q.Right;

            if(qRight == p)
            {
                p.Left = qLeft;
                if(qLeft != null)
                {
                    qLeft.Right = p;
                }

                if(pRight != null)
                {
                    pRight.Left = q;
                }
                q.Right = pRight;

                q.Left = p;
                p.Right = q;

            }
            else if(pRight == q)
            {
                q.Left = pLeft;
                if(pLeft != null)
                {
                    pLeft.Right = q;
                }

                if(qRight != null)
                {
                    qRight.Left = p;
                }
                p.Right = qRight;

                p.Left = q;
                q.Right = p;
            }
            else
            {
                q.Left = pLeft;
                if(pLeft != null)
                {
                    pLeft.Right = q;
                }

                q.Right = pRight;
                if(pRight != null)
                {
                    pRight.Left = q;
                }

                p.Left = qLeft;
                if(qLeft != null)
                {
                    qLeft.Right = p;
                }

                p.Right = qRight;
                if(qRight != null)
                {
                    qRight.Left = p;
                }

            }

            if(this._first == p)
            {
                this._first = q;
            }
            else if(this._first == q)
            {
                this._first = p;
            }
        }

        public void Add(object data)
        {
            DoublyLinkedListNode y = new DoublyLinkedListNode();
            y.Data = data;

            if(this._first == null)
            {
                this._first = y;
                _count ++;
                return;
            }

            DoublyLinkedListNode current = this._first;

            while(current.Right != null)
            {
                current = current.Right;
            }

            current.Right = y;
            y.Left = current;

            _count ++;
        }

        /// <summary>
        ///  
        /// </summary>
        /// <param name="c"></param>
        public void AddRange(ICollection c)
        {
            foreach(object obj in c)
            {
                this.Add(obj);
            }
        }

        public void Sort()
        {
            object[] array = new object[this._count];
            this.CopyTo(array);

            Array.Sort(array);
             
            this.SetRange(0, array);
        }

        public void Sort(IComparer comparer)
        {
            object[] array = new object[this._count];
            this.CopyTo(array);

            Array.Sort(array, comparer);
             
            this.SetRange(0, array);
        }

        public void SetRange(int index, ICollection c)
        {
            if(index < 0 || index >= this._count)
            {
                throw new ArgumentOutOfRangeException("index");
            }

            DoublyLinkedListNode p = this._first;
            int itemIndex = 0;
            while(p != null)
            {
                if(itemIndex >= index)
                {
                    break;
                }

                p = p.Right;
                itemIndex ++;
            }

            if(itemIndex < index || p == null)
            {
                return;
            }

            IEnumerator e = c.GetEnumerator();

            while(e.MoveNext() && p != null)
            {
                p.Data = e.Current;
                p = p.Right;
            }
        }

        public void CopyTo(Array array)
        {
            DoublyLinkedListNode p = this._first;

            int itemIndex = 0;
            while(p != null)
            {
                array.SetValue(p.Data, itemIndex);

                p = p.Right;
                itemIndex ++;
            }
        }

        public object[] ToArray()
        {
            object[] array = new object[this._count];
            this.CopyTo(array);
            return array;
        }

        public Array ToArray(Type type)
        {
            if(type == null)
            {
                throw new ArgumentNullException("type");
            }

            Array array = Array.CreateInstance(type, this._count);
            this.CopyTo(array);
            return array;
        }

        public void Reverse()
        {
            object[] objArray = new object[this._count];

            this.CopyTo(objArray);

            Array.Reverse(objArray);

            this.SetRange(0, objArray);
        }

        /// <summary>
        /// 清除链表
        /// </summary>
        public void Clear()
        {
            this._first = null;
            _count = 0;
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public DoublyLinkedListEnumerator GetEnumerator()
        {
            return new DoublyLinkedListEnumerator(this);
        }

        private class DoublyLinkedListNode
        {
            public object Data;
            public DoublyLinkedListNode Left;
            public DoublyLinkedListNode Right;
        }

        public class DoublyLinkedListEnumerator : IEnumerator
        {
            private DoublyLinkedList _list;
            private DoublyLinkedListNode _location;

            public DoublyLinkedListEnumerator(DoublyLinkedList list)
            {
                this._list = list;
            }

            public bool MoveNext()
            {
                if(this._location == null)
                {
                    this._location = _list._first;
                }
                else
                {
                    this._location = this._location.Right;
                }

                return this._location != null;
            }

            public bool MovePrevious
            {
                get
                {
                    if(this._location == null)
                    {
                        this._location = _list._first;
                    }
                    else
                    {
                        this._location = this._location.Left;
                    }

                    return this._location != null;
                }
            }

            public void Reset()
            {
                this._location = _list._first;
            }

            public object Current
            {
                get
                {
                    return this._location.Data;
                }
            }
        }
    }
}

--

※ 来源:·BBS 水木清华站 smth.org·[FROM: 218.17.72.63]
上一篇
返回上一页
回到目录
回到页首
下一篇