LinkedList.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / whidbey / NetFXspW7 / ndp / fx / src / CompMod / System / Collections / Generic / LinkedList.cs / 1 / LinkedList.cs

                             
namespace System.Collections.Generic {
    using System;
    using System.Diagnostics;
    using System.Runtime.Serialization; 
    using System.Security.Permissions;
 
    [Serializable()] 
    [System.Runtime.InteropServices.ComVisible(false)]
    [DebuggerTypeProxy(typeof(System_CollectionDebugView<>))] 
    [DebuggerDisplay("Count = {Count}")]
    public class LinkedList: ICollection, System.Collections.ICollection, ISerializable, IDeserializationCallback {
        // This LinkedList is a doubly-Linked circular list.
        internal LinkedListNode head; 
        internal int count;
        internal int version; 
        private Object _syncRoot; 

        private SerializationInfo siInfo; //A temporary variable which we need during deserialization. 

        // names for serialization
        const String VersionName = "Version";
        const String CountName = "Count"; 
        const String ValuesName = "Data";
 
        public LinkedList() { 
        }
 
        public LinkedList(IEnumerable collection) {
            if (collection==null) {
                throw new ArgumentNullException("collection");
            } 

            foreach( T item in collection) { 
                AddLast(item); 
            }
        } 

        protected LinkedList(SerializationInfo info, StreamingContext context) {
            siInfo = info;
        } 

        public int Count { 
            get { return count;} 
        }
 
        public LinkedListNode First {
            get { return head;}
        }
 
        public LinkedListNode Last {
            get { return head == null? null: head.prev;} 
        } 

        bool ICollection.IsReadOnly { 
            get { return false; }
        }

        void ICollection.Add(T value) { 
            AddLast(value);
        } 
 
        public LinkedListNode AddAfter(LinkedListNode node, T value) {
            ValidateNode(node); 
            LinkedListNode result = new LinkedListNode(node.list, value);
            InternalInsertNodeBefore(node.next, result);
            return result;
        } 

        public void AddAfter(LinkedListNode node, LinkedListNode newNode) { 
            ValidateNode(node); 
            ValidateNewNode(newNode);
            InternalInsertNodeBefore(node.next, newNode); 
            newNode.list = this;
        }

        public LinkedListNode AddBefore(LinkedListNode node, T value) { 
            ValidateNode(node);
            LinkedListNode result = new LinkedListNode(node.list, value); 
            InternalInsertNodeBefore(node, result); 
            if ( node == head) {
                head = result; 
            }
            return result;
        }
 
        public void AddBefore(LinkedListNode node, LinkedListNode newNode) {
            ValidateNode(node); 
            ValidateNewNode(newNode); 
            InternalInsertNodeBefore(node, newNode);
            newNode.list = this; 
            if ( node == head) {
                head = newNode;
            }
        } 

        public LinkedListNode AddFirst(T value) { 
            LinkedListNode result = new LinkedListNode(this, value); 
            if (head == null) {
                InternalInsertNodeToEmptyList(result); 
            }
            else {
                InternalInsertNodeBefore( head, result);
                head = result; 
            }
            return result; 
        } 

        public void AddFirst(LinkedListNode node) { 
            ValidateNewNode(node);

            if (head == null) {
                InternalInsertNodeToEmptyList(node); 
            }
            else { 
                InternalInsertNodeBefore( head, node); 
                head = node;
            } 
            node.list = this;
        }

        public LinkedListNode AddLast(T value) { 
            LinkedListNode result = new LinkedListNode(this, value);
            if (head== null) { 
                InternalInsertNodeToEmptyList(result); 
            }
            else { 
                InternalInsertNodeBefore( head, result);
            }
            return result;
        } 

        public void AddLast(LinkedListNode node) { 
            ValidateNewNode(node); 

            if (head == null) { 
                InternalInsertNodeToEmptyList(node);
            }
            else {
                InternalInsertNodeBefore( head, node); 
            }
            node.list = this; 
        } 

        public void Clear() { 
            LinkedListNode current = head;
            while (current != null ) {
                LinkedListNode temp = current;
                current = current.Next;   // use Next the instead of "next", otherwise it will loop forever 
                temp.Invalidate();
            } 
 
            head = null;
            count = 0; 
            version++;
        }

        public bool Contains(T value) { 
            return Find(value) != null;
        } 
 
        public void CopyTo( T[] array, int index) {
            if (array == null) { 
                throw new ArgumentNullException("array");
            }

            if(index < 0 || index > array.Length) { 
                throw new ArgumentOutOfRangeException("index",SR.GetString(SR.IndexOutOfRange, index) );
            } 
 
            if (array.Length - index < Count) {
                throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace)); 
            }

            LinkedListNode node = head;
            if (node != null) { 
                do {
                    array[index++] = node.item; 
                    node = node.next; 
                } while (node != head);
            } 
        }

        public LinkedListNode Find(T value) {
            LinkedListNode node = head; 
            EqualityComparer c = EqualityComparer.Default;
            if (node != null) { 
                if (value != null) { 
                    do {
                        if (c.Equals(node.item, value)) { 
                            return node;
                        }
                        node = node.next;
                    } while (node != head); 
                }
                else { 
                    do { 
                        if (node.item == null) {
                            return node; 
                        }
                        node = node.next;
                    } while (node != head);
                } 
            }
            return null; 
        } 

        public LinkedListNode FindLast(T value) { 
            if ( head == null) return null;

            LinkedListNode last = head.prev;
            LinkedListNode node = last; 
            EqualityComparer c = EqualityComparer.Default;
            if (node != null) { 
                if (value != null) { 
                    do {
                        if (c.Equals(node.item, value)) { 
                            return node;
                        }

                        node = node.prev; 
                    } while (node != last);
                } 
                else { 
                    do {
                        if (node.item == null) { 
                            return node;
                        }
                        node = node.prev;
                    } while (node != last); 
                }
            } 
            return null; 
        }
 
        public Enumerator GetEnumerator() {
            return new Enumerator(this);
        }
 
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator(); 
        } 

        public bool Remove(T value) { 
            LinkedListNode node = Find(value);
            if (node != null) {
                InternalRemoveNode(node);
                return true; 
            }
            return false; 
        } 

        public void Remove(LinkedListNode node) { 
            ValidateNode(node);
            InternalRemoveNode(node);
        }
 
        public void RemoveFirst() {
            if ( head == null) { throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty)); } 
            InternalRemoveNode(head); 
        }
 
        public void RemoveLast() {
            if ( head == null) { throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty)); }
            InternalRemoveNode(head.prev);
        } 

        [SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)] 		 
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context) { 
            // Customized serialization for LinkedList.
            // We need to do this because it will be too expensive to Serialize each node. 
            // This will give us the flexiblility to change internal implementation freely in future.
            if (info==null) {
                throw new ArgumentNullException("info");
            } 
            info.AddValue(VersionName, version);
            info.AddValue(CountName, count); //This is the length of the bucket array. 
            if ( count != 0) { 
                T[] array = new T[Count];
                CopyTo(array, 0); 
                info.AddValue(ValuesName, array, typeof(T[]));
            }
        }
 
        public virtual void OnDeserialization(Object sender) {
            if (siInfo==null) { 
                return; //Somebody had a dependency on this Dictionary and fixed us up before the ObjectManager got to it. 
            }
 
            int realVersion = siInfo.GetInt32(VersionName);
            int count = siInfo.GetInt32(CountName);

            if ( count != 0) { 
                T[] array = (T[]) siInfo.GetValue(ValuesName, typeof(T[]));
 
                if (array==null) { 
                    throw new SerializationException(SR.GetString(SR.Serialization_MissingValues));
                } 
                for ( int i = 0; i < array.Length; i++) {
                    AddLast(array[i]);
                }
            } 
            else {
                head = null; 
            } 

            version = realVersion; 
            siInfo=null;
        }

 
        private void InternalInsertNodeBefore(LinkedListNode node, LinkedListNode newNode) {
            newNode.next = node; 
            newNode.prev = node.prev; 
            node.prev.next = newNode;
            node.prev = newNode; 
            version++;
            count++;
        }
 
        private void InternalInsertNodeToEmptyList(LinkedListNode newNode) {
            Debug.Assert( head == null && count == 0, "LinkedList must be empty when this method is called!"); 
            newNode.next = newNode; 
            newNode.prev = newNode;
            head = newNode; 
            version++;
            count++;
        }
 
        internal void InternalRemoveNode(LinkedListNode node) {
            Debug.Assert( node.list == this, "Deleting the node from another list!"); 
            Debug.Assert( head != null, "This method shouldn't be called on empty list!"); 
            if ( node.next == node) {
                Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node"); 
                head  = null;
            }
            else {
                node.next.prev = node.prev; 
                node.prev.next = node.next;
                if ( head == node) { 
                    head = node.next; 
                }
            } 
            node.Invalidate();
            count--;
            version++;
        } 

        internal void ValidateNewNode(LinkedListNode node) { 
            if (node == null) { 
                throw new ArgumentNullException("node");
            } 

            if ( node.list != null) {
                throw new InvalidOperationException(SR.GetString(SR.LinkedListNodeIsAttached));
            } 
        }
 
 
        internal void ValidateNode(LinkedListNode node) {
            if (node == null) { 
                throw new ArgumentNullException("node");
            }

            if ( node.list != this) { 
                throw new InvalidOperationException(SR.GetString(SR.ExternalLinkedListNode));
            } 
        } 

        bool System.Collections.ICollection.IsSynchronized { 
            get { return false;}
        }

        object System.Collections.ICollection.SyncRoot  { 
            get {
                if( _syncRoot == null) { 
                    System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); 
                }
                return _syncRoot; 
            }
        }

        void System.Collections.ICollection.CopyTo(Array  array, int index) { 
            if (array == null) {
                throw new ArgumentNullException("array"); 
            } 

            if (array.Rank != 1) { 
                throw new ArgumentException(SR.GetString(SR.Arg_MultiRank));
            }

            if( array.GetLowerBound(0) != 0 ) { 
                throw new ArgumentException(SR.GetString(SR.Arg_NonZeroLowerBound));
            } 
 
            if (index < 0) {
                throw new ArgumentOutOfRangeException("index",SR.GetString(SR.IndexOutOfRange, index) ); 
            }

            if (array.Length - index < Count) {
                throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace)); 
            }
 
            T[] tArray = array as T[]; 
            if (tArray != null) {
                CopyTo(tArray, index); 
            }
            else {
                //
                // Catch the obvious case assignment will fail. 
                // We can found all possible problems by doing the check though.
                // For example, if the element type of the Array is derived from T, 
                // we can't figure out if we can successfully copy the element beforehand. 
                //
                Type targetType = array.GetType().GetElementType(); 
                Type sourceType = typeof(T);
                if(!(targetType.IsAssignableFrom(sourceType) || sourceType.IsAssignableFrom(targetType))) {
                    throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
                } 

                object[] objects = array as object[]; 
                if (objects == null) { 
                    throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
                } 
                    LinkedListNode node = head;
                try {
                    if (node != null) {
                        do { 
                            objects[index++] = node.item;
                            node = node.next; 
                        } while (node != head); 
                    }
                } 
                catch(ArrayTypeMismatchException) {
                    throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
                }
            } 
        }
 
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { 
            return GetEnumerator();
        } 


        [Serializable()]
        public struct Enumerator : IEnumerator, System.Collections.IEnumerator, ISerializable, IDeserializationCallback { 
            private LinkedList list;
            private LinkedListNode node; 
            private int version; 
            private T current;
            private int index; 
            private SerializationInfo siInfo; //A temporary variable which we need during deserialization.

            const string LinkedListName = "LinkedList";
            const string CurrentValueName = "Current"; 
            const string VersionName = "Version";
            const string IndexName = "Index"; 
 
            internal Enumerator(LinkedList list) {
                this.list = list; 
                version = list.version;
                node = list.head;
                current = default(T);
                index = 0; 
                siInfo = null;
            } 
 
            internal Enumerator(SerializationInfo info, StreamingContext context) {
                siInfo = info; 
                list = null;
                version = 0;
                node = null;
                current = default(T); 
                index = 0;
            } 
 
            public T Current {
                get { return current;} 
            }

            object System.Collections.IEnumerator.Current {
                get { 
                    if( index == 0 || (index == list.Count + 1)) {
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 
                    } 

                    return current; 
                }
            }

            public bool MoveNext() { 
                if (version != list.version) {
                    throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion)); 
                } 

                if (node == null) { 
                    index = list.Count + 1;
                    return false;
                }
 
                ++index;
                current = node.item; 
                node = node.next; 
                if (node == list.head) {
                    node = null; 
                }
                return true;
            }
 
            void System.Collections.IEnumerator.Reset() {
                if (version != list.version) { 
                    throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion)); 
                }
 
                current = default(T);
                node = list.head;
                index = 0;
            } 

            public void Dispose() { 
            } 

            void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) { 
                if (info==null) {
                    throw new ArgumentNullException("info");
                }
 
                info.AddValue(LinkedListName, list);
                info.AddValue(VersionName, version); 
                info.AddValue(CurrentValueName, current); 
                info.AddValue(IndexName, index);
            } 

            void IDeserializationCallback.OnDeserialization(Object sender) {
                if (list != null) {
                    return; //Somebody had a dependency on this Dictionary and fixed us up before the ObjectManager got to it. 
                }
 
                if (siInfo==null) { 
                    throw new SerializationException(SR.GetString(SR.Serialization_InvalidOnDeser));
                } 

                list = (LinkedList)siInfo.GetValue(LinkedListName, typeof(LinkedList));
                version = siInfo.GetInt32(VersionName);
                current = (T)siInfo.GetValue(CurrentValueName, typeof(T)); 
                index = siInfo.GetInt32(IndexName);
 
                if( list.siInfo != null) { 
                    list.OnDeserialization(sender);
                } 

                if( index == list.Count + 1) {  // end of enumeration
                    node = null;
                } 
                else {
                    node = list.First; 
                    // We don't care if we can point to the correct node if the LinkedList was changed 
                    // MoveNext will throw upon next call and Current has the correct value.
                    if( node != null && index != 0) { 
                        for(int i =0; i< index; i++) {
                            node = node.next;
                         }
                         if( node == list.First) { 
                             node = null;
                         } 
                     } 
                }
                siInfo=null; 
            }
        }

    } 

    // Note following class is not serializable since we customized the serialization of LinkedList. 
    [System.Runtime.InteropServices.ComVisible(false)] 
    public sealed class LinkedListNode {
        internal LinkedList list; 
        internal LinkedListNode next;
        internal LinkedListNode prev;
        internal T item;
 
        public LinkedListNode( T value) {
            this.item = value; 
        } 

        internal LinkedListNode(LinkedList list, T value) { 
            this.list = list;
            this.item = value;
        }
 
        public LinkedList List {
            get { return list;} 
        } 

        public LinkedListNode Next { 
            get { return next == null || next == list.head? null: next;}
        }

        public LinkedListNode Previous { 
            get { return prev == null || this == list.head? null: prev;}
        } 
 
        public T Value {
            get { return item;} 
            set { item = value;}
        }

        internal void Invalidate() { 
            list = null;
            next = null; 
            prev = null; 
        }
    } 
}


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
 
namespace System.Collections.Generic {
    using System;
    using System.Diagnostics;
    using System.Runtime.Serialization; 
    using System.Security.Permissions;
 
    [Serializable()] 
    [System.Runtime.InteropServices.ComVisible(false)]
    [DebuggerTypeProxy(typeof(System_CollectionDebugView<>))] 
    [DebuggerDisplay("Count = {Count}")]
    public class LinkedList: ICollection, System.Collections.ICollection, ISerializable, IDeserializationCallback {
        // This LinkedList is a doubly-Linked circular list.
        internal LinkedListNode head; 
        internal int count;
        internal int version; 
        private Object _syncRoot; 

        private SerializationInfo siInfo; //A temporary variable which we need during deserialization. 

        // names for serialization
        const String VersionName = "Version";
        const String CountName = "Count"; 
        const String ValuesName = "Data";
 
        public LinkedList() { 
        }
 
        public LinkedList(IEnumerable collection) {
            if (collection==null) {
                throw new ArgumentNullException("collection");
            } 

            foreach( T item in collection) { 
                AddLast(item); 
            }
        } 

        protected LinkedList(SerializationInfo info, StreamingContext context) {
            siInfo = info;
        } 

        public int Count { 
            get { return count;} 
        }
 
        public LinkedListNode First {
            get { return head;}
        }
 
        public LinkedListNode Last {
            get { return head == null? null: head.prev;} 
        } 

        bool ICollection.IsReadOnly { 
            get { return false; }
        }

        void ICollection.Add(T value) { 
            AddLast(value);
        } 
 
        public LinkedListNode AddAfter(LinkedListNode node, T value) {
            ValidateNode(node); 
            LinkedListNode result = new LinkedListNode(node.list, value);
            InternalInsertNodeBefore(node.next, result);
            return result;
        } 

        public void AddAfter(LinkedListNode node, LinkedListNode newNode) { 
            ValidateNode(node); 
            ValidateNewNode(newNode);
            InternalInsertNodeBefore(node.next, newNode); 
            newNode.list = this;
        }

        public LinkedListNode AddBefore(LinkedListNode node, T value) { 
            ValidateNode(node);
            LinkedListNode result = new LinkedListNode(node.list, value); 
            InternalInsertNodeBefore(node, result); 
            if ( node == head) {
                head = result; 
            }
            return result;
        }
 
        public void AddBefore(LinkedListNode node, LinkedListNode newNode) {
            ValidateNode(node); 
            ValidateNewNode(newNode); 
            InternalInsertNodeBefore(node, newNode);
            newNode.list = this; 
            if ( node == head) {
                head = newNode;
            }
        } 

        public LinkedListNode AddFirst(T value) { 
            LinkedListNode result = new LinkedListNode(this, value); 
            if (head == null) {
                InternalInsertNodeToEmptyList(result); 
            }
            else {
                InternalInsertNodeBefore( head, result);
                head = result; 
            }
            return result; 
        } 

        public void AddFirst(LinkedListNode node) { 
            ValidateNewNode(node);

            if (head == null) {
                InternalInsertNodeToEmptyList(node); 
            }
            else { 
                InternalInsertNodeBefore( head, node); 
                head = node;
            } 
            node.list = this;
        }

        public LinkedListNode AddLast(T value) { 
            LinkedListNode result = new LinkedListNode(this, value);
            if (head== null) { 
                InternalInsertNodeToEmptyList(result); 
            }
            else { 
                InternalInsertNodeBefore( head, result);
            }
            return result;
        } 

        public void AddLast(LinkedListNode node) { 
            ValidateNewNode(node); 

            if (head == null) { 
                InternalInsertNodeToEmptyList(node);
            }
            else {
                InternalInsertNodeBefore( head, node); 
            }
            node.list = this; 
        } 

        public void Clear() { 
            LinkedListNode current = head;
            while (current != null ) {
                LinkedListNode temp = current;
                current = current.Next;   // use Next the instead of "next", otherwise it will loop forever 
                temp.Invalidate();
            } 
 
            head = null;
            count = 0; 
            version++;
        }

        public bool Contains(T value) { 
            return Find(value) != null;
        } 
 
        public void CopyTo( T[] array, int index) {
            if (array == null) { 
                throw new ArgumentNullException("array");
            }

            if(index < 0 || index > array.Length) { 
                throw new ArgumentOutOfRangeException("index",SR.GetString(SR.IndexOutOfRange, index) );
            } 
 
            if (array.Length - index < Count) {
                throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace)); 
            }

            LinkedListNode node = head;
            if (node != null) { 
                do {
                    array[index++] = node.item; 
                    node = node.next; 
                } while (node != head);
            } 
        }

        public LinkedListNode Find(T value) {
            LinkedListNode node = head; 
            EqualityComparer c = EqualityComparer.Default;
            if (node != null) { 
                if (value != null) { 
                    do {
                        if (c.Equals(node.item, value)) { 
                            return node;
                        }
                        node = node.next;
                    } while (node != head); 
                }
                else { 
                    do { 
                        if (node.item == null) {
                            return node; 
                        }
                        node = node.next;
                    } while (node != head);
                } 
            }
            return null; 
        } 

        public LinkedListNode FindLast(T value) { 
            if ( head == null) return null;

            LinkedListNode last = head.prev;
            LinkedListNode node = last; 
            EqualityComparer c = EqualityComparer.Default;
            if (node != null) { 
                if (value != null) { 
                    do {
                        if (c.Equals(node.item, value)) { 
                            return node;
                        }

                        node = node.prev; 
                    } while (node != last);
                } 
                else { 
                    do {
                        if (node.item == null) { 
                            return node;
                        }
                        node = node.prev;
                    } while (node != last); 
                }
            } 
            return null; 
        }
 
        public Enumerator GetEnumerator() {
            return new Enumerator(this);
        }
 
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator(); 
        } 

        public bool Remove(T value) { 
            LinkedListNode node = Find(value);
            if (node != null) {
                InternalRemoveNode(node);
                return true; 
            }
            return false; 
        } 

        public void Remove(LinkedListNode node) { 
            ValidateNode(node);
            InternalRemoveNode(node);
        }
 
        public void RemoveFirst() {
            if ( head == null) { throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty)); } 
            InternalRemoveNode(head); 
        }
 
        public void RemoveLast() {
            if ( head == null) { throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty)); }
            InternalRemoveNode(head.prev);
        } 

        [SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)] 		 
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context) { 
            // Customized serialization for LinkedList.
            // We need to do this because it will be too expensive to Serialize each node. 
            // This will give us the flexiblility to change internal implementation freely in future.
            if (info==null) {
                throw new ArgumentNullException("info");
            } 
            info.AddValue(VersionName, version);
            info.AddValue(CountName, count); //This is the length of the bucket array. 
            if ( count != 0) { 
                T[] array = new T[Count];
                CopyTo(array, 0); 
                info.AddValue(ValuesName, array, typeof(T[]));
            }
        }
 
        public virtual void OnDeserialization(Object sender) {
            if (siInfo==null) { 
                return; //Somebody had a dependency on this Dictionary and fixed us up before the ObjectManager got to it. 
            }
 
            int realVersion = siInfo.GetInt32(VersionName);
            int count = siInfo.GetInt32(CountName);

            if ( count != 0) { 
                T[] array = (T[]) siInfo.GetValue(ValuesName, typeof(T[]));
 
                if (array==null) { 
                    throw new SerializationException(SR.GetString(SR.Serialization_MissingValues));
                } 
                for ( int i = 0; i < array.Length; i++) {
                    AddLast(array[i]);
                }
            } 
            else {
                head = null; 
            } 

            version = realVersion; 
            siInfo=null;
        }

 
        private void InternalInsertNodeBefore(LinkedListNode node, LinkedListNode newNode) {
            newNode.next = node; 
            newNode.prev = node.prev; 
            node.prev.next = newNode;
            node.prev = newNode; 
            version++;
            count++;
        }
 
        private void InternalInsertNodeToEmptyList(LinkedListNode newNode) {
            Debug.Assert( head == null && count == 0, "LinkedList must be empty when this method is called!"); 
            newNode.next = newNode; 
            newNode.prev = newNode;
            head = newNode; 
            version++;
            count++;
        }
 
        internal void InternalRemoveNode(LinkedListNode node) {
            Debug.Assert( node.list == this, "Deleting the node from another list!"); 
            Debug.Assert( head != null, "This method shouldn't be called on empty list!"); 
            if ( node.next == node) {
                Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node"); 
                head  = null;
            }
            else {
                node.next.prev = node.prev; 
                node.prev.next = node.next;
                if ( head == node) { 
                    head = node.next; 
                }
            } 
            node.Invalidate();
            count--;
            version++;
        } 

        internal void ValidateNewNode(LinkedListNode node) { 
            if (node == null) { 
                throw new ArgumentNullException("node");
            } 

            if ( node.list != null) {
                throw new InvalidOperationException(SR.GetString(SR.LinkedListNodeIsAttached));
            } 
        }
 
 
        internal void ValidateNode(LinkedListNode node) {
            if (node == null) { 
                throw new ArgumentNullException("node");
            }

            if ( node.list != this) { 
                throw new InvalidOperationException(SR.GetString(SR.ExternalLinkedListNode));
            } 
        } 

        bool System.Collections.ICollection.IsSynchronized { 
            get { return false;}
        }

        object System.Collections.ICollection.SyncRoot  { 
            get {
                if( _syncRoot == null) { 
                    System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); 
                }
                return _syncRoot; 
            }
        }

        void System.Collections.ICollection.CopyTo(Array  array, int index) { 
            if (array == null) {
                throw new ArgumentNullException("array"); 
            } 

            if (array.Rank != 1) { 
                throw new ArgumentException(SR.GetString(SR.Arg_MultiRank));
            }

            if( array.GetLowerBound(0) != 0 ) { 
                throw new ArgumentException(SR.GetString(SR.Arg_NonZeroLowerBound));
            } 
 
            if (index < 0) {
                throw new ArgumentOutOfRangeException("index",SR.GetString(SR.IndexOutOfRange, index) ); 
            }

            if (array.Length - index < Count) {
                throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace)); 
            }
 
            T[] tArray = array as T[]; 
            if (tArray != null) {
                CopyTo(tArray, index); 
            }
            else {
                //
                // Catch the obvious case assignment will fail. 
                // We can found all possible problems by doing the check though.
                // For example, if the element type of the Array is derived from T, 
                // we can't figure out if we can successfully copy the element beforehand. 
                //
                Type targetType = array.GetType().GetElementType(); 
                Type sourceType = typeof(T);
                if(!(targetType.IsAssignableFrom(sourceType) || sourceType.IsAssignableFrom(targetType))) {
                    throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
                } 

                object[] objects = array as object[]; 
                if (objects == null) { 
                    throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
                } 
                    LinkedListNode node = head;
                try {
                    if (node != null) {
                        do { 
                            objects[index++] = node.item;
                            node = node.next; 
                        } while (node != head); 
                    }
                } 
                catch(ArrayTypeMismatchException) {
                    throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
                }
            } 
        }
 
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { 
            return GetEnumerator();
        } 


        [Serializable()]
        public struct Enumerator : IEnumerator, System.Collections.IEnumerator, ISerializable, IDeserializationCallback { 
            private LinkedList list;
            private LinkedListNode node; 
            private int version; 
            private T current;
            private int index; 
            private SerializationInfo siInfo; //A temporary variable which we need during deserialization.

            const string LinkedListName = "LinkedList";
            const string CurrentValueName = "Current"; 
            const string VersionName = "Version";
            const string IndexName = "Index"; 
 
            internal Enumerator(LinkedList list) {
                this.list = list; 
                version = list.version;
                node = list.head;
                current = default(T);
                index = 0; 
                siInfo = null;
            } 
 
            internal Enumerator(SerializationInfo info, StreamingContext context) {
                siInfo = info; 
                list = null;
                version = 0;
                node = null;
                current = default(T); 
                index = 0;
            } 
 
            public T Current {
                get { return current;} 
            }

            object System.Collections.IEnumerator.Current {
                get { 
                    if( index == 0 || (index == list.Count + 1)) {
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); 
                    } 

                    return current; 
                }
            }

            public bool MoveNext() { 
                if (version != list.version) {
                    throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion)); 
                } 

                if (node == null) { 
                    index = list.Count + 1;
                    return false;
                }
 
                ++index;
                current = node.item; 
                node = node.next; 
                if (node == list.head) {
                    node = null; 
                }
                return true;
            }
 
            void System.Collections.IEnumerator.Reset() {
                if (version != list.version) { 
                    throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion)); 
                }
 
                current = default(T);
                node = list.head;
                index = 0;
            } 

            public void Dispose() { 
            } 

            void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) { 
                if (info==null) {
                    throw new ArgumentNullException("info");
                }
 
                info.AddValue(LinkedListName, list);
                info.AddValue(VersionName, version); 
                info.AddValue(CurrentValueName, current); 
                info.AddValue(IndexName, index);
            } 

            void IDeserializationCallback.OnDeserialization(Object sender) {
                if (list != null) {
                    return; //Somebody had a dependency on this Dictionary and fixed us up before the ObjectManager got to it. 
                }
 
                if (siInfo==null) { 
                    throw new SerializationException(SR.GetString(SR.Serialization_InvalidOnDeser));
                } 

                list = (LinkedList)siInfo.GetValue(LinkedListName, typeof(LinkedList));
                version = siInfo.GetInt32(VersionName);
                current = (T)siInfo.GetValue(CurrentValueName, typeof(T)); 
                index = siInfo.GetInt32(IndexName);
 
                if( list.siInfo != null) { 
                    list.OnDeserialization(sender);
                } 

                if( index == list.Count + 1) {  // end of enumeration
                    node = null;
                } 
                else {
                    node = list.First; 
                    // We don't care if we can point to the correct node if the LinkedList was changed 
                    // MoveNext will throw upon next call and Current has the correct value.
                    if( node != null && index != 0) { 
                        for(int i =0; i< index; i++) {
                            node = node.next;
                         }
                         if( node == list.First) { 
                             node = null;
                         } 
                     } 
                }
                siInfo=null; 
            }
        }

    } 

    // Note following class is not serializable since we customized the serialization of LinkedList. 
    [System.Runtime.InteropServices.ComVisible(false)] 
    public sealed class LinkedListNode {
        internal LinkedList list; 
        internal LinkedListNode next;
        internal LinkedListNode prev;
        internal T item;
 
        public LinkedListNode( T value) {
            this.item = value; 
        } 

        internal LinkedListNode(LinkedList list, T value) { 
            this.list = list;
            this.item = value;
        }
 
        public LinkedList List {
            get { return list;} 
        } 

        public LinkedListNode Next { 
            get { return next == null || next == list.head? null: next;}
        }

        public LinkedListNode Previous { 
            get { return prev == null || this == list.head? null: prev;}
        } 
 
        public T Value {
            get { return item;} 
            set { item = value;}
        }

        internal void Invalidate() { 
            list = null;
            next = null; 
            prev = null; 
        }
    } 
}


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK